On the Hardest Problem Formulations for the 0/1 Lasserre Hierarchy

• 成果类型: Article
• 署名作者: Kurpisz, Adam; Leppanen, Samuli; Mastrolilli, Monaldo
• 署名单位: Universita della Svizzera Italiana
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2016.0797
• 发表日期: 2017
• 页码: 135-143
• 关键词: approximation algorithms; optimization; squares; proofs; bounds; sums

摘要

The Lasserre/Sum-of-Squares (SoS) hierarchy is a systematic procedure for constructing a sequence of increasingly tight semidefinite relaxations. It is known that the hierarchy converges to the 0/1 polytope in n levels and captures the convex relaxations used in the best available approximation algorithms for a wide variety of optimization problems. In this paper we characterize the set of 0/1 integer linear problems and unconstrained 0/1 polynomial optimization problems that can still have an integrality gap at level n-1. These problems are the hardest for the Lasserre hierarchy in this sense.