An unbounded Sum-of-Squares hierarchy integrality gap for a polynomially solvable problem

• 成果类型: Article
• 署名作者: Kurpisz, Adam; Leppanen, Samuli; Mastrolilli, Monaldo
• 署名单位: Universita della Svizzera Italiana
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-016-1102-7
• 发表日期: 2017
• 页码: 1-17
• 关键词: lasserre; number; proofs; bounds

摘要

In this paper we study the complexity of the Min-sum single machine scheduling problem under algorithms from the Sum-of-Squares/Lasserre hierarchy. We prove the first lower bound for this model by showing that the integrality gap is unbounded at level even for a variant of the problem that is solvable in time by the Moore-Hodgson algorithm, namely Min-number of late jobs. We consider a natural formulation that incorporates the objective function as a constraint and prove the result by partially diagonalizing the matrix associated with the relaxation and exploiting this characterization. To the best of our knowledge, our result provides the first example where the Sum-of-Squares hierarchy exhibits an unbounded integrality gap for a polynomially solvable problem after non-constant number of levels.