- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- BIRS Workshop Lecture Videos /
- Estimating The Makespan of The Two-Valued Restricted...
Open Collections
BIRS Workshop Lecture Videos
BIRS Workshop Lecture Videos
Estimating The Makespan of The Two-Valued Restricted Assignment Problem Land, Kati
Description
We consider a special case of the scheduling problem on unrelated machines, namely the Restricted Assignment Problem with two diifferent processing times. We show that the configuration LP has an integrality gap of at most 5=3 1:667 for this problem. This allows us to estimate the optimal makespan within a factor of 5/3 , improving upon the previously best known estimation algorithm with ratio 11=6 1:833 due to Chakrabarty, Khanna, and Li. This is joint work with Klaus Jansen and Marten Maack.
Item Metadata
Title |
Estimating The Makespan of The Two-Valued Restricted Assignment Problem
|
Creator | |
Publisher |
Banff International Research Station for Mathematical Innovation and Discovery
|
Date Issued |
2015-12-01T10:59
|
Description |
We consider a special case of the scheduling problem on unrelated machines, namely the Restricted Assignment Problem with two diifferent processing times. We show that the configuration LP has an integrality gap of at most 5=3 1:667 for this problem. This allows us to estimate the optimal makespan within a factor of 5/3 , improving upon the previously best known estimation algorithm with ratio 11=6 1:833 due to Chakrabarty, Khanna, and Li. This is joint work with Klaus Jansen and Marten Maack.
|
Extent |
19 minutes
|
Subject | |
Type | |
File Format |
video/mp4
|
Language |
eng
|
Notes |
Author affiliation: Christian-Albrechts-Universität zu Kiel
|
Series | |
Date Available |
2016-06-07
|
Provider |
Vancouver : University of British Columbia Library
|
Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
DOI |
10.14288/1.0304575
|
URI | |
Affiliation | |
Peer Review Status |
Unreviewed
|
Scholarly Level |
Graduate
|
Rights URI | |
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International