A Lasserre Lower Bound for the Min-Sum Single Machine Scheduling Problem

The Min-sum single machine scheduling problem (denoted 1|| ∑ 

f

j

) generalizes a large number of sequencing problems. The first constant approximation guarantees have been obtained only recently and are based on natural time-indexed LP relaxations strengthened with the so called

Knapsack-Cover

inequalities (see Bansal and Pruhs, Cheung and Shmoys and the recent (4 + 

ε

)-approximation by Mestre and Verschae). These relaxations have an integrality gap of 2, since the Min-knapsack problem is a special case. No APX-hardness result is known and it is still conceivable that there exists a PTAS. Interestingly, the Lasserre hierarchy relaxation, when the objective function is incorporated as a constraint, reduces the integrality gap for the Min-knapsack problem to 1 + 

ε

.

In this paper we study the complexity of the Min-sum single machine scheduling problem under algorithms from the Lasserre hierarchy. We prove the first lower bound for this model by showing that the integrality gap is unbounded at level

$\Omega(\sqrt{n})$

even for a variant of the problem that is solvable in

O

(

n

log

n

) time, namely Min-number of tardy 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.