Advertisement
Published in:
2013 | OriginalPaper | Chapter
Approximating the Configuration-LP for Minimizing Weighted Sum of Completion Times on Unrelated Machines
Authors : Maxim Sviridenko, Andreas Wiese
Published in: Integer Programming and Combinatorial Optimization
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.