Optimization Online


Strongly Polynomial Primal-Dual Algorithms for Concave Cost Combinatorial Optimization Problems

Thomas L. Magnanti(magnanti***at***mit.edu)
Dan Stratila(dstrat***at***rci.rutgers.edu)

Abstract: We introduce an algorithm design technique for a class of combinatorial optimization problems with concave costs. This technique yields a strongly polynomial primal-dual algorithm for a concave cost problem whenever such an algorithm exists for the fixed-charge counterpart of the problem. For many practical concave cost problems, the fixed-charge counterpart is a well-studied 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.61-approximation algorithm for the concave cost facility location problem. For inventory problems, we obtain a new exact algorithm for the economic lot-sizing problem with general concave ordering costs, and a 4-approximation algorithm for the joint replenishment problem with general concave individual ordering costs.


Category 1: Combinatorial Optimization

Category 2: Applications -- OR and Management Sciences (Supply Chain Management )


Download: [PDF]

Entry Submitted: 02/13/2012
Entry Accepted: 02/13/2012
Entry Last Modified: 02/13/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society