2013 | OriginalPaper | Buchkapitel
Approximating the Configuration-LP for Minimizing Weighted Sum of Completion Times on Unrelated Machines
verfasst von : Maxim Sviridenko, Andreas Wiese
Erschienen in: Integer Programming and Combinatorial Optimization
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.