MPI-INF Logo
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, Micheldblp
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:
Note, Abstract, ©
(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},
ADDRESS = {Valparaíso, Chile},
ISBN = {978-3-642-36693-2},
}


Entry last modified by Stephanie Müller, 02/17/2014
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]
Created
12/13/2012 10:37:09 AM
Revisions
9.
8.
7.
6.
5.
Editor(s)
Stephanie Müller
Stephanie Müller
Stephanie Müller
Andreas Wiese
Andreas Wiese
Edit Dates
06.02.2013 09:40:02
04.02.2013 15:57:57
04.02.2013 15:56:07
12/13/2012 10:56:28 AM
12/13/2012 10:47:10 AM