Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




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

URL of the conference:

http://ipco2013.dim.uchile.cl/index.html

URL for downloading the paper:


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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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