Browsing by Author "Magnanti, Thomas L."
Now showing 1 - 1 of 1
- Results Per Page
- Sort Options
Item Strongly Polynomial Primal-Dual Algorithms for Concave Cost Combinatorial Optimization Problems [Articol](2024) Magnanti, Thomas L.; Stratila, DanWe 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. Using our technique, we obtain a 1.61-approximation algorithm for the concave cost facility location problem, an exact algorithm for the concave cost lot-sizing problem, and a 4-approximation algorithm for the joint replenishment problem with general concave individual ordering costs.