3 papers
cs.DS2015
A Lasserre Lower Bound for the Min-Sum Single Machine Scheduling Problem
Adam Kurpisz, Samuli Leppänen, Monaldo Mastrolilli
The Min-sum single machine scheduling problem (denoted 1||sum f_j) generalizes a large number of sequencing problems. The first constant approximation guarantees have been obtained…
cs.CC2015
On the Hardest Problem Formulations for the 0/1 Lasserre Hierarchy
Adam Kurpisz, Samuli Leppänen, Monaldo Mastrolilli
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 con…
cs.DS2014
Sum-of-squares hierarchy lower bounds for symmetric formulations
Adam Kurpisz, Samuli Leppänen, Monaldo Mastrolilli
We introduce a method for proving Sum-of-Squares (SoS)/ Lasserre hierarchy lower bounds when the initial problem formulation exhibits a high degree of symmetry. Our main technical…