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.

Statistics

Seen <100 times
0 Comments

More articles like this

Minimizing the sum of weighted completion times in...

on Operations Research Letters Jan 01, 2010

Minimizing the sum of job completion times on capa...

on Mathematical and Computer Mode... Jan 01, 1994

A note on minimizing the sum of quadratic completi...

on Information Processing Letters Oct 15, 2012

Minimizing the sum of job completion times on capa...

on European Journal of Operationa... Jan 01, 2009
More articles like this..