Polynomial time preprocessing data reduction

CHRISTOPHE PAUL - pefav

English

51 Pages

Start your free trial

Read an excerpt

Gain access to the library to view online
Learn more

About
Information

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

Time complexity

Informations

Published by	pefav
Published	01 January 2012
Reads	12
Language	English

From the same publisher

See all

Digital mathematics libraries: The good the bad the ugly

THIERRY BOUCHE

Thierry LEQUEU Avril DATA076 Fichier PROJETS IUT2 DOC

THIERRY LEQUEU

”What mathematicians know about the solutions of Schrodinger Coulomb Hamiltonian

Thierry LEQUEU Juin DATA076 Fichier PROJETS IUT5 DOC

THIERRY LEQUEU

Learning on images with segmentation graph kernels

FRANCIS BACH

Machine Learning Summer School Ile de Re Learning with sparsity inducing norms slides

FRANCIS BACH

Report a problem

Polynomial

KERNELIZATION

time preprocessing - data

Christophe Paul

Journ´eeAlgo&Calcul-NUMEV 11 Janvier 2012

reduction

Don’t expecteﬃcientexactalgorithms for a number of problems !

What does computational theory tell us ?

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

ICPTPehrome,arorAotoG,egieFlPde¨o(G0120zeriM,toavzsaSrfawinsserldwad,Lo,Lundeensent(Iy)epndzSdndegeuS,aanadon’texpemated)IDaepporixctnaonbtmsthrigoalontimaixorppatneicﬃetcn...dsoo!Ianlemsrpborefounbmofar

What does computational theory tell us ?

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

IDon’t expecteﬃcientexactalgorithms 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 expecteﬃcientapproximationalgorithms for a number of problems !

Inadsoon...

What does computational theory tell us ?

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

IDon’t expecteﬃcientexactalgorithms 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 expecteﬃcientapproximationalgorithms 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.buﬀalo.edu/selman/report/,1999.

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