- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- BIRS Workshop Lecture Videos /
- A Lasserre Lower Bound for the Min-Sum Single Machine...
Open Collections
BIRS Workshop Lecture Videos
BIRS Workshop Lecture Videos
A Lasserre Lower Bound for the Min-Sum Single Machine Scheduling Problem Mastrolilli, Palmo Monaldo
Description
The Min-sum single machine scheduling problem (denoted 1jjPfj) 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 (pn) even for a variant of the problem that is solvable in O(n log n) time by the Moore-Hodgson algorithm, 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. Joint work with Adam Kurpisz and Samuli Leppanen.
Item Metadata
Title |
A Lasserre Lower Bound for the Min-Sum Single Machine Scheduling Problem
|
Creator | |
Publisher |
Banff International Research Station for Mathematical Innovation and Discovery
|
Date Issued |
2015-12-01T11:19
|
Description |
The Min-sum single machine scheduling problem (denoted 1jjPfj) 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 (pn) even for a variant of the problem that is solvable in O(n log n) time by the Moore-Hodgson algorithm, 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. Joint work with Adam Kurpisz and Samuli Leppanen.
|
Extent |
36 minutes
|
Subject | |
Type | |
File Format |
video/mp4
|
Language |
eng
|
Notes |
Author affiliation: IDSIA Instituto Dalle Molle di Studi sull'Intelligenza Artificiale
|
Series | |
Date Available |
2016-06-07
|
Provider |
Vancouver : University of British Columbia Library
|
Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
DOI |
10.14288/1.0304576
|
URI | |
Affiliation | |
Peer Review Status |
Unreviewed
|
Scholarly Level |
Faculty
|
Rights URI | |
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International