Sviridenko, Maxim; Wiese, Andreas Approximating the configuration-LP for minimizing weighted sum of completion times on unrelated machines. (English) Zbl 1377.90034 Goemans, Michel (ed.) et al., Integer programming and combinatorial optimization. 16th international conference, IPCO 2013, Valparaíso, Chile, March 18–20, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-36693-2/pbk). Lecture Notes in Computer Science 7801, 387-398 (2013). Summary: 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}| \sum w_j C_j\) and a fully polynomial time approximation scheme to solve a relaxation of \(R \| \sum 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.For the entire collection see [Zbl 1258.90003]. Cited in 4 Documents MSC: 90B35 Deterministic scheduling theory in operations research 68W25 Approximation algorithms 90C05 Linear programming PDFBibTeX XMLCite \textit{M. Sviridenko} and \textit{A. Wiese}, Lect. Notes Comput. Sci. 7801, 387--398 (2013; Zbl 1377.90034) Full Text: DOI