Showing cs.DSShow all
2 papers · 1 filter
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.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…