Affordable Access

Approximating the configuration-LP for minimizing weighted sum of completion times on unrelated machines

Authors
Publisher
Springer-Verlag
Publication Date
Disciplines
  • Computer Science
  • Design

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

There are no comments yet on this publication. Be the first to share your thoughts.