Polynomial time preprocessing data reduction

Christophe Paul

Description

KERNELIZATION Polynomial time preprocessing - data reduction Christophe Paul Journee Algo & Calcul - NUMEV 11 Janvier 2012

• approximation algorithms


• developing means


• computational theory


• karp's list


• np -complete problems


• calcul - numev


• algorithms has


• polynomial time

Sujets

• Approximation algorithm
• Theory of computation
• Time complexity

Informations

• Publié par: pefav
• Publié le: 01 janvier 2012
• Nombre de lectures: 12
• Langue: English

Extrait

Polynomial

KERNELIZATION

time preprocessing - data

Christophe Paul

Journ´eeAlgo&Calcul-NUMEV 11 Janvier 2012

reduction

Don’t expectefficientexactalgorithms for a number of problems !

I

What does computational theory tell us ?

SAT is NP-Complete [Cook’s Theorem, 1971] + Karp’s list of 21 NP-Complete problems [1972]

I

I CPTPehrome,arorAotoG,egieFlPde¨o(G0120zeri M,toavzsaSrfawin sserldwa d,Lo , Lun deensent(I y) epnd zSdndegeuS,aanad on’texpe mated) ID aepporixctnaonbt msthrigoalontimaixorppatneicffietc n...dsoo ! I an lemsrpborefounbmofar

What does computational theory tell us ?

I

I

SAT is NP-Complete [Cook’s Theorem, 1971] + Karp’s list of 21 NP-Complete problems [1972]

IDon’t expectefficientexactalgorithms for a number of problems !

PCP Theorem (002e1ledozirPG¨to Arora, Feige, Goldwasser, Lund, Lovasz, Motwani Safra, Sudan and Szegedy) (Independent set cannot be approximated)

IDon’t expectefficientapproximationalgorithms for a number of problems !

I nadsoon...

What does computational theory tell us ?

I

I

I

SAT is NP-Complete [Cook’s Theorem, 1971] + Karp’s list of 21 NP-Complete problems [1972]

IDon’t expectefficientexactalgorithms for a number of problems !

PCP Theorem (¨GledozirP00e21to Arora, Feige, Goldwasser, Lund, Lovasz, Motwani Safra, Sudan and Szegedy) (Independent set cannot be approximated)

IDon’t expectefficientapproximationalgorithms for a number of problems !

and so on . . .

What does computational theory tell us ?

InChallenges for theory of computing: Report for an NSF-sponsored workshop on research in theoretical computer science. Condon, Edelsbrunner, Emerson, Fortnow, Haber, Karp, Leivant, Lipton, Lynch, Parberry, Papadimitriou, Rabin, Rosenberg, Royer, Savage, Selman, Smith, Tardos, and Vitter.

Available at http://www.cs.buffalo.edu/selman/report/,1999.

[ . . . Whiletheoretical workon models of computation and methods for analyzing algorithms has had enormous payoffs, we are not done. In many situations,simple algorithms do well.We don’t understand why!

naatrnod c lae upmorsteagisndraalch a f glrotimhasdnehuristicsonrealda profsnaenitciderrfpehegteoncmaorDevingmelop ]...shmitorlgnaeingle