Strong reductions for extended formulations

• 成果类型: Article
• 署名作者: Braun, Gabor; Pokutta, Sebastian; Roy, Aurko
• 署名单位: University System of Georgia; Georgia Institute of Technology; University System of Georgia; Georgia Institute of Technology
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-018-1316-y
• 发表日期: 2018
• 页码: 591-620
• 关键词: sparsest-cut

摘要

We generalize the reduction mechanism for linear programming problems and semidefinite programming problems from Braun et al. (Inapproximability of combinatorial problems via small LPs and SDPs, 2015) in two ways (1) relaxing the requirement of affineness, and (2) extending to fractional optimization problems. As applications we provide several new LP-hardness and SDP-hardness results, e.g., for the SparsestCut problem, the BalancedSeparator problem, and the MaxCut problem and show how to extend ad-hoc reductions between Sherali-Adams relaxations to reductions between LPs.