Affine reductions for LPs and SDPs

• 成果类型: Article
• 署名作者: Braun, Gabor; Pokutta, Sebastian; Zink, Daniel
• 署名单位: University System of Georgia; Georgia Institute of Technology
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-017-1221-9
• 发表日期: 2019
• 页码: 281-312
• 关键词: max-cut; Approximation algorithms; extension complexity; independent set; Inapproximability; hardness; optimization

摘要

We define a reduction mechanism for LP and SDP formulations that degrades approximation factors in a controlled fashion. Our reduction mechanism is a minor restriction of classical hardness reductions requiring an additional independence assumption and it allows for reusing many hardness reductions that have been used to show inapproximability in the context of PCP theorems. As a consequence we establish strong linear programming inapproximability (for LPs with a polynomial number of constraints) for many problems. In particular we obtain a epsilon inapproximability for answering an open question in Chan et al. (Proceedings of FOCS, pp. 350-359, 2013, https://doi.org/10.1109/FOCS.2013.45) and prove an inapproximability factor of epsilon for bounded degree . In the case of SDPs, we obtain inapproximability results for these problems relative to the SDP-inapproximability of MaxCUT. Moreover, using our reduction framework we are able to reproduce various results for CSPs from Chan et al. (Proceedings of FOCS, pp. 350-359, 2013, https://doi.org/10.1109/FOCS.2013.45) via simple reductions from Max-2-XOR.