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

2015/10/07 by Kurpisz, Adam, Leppänen, Samuli, Mastrolilli, Monaldo · 1 citation
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1510.01891

Abstract

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.

Cited by

• On the Bit Size of Sum-of-Squares Proofs for Symmetric Formulations

Related

• Tight Sum-of-Squares lower bounds for binary polynomial optimization problems
• The Lasserre Hierarchy in Almost Diagonal Form
• Sum-of-squares hierarchy lower bounds for symmetric formulations
• Exactness and Effective Degree Bound of Lasserre's Relaxation for Polynomial Optimization over Finite Variety
• On the hardness of deciding the finite convergence of Lasserre hierarchies