Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Polynomial time preprocessing data reduction

De
51 pages
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


Voir plus Voir moins
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
ICPTPehrome,arorAotoG,egieFlPde¨o(G0120zeriM,toavzsaSrfawinsserldwad,Lo,Lundeensent(Iy)epndzSdndegeuS,aanadontexpemated)IDaepporixctnaonbtmsthrigoalontimaixorppatneicetcn...dsoo!Ianlemsrpborefounbmofar
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 !
Inadsoon...
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!
naatrnodclaeupmorsteagisndraalchafglrotimhasdnehuristicsonrealdaprofsnaenitciderrfpehegteoncmaorDevingmelop]...shmitorlgnaeingle
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin