Approximating the Configuration-LP for Minimizing Weighted Sum of Completion 
Times on Unrelated Machines

Sviridenko, Maxim; Wiese, Andreas

doi:10.1007/978-3-642-36694-9_33

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Conference Paper

Approximating the Configuration-LP for Minimizing Weighted Sum of Completion Times on Unrelated Machines

MPS-Authors

/persons/resource/persons45742

Wiese, Andreas
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

Sviridenko, M., & Wiese, A. (2013). Approximating the Configuration-LP for Minimizing Weighted Sum of Completion Times on Unrelated Machines. In M. Goemans, & J. Correa (Eds.), Integer Programming and Combinatorial Optimization (pp. 387-398). Berlin: Springer. doi:10.1007/978-3-642-36694-9_33.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0015-3E9E-D

Abstract

Configuration LP's have proved to be successful in the design and analysis of approximation algorithms for a variety of discrete optimization problem. In addition, lower bounds based on configuration LP's are a tool of choice for many practitioners especially those solving transportation 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|\sum w_jC_j and fully polynomial time approximation scheme to solve a relaxation of R||\sum w_jC_j.