Lundi 13 février 2011 à 14h salle A711
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.