  


Minimizing the sum of weighted completion times in a concurrent open shop
Monaldo Mastrolilli (monaldoidsia.ch) Abstract: We study minimizing the sum of weighted completion times in a concurrent open shop. We give a primaldual 2approximation 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 \ne NP, or strictly less than 4/3 if the Unique Games Conjecture also holds. Keywords: scheduling, integrality gap, approximation algorithms, hardness of approximation Category 1: Combinatorial Optimization (Approximation Algorithms ) Category 2: Integer Programming ((Mixed) Integer Linear Programming ) Category 3: Applications  OR and Management Sciences (Scheduling ) Citation: Operations Research Letters, to appear. doi:10.1016/j.orl.2010.04.011 Download: Entry Submitted: 11/11/2008 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  