Séminaire d'Optimisation Combinatoire

LAMSADE, Université Paris-Dauphine

Organisateur : Cristina Bazgan

Prochains exposés:
Lundi 13 février 2011 à 14h salle A711
Sophie Toulouse, LIPN, Université Paris 13
Titre : Approximation différentielle des problèmes d'optimisation SNP
Abstract: We revisit the class SNPO of the SNP optimization problems under the differential approximation paradigm, focusing on three questions: what is the largest k such that the k-ary boolean Constraint Satisfaction Problems, CSP are DAPX? more generally, how affine and differential approximation preserving reductions do arrange SNPO problems? in a more structural point of view, what differential approximation guarantee can we expect from local optima? We here show that 3-ary boolean CSP are 0,2146-differential approximable. We also show that any (2k)-ary boolean CSP is equivalent to MaxNAE(2k)Sat, and that any (2k+1)-ary CSP is (r/2)-differential approximable, if MaxNAE(2k)Sat is r-differential approximable. We finally review some interesting observations regarding neighborhood structures, notably: on the one hand, 1-bounded local optima are 1/(n+1)-differential approximate for MaxNAE2Sat; on the other hand, given any solution of any k-ary boolean CSP, its k-bounded neighborhood contains a solution that is (1/n^k)-differential approximate. We therefore leave many questions unanswered, in particular: are 4-ary boolean CSP constantly differential approximable? what about (2k)-ary boolean CSP vs. (2k-1)-ary boolean CSP? However, this talk also aims at providing somme clues in order to go further. The talk is based on a joint work with Jean-François Culus and Frédéric Roupin.

Les anciens exposés de 2012

Les anciens exposés de 2011

Les anciens exposés de 2010

Les anciens exposés de 2009

Les anciens exposés de 2008

Les anciens exposés de 2007