Faster approximation algorithms for packing and covering problems

  • Daniel Bienstock
  • Garud Iyengar
    • Categories Approximation Algorithms, Convex Optimization, Linear Programming Tags , Short URL: https://optimization-online.org/?p=9590

    We adapt a method due to Nesterov so as to obtain an algorithm for solving block-angular fractional packing or covering problems to relative tolerance epsilon, while using a number of iterations that grows polynomially in the size of the problem and whose dependency on epsilon is proportional to 1/epsilon.

    Citation

    CORC report TR-2004-09, Computational Optimization Research Center, Columbia University

    Article

    Download

    View Faster approximation algorithms for packing and covering problems