English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  Approximating the Configuration-LP for Minimizing Weighted Sum of Completion Times on Unrelated Machines

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.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0015-3E9E-D Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0024-9CB3-3
Genre: Conference Paper
Latex : Approximating the Configuration-{LP} for Minimizing Weighted Sum of Completion Times on Unrelated Machines

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Sviridenko, Maxim1, Author
Wiese, Andreas2, Author           
Affiliations:
1External Organizations, ou_persistent22              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 20132013
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: DOI: 10.1007/978-3-642-36694-9_33
BibTex Citekey: SviridenkoWiese2013
Other: Local-ID: 56F6AEF322B11592C1257AD30034D756-SviridenkoWiese2013
 Degree: -

Event

show
hide
Title: 16th International Conference on Integer Programming and Combinatorial Optimization
Place of Event: Valparaíso, Chile
Start-/End Date: 2013-03-18 - 2013-03-20

Legal Case

show

Project information

show

Source 1

show
hide
Title: Integer Programming and Combinatorial Optimization
  Abbreviation : IPCO 2013
  Subtitle : 16th International Conference, IPCO 2013, Valparaíso, Chile, March 18-20, 2013. Proceedings
Source Genre: Proceedings
 Creator(s):
Goemans, Michel1, Editor
Correa, José1, Editor
Affiliations:
1 External Organizations, ou_persistent22            
Publ. Info: Berlin : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 387 - 398 Identifier: ISBN: 978-3-642-36693-2

Source 2

show
hide
Title: Lecture Notes in Computer Science
  Abbreviation : LNCS
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 7801 Sequence Number: - Start / End Page: - Identifier: ISSN: 0302-9743