Faster approximation algorithms for packing and covering problems

Daniel Bienstock (danocolumbia.edu)
Garud Iyengar (garudieor.columbia.edu)

Abstract: 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.

Keywords: approximation algorithms, concurrent flows

Category 1: Combinatorial Optimization (Approximation Algorithms )

Category 2: Linear, Cone and Semidefinite Programming (Linear Programming )

Category 3: Convex and Nonsmooth Optimization (Convex Optimization )

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

Download: [PDF]

Entry Submitted: 08/26/2004
Entry Accepted: 08/26/2004
Entry Last Modified: 08/26/2004

Modify/Update this entry