Title	Estimating The Makespan of The Two-Valued Restricted Assignment Problem
Creator	Land, Kati
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	Mathematics; Computer science; Combinatorics; Theoretical computer science
Type	Moving Image
File Format	video/mp4
Language	eng
Notes	Author affiliation: Christian-Albrechts-Universität zu Kiel
Series	BIRS Workshop Lecture Videos (Banff, Alta)
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	http://hdl.handle.net/2429/58236
Affiliation	Non UBC
Peer Review Status	Unreviewed
Scholarly Level	Graduate
Rights URI	http://creativecommons.org/licenses/by-nc-nd/4.0/
Aggregated Source Repository	DSpace

Open Collections

BIRS Workshop Lecture Videos