2 CSPs All Are Approximable Within a Constant Differential Factor - Université des Antilles Accéder directement au contenu
Communication Dans Un Congrès Année : 2018

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 .
Fichier principal
Vignette du fichier
ISCO2018_paper_91.pdf (361.65 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-02350144 , version 1 (05-11-2019)

Identifiants

  • HAL Id : hal-02350144 , version 1

Citer

Jean-François Culus, Sophie Toulouse. 2 CSPs All Are Approximable Within a Constant Differential Factor. International Symposiyum on Combinatorial Optomisation, Apr 2018, Marrakesh, Morocco. ⟨hal-02350144⟩
89 Consultations
135 Téléchargements

Partager

Gmail Facebook X LinkedIn More