On LP-based approximability for strict CSPs

MaRDI QIDQ5365139zbMATH OpenFDO

Authors Amit Kumar, Rajsekar Manokaran, Madhur Tulsiani, Nisheeth K. Vishnoi

Publication date 29 September 2017

Full work available at URL http://dl.acm.org/citation.cfm?id=2133157

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25) Linear programming (90C05) Combinatorial optimization (90C27)

Recommendations

• Approximating CSPs using LP relaxation
• No small linear program approximates vertex cover within a factor \(2 -\varepsilon\)
• From weak to strong LP gaps for all CSPs
• Inapproximability of combinatorial problems via small LPs and SDPs
• Towards sharp inapproximability for any 2-CSP

Cited in

(10)

• Towards a characterization of constant-factor approximable finite-valued CSPs
• Nearly optimal NP-hardness of vertex cover on k-uniform k-partite hypergraphs
• Approximating CSPs using LP relaxation
• Nearly tight approximation bounds for vertex cover on dense \(k\)-uniform \( k\)-partite hypergraphs
• The quest for strong inapproximability results with perfect completeness
• The power of Sherali-Adams relaxations for general-valued CSPs
• PTAS for Sparse General-valued CSPs
• Minimizing the sum of weighted completion times in a concurrent open shop
• The Sherali-Adams and Weisfeiler-Leman hierarchies in (promise valued) constraint satisfaction problems
• On the constant-factor approximability of minimum cost constraint satisfaction problems

This page was built for publication: On LP-based approximability for strict CSPs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5365139)