Polynomial time preprocessing data reduction

-

English
51 Pages
Read an excerpt
Gain access to the library to view online
Learn more

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


Subjects

Informations

Published by
Published 01 January 2012
Reads 12
Language English
Report a problem
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