Skip to Main content Skip to Navigation
Conference papers

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 metadata
Contributor : Jean-François Culus <>
Submitted on : Tuesday, November 5, 2019 - 11:17:23 PM
Last modification on : Tuesday, March 24, 2020 - 1:11:48 AM
Long-term archiving on: : Friday, February 7, 2020 - 12:27:08 PM


Files produced by the author(s)


  • HAL Id : hal-02350144, version 1


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⟩



Record views


Files downloads