Towards a characterization of constant-factor approximable finite-valued CSPs

作者：

Highlights：

• New natural algebraic conditions for the finiteness of the integrality gap for the basic LP relaxation of VCSP are given.

• Efficient constant-factor approximation algorithms using the algebraic conditions are given.

• Algebraic conditions for NP-hardness of constant-factor approximation are given.

摘要

•New natural algebraic conditions for the finiteness of the integrality gap for the basic LP relaxation of VCSP are given.•Efficient constant-factor approximation algorithms using the algebraic conditions are given.•Algebraic conditions for NP-hardness of constant-factor approximation are given.

论文关键词：Constraint satisfaction problem,Approximation algorithms,Universal algebra

论文评审过程：Received 23 September 2016, Revised 17 January 2018, Accepted 15 March 2018, Available online 17 April 2018, Version of Record 13 August 2018.

论文官网地址：https://doi.org/10.1016/j.jcss.2018.03.003