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

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

2012-02-13

arxiv.org/abs/1202.2654v1

Mathematics

Optimization and Control

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Strongly Polynomial Primal-Dual Algorithms for Concave Cost Combinatorial Optimization Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Strongly Polynomial Primal-Dual Algorithms for Concave Cost Combinatorial Optimization Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Strongly Polynomial Primal-Dual Algorithms for Concave Cost Combinatorial Optimization Problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-681352