2 CSPs All Are Approximable Within a Constant Differential Factor

Abstract : 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 .
Complete list of metadatas

https://hal.univ-antilles.fr/hal-02350144
Contributor : Jean-François Culus <>
Submitted on : Tuesday, November 5, 2019 - 11:17:23 PM
Last modification on : Friday, November 8, 2019 - 1:41:13 AM

File

ISCO2018_paper_91.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02350144, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

4

Files downloads

2