  


Strongly Polynomial PrimalDual Algorithms for Concave Cost Combinatorial Optimization Problems
Thomas L. Magnanti(magnantimit.edu) Abstract: We introduce an algorithm design technique for a class of combinatorial optimization problems with concave costs. This technique yields a strongly polynomial primaldual algorithm for a concave cost problem whenever such an algorithm exists for the fixedcharge counterpart of the problem. For many practical concave cost problems, the fixedcharge counterpart is a wellstudied combinatorial optimization problem. Our technique preserves constant factor approximation ratios, as well as ratios that depend only on certain problem parameters, and exact algorithms yield exact algorithms. Using our technique, we obtain a new 1.61approximation algorithm for the concave cost facility location problem. For inventory problems, we obtain a new exact algorithm for the economic lotsizing problem with general concave ordering costs, and a 4approximation algorithm for the joint replenishment problem with general concave individual ordering costs. Keywords: Category 1: Combinatorial Optimization Category 2: Applications  OR and Management Sciences (Supply Chain Management ) Citation: Download: [PDF] Entry Submitted: 02/13/2012 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  