Abstract
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 logn) 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.
Supported by the Swiss National Science Foundation project 200020-144491/1 “Approximation Algorithms for Machine Scheduling Through Theory and Experiments”.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bansal, N., Pruhs, K.: The geometry of scheduling. In: FOCS, pp. 407–414 (2010)
Barak, B., Chan, S.O., Kothari, P.: Sum of squares lower bounds from pairwise independence. In: STOC (2015)
Bhaskara, A., Charikar, M., Vijayaraghavan, A., Guruswami, V., Zhou, Y.: Polynomial integrality gaps for strong sdp relaxations of densest k-subgraph. In: SODA, pp. 388–405 (2012)
Carr, R.D., Fleischer, L., Leung, V.J., Phillips, C.A.: Strengthening integrality gaps for capacitated network design and covering problems. In: SODA, pp. 106–115 (2000)
Cheung, M., Shmoys, D.B.: A primal-dual approximation algorithm for min-sum single-machine scheduling problems. In: Goldberg, L.A., Jansen, K., Ravi, R., Rolim, J.D.P. (eds.) RANDOM 2011 and APPROX 2011. LNCS, vol. 6845, pp. 135–146. Springer, Heidelberg (2011)
Chlamtac, E., Tulsiani, M.: Convex relaxations and integrality gaps. In: Handbook on Semidefinite, Conic and Polynomial Optimization. Springer (to appear)
Fawzi, H., Saunderson, J., Parrilo, P.: Sparse sum-of-squares certificates on finite abelian groups. CoRR, abs/1503.01207 (2015)
Grigoriev, D.: Complexity of positivstellensatz proofs for the knapsack. Computational Complexity 10(2), 139–154 (2001)
Grigoriev, D.: Linear lower bound on degrees of positivstellensatz calculus proofs for the parity. Theoretical Computer Science 259(1-2), 613–622 (2001)
Karlin, A.R., Mathieu, C., Nguyen, C.T.: Integrality gaps of linear and semi-definite programming relaxations for knapsack. In: Günlük, O., Woeginger, G.J. (eds.) IPCO 2011. LNCS, vol. 6655, pp. 301–314. Springer, Heidelberg (2011)
Karp, R.M.: Reducibility among combinatorial problems. In: Proceedings of a symposium on the Complexity of Computer Computations, March 20-22, pp. 85–103. Thomas J. Watson Research Center, Yorktown Heights (1972)
Kurpisz, A., Leppänen, S., Mastrolilli, M.: On the hardest problem formulations for the 0/1 Lasserre hierarchy. In: Halldórsson, M M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015. LNCS, vol. 9134, pp. 872–885. Springer, Heidelberg (2015)
Lasserre, J.B.: Global optimization with polynomials and the problem of moments. SIAM Journal on Optimization 11(3), 796–817 (2001)
Laurent, M.: A comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre relaxations for 0-1 programming. Mathematics of Operations Research 28(3), 470–496 (2003)
Meka, R., Potechin, A., Wigderson, A.: Sum-of-squares lower bounds for planted clique. CoRR, abs/1503.06447. In: STOC 2015 (2015) (to appear)
Mestre, J., Verschae, J.: A 4-approximation for scheduling on a single machine with general cost function. CoRR, abs/1403.0298 (2014)
Moore, M.J.: An n job, one machine sequencing algorithm for minimizing the number of late jobs. Management Science 15, 102–109 (1968)
O’Donnell, R., Zhou, Y.: Approximability and proof complexity. In: Khanna, S. (ed.) SODA, pp. 1537–1556. SIAM (2013)
Parrilo, P.: Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization. PhD thesis, California Institute of Technology (2000)
Rothvoß, T.: The lasserre hierarchy in approximation algorithms. Lecture Notes for the MAPSP 2013 - Tutorial (June 2013)
Schoenebeck, G.: Linear level Lasserre lower bounds for certain k-csps. In: FOCS, pp. 593–602 (2008)
Shor, N.: Class of global minimum bounds of polynomial functions. Cybernetics 23(6), 731–734 (1987)
Tulsiani, M.: Csp gaps and reductions in the Lasserre hierarchy. In: STOC, pp. 303–312 (2009)
Wolsey, L.A.: Facets for a linear inequality in 0–1 variables. Mathematical Programming 8, 168–175 (1975)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kurpisz, A., Leppänen, S., Mastrolilli, M. (2015). A Lasserre Lower Bound for the Min-Sum Single Machine Scheduling Problem. In: Bansal, N., Finocchi, I. (eds) Algorithms - ESA 2015. Lecture Notes in Computer Science(), vol 9294. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-48350-3_71
Download citation
DOI: https://doi.org/10.1007/978-3-662-48350-3_71
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-48349-7
Online ISBN: 978-3-662-48350-3
eBook Packages: Computer ScienceComputer Science (R0)