The Library
Approximating the configuration-LP for minimizing weighted sum of completion times on unrelated machines
Tools
Sviridenko, Maxim and Wiese, Andreas (2013) Approximating the configuration-LP for minimizing weighted sum of completion times on unrelated machines. In: Goemans, Michel and Correa, Jose, (eds.) Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science, 7801 . Berlin Heidelberg: Springer-Verlag, pp. 387-398. ISBN 9783642366932
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1007/978-3-642-36694-9_33
Abstract
Configuration-LPs have proved to be successful in the design and analysis of approximation algorithms for a variety of discrete optimization problems. In addition, lower bounds based on configuration-LPs are a tool of choice for many practitioners especially those solving transportation and bin packing problems. In this work we initiate a study of linear programming relaxations with exponential number of variables for unrelated parallel machine scheduling problems with total weighted sum of completion times objective. We design a polynomial time approximation scheme to solve such a relaxation for R|r ij | ∑ w j C j and a fully polynomial time approximation scheme to solve a relaxation of R|| ∑ w j C j . As a byproduct of our techniques we derive a polynomial time approximation scheme for the one machine scheduling problem with rejection penalties, release dates and the total weighted sum of completion times objective
Item Type: | Book Item | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Series Name: | Lecture Notes in Computer Science | ||||
Publisher: | Springer-Verlag | ||||
Place of Publication: | Berlin Heidelberg | ||||
ISBN: | 9783642366932 | ||||
ISSN: | 0302-9743 | ||||
Book Title: | Integer Programming and Combinatorial Optimization | ||||
Editor: | Goemans, Michel and Correa, Jose | ||||
Official Date: | 2013 | ||||
Dates: |
|
||||
Volume: | 7801 | ||||
Page Range: | pp. 387-398 | ||||
DOI: | 10.1007/978-3-642-36694-9_33 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Description: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |