Thomas L. Magnanti

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

  • Thomas L. Magnanti
  • Dan Stratila
    • Categories Combinatorial Optimization, Supply Chain Management

    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 … Read more

    Separable Concave Optimization Approximately Equals Piecewise-Linear Optimization

  • Thomas L. Magnanti
  • Dan Stratila
    • Categories Combinatorial Optimization, Network Optimization

    We study the problem of minimizing a nonnegative separable concave function over a compact feasible set. We approximate this problem to within a factor of 1+epsilon by a piecewise-linear minimization problem over the same feasible set. Our main result is that when the feasible set is a polyhedron, the number of resulting pieces is polynomial … Read more