Publications

### Server    domino.mpi-inf.mpg.de

 Proceedings Article, Paper @InProceedings Beitrag in Tagungsband, Workshop
 Author, Editor
 Author(s): Sviridenko, Maxim Wiese, Andreas dblp dblp Not MPG Author(s): Sviridenko, Maxim
 Editor(s): Goemans, Michel dblp Not MPII Editor(s): Goemans, Michel
 BibTeX cite key*: SviridenkoWiese2013
 Title, Booktitle
 Title*: Approximating the Configuration-LP for Minimizing Weighted Sum of Completion Times on Unrelated Machines Booktitle*: Proceedings of the 16th Conference on Integer Programming and Combinatorial Optimization (IPCO 2013)
 Event, URLs
 Conference URL:: http://ipco2013.dim.uchile.cl/index.html Downloading URL: Event Address*: Valparaíso, Chile Language: English Event Date* (no longer used): Organization: Event Start Date: 18 March 2013 Event End Date: 20 March 2013
 Publisher
 Name*: Springer URL: http://www.springer.com Address*: Heidelberg Type:
 Vol, No, Year, pp.
 Series: Lecture Notes in Computer Science
 Volume: 7801 Number: Month: Pages: Year*: 2013 VG Wort Pages: ISBN/ISSN: 978-3-642-36693-2 Sequence Number: DOI:
 (LaTeX) 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$. Download Access Level: Internal

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@INPROCEEDINGS{SviridenkoWiese2013,
AUTHOR = {Sviridenko, Maxim and Wiese, Andreas},
EDITOR = {Goemans, Michel},
TITLE = {Approximating the Configuration-{LP} for Minimizing Weighted Sum of Completion Times on Unrelated Machines},
BOOKTITLE = {Proceedings of the 16th Conference on Integer Programming and Combinatorial Optimization (IPCO 2013)},
PUBLISHER = {Springer},
YEAR = {2013},
VOLUME = {7801},
SERIES = {Lecture Notes in Computer Science},