Minimizing the sum of weighted completion times in a concurrent open shop

We study minimizing the sum of weighted completion times in a concurrent open shop. We give a primal–dual 2-approximation algorithm for this problem. We also show that several natural linear programming relaxations for this problem have an integrality gap of 2. Finally, we show that this problem is...

Full description

Saved in:
Bibliographic Details
Published in:Operations research letters 2010-09, Vol.38 (5), p.390-395
Main Authors: Mastrolilli, Monaldo, Queyranne, Maurice, Schulz, Andreas S., Svensson, Ola, Uhan, Nelson A.
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Approximation algorithm
Completion time
Exact sciences and technology
Flows in networks. Combinatorial problems
Games
Hardness of approximation
Integrality gap
Linear programming
Mathematical programming
Operational research and scientific management
Operational research. Management science
Operations research
Scheduling
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We study minimizing the sum of weighted completion times in a concurrent open shop. We give a primal–dual 2-approximation algorithm for this problem. We also show that several natural linear programming relaxations for this problem have an integrality gap of 2. Finally, we show that this problem is inapproximable within a factor strictly less than 6/5 if P ≠ NP , or strictly less than 4/3 if the Unique Games Conjecture also holds.
ISSN:0167-6377
1872-7468
1872-7468
DOI:10.1016/j.orl.2010.04.011