Browsing by Author "Magnanti, Thomas L."

Filter results by typing the first few letters
Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Strongly Polynomial Primal-Dual Algorithms for Concave Cost Combinatorial Optimization Problems [Articol]
    (2024) Magnanti, Thomas L.; Stratila, Dan
    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. 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.