2 CSPs All Are Approximable Within a Constant Differential Factor
Résumé
Only a few facts are known regarding the approximability of optimization CSPs with respect to the differential approximation measure , which compares the gain of a given solution over the worst solution value to the instance diameter. Notably, the question whether k CSP−q is approximable within any constant factor is open in case when q ≥ 3 or k ≥ 4. Given three integers k ≥ 2, p ≥ k and q > p, we analyse the expansion of a precise reduction from k CSP−q to k CSP−p. We introduce a family of combinatorial designs from which we deduce a lower bound of 1/(q − p + k/2) k for this expansion. When p = k = 2, this implies together with the result of Nesterov as regards 2 CSP−2 [?] that for all constant integers q ≥ 2, 2 CSP−q is approximable within factor (2 − π/2)/(q − 1) 2 .
Origine : Fichiers produits par l'(les) auteur(s)