Polynomial time preprocessing data reduction

Polynomial time preprocessing data reduction

-

Documents
51 pages
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

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

Informations

Publié par
Ajouté le 01 janvier 2012
Nombre de lectures 12
Langue English
Signaler un abus
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