Approximating low-congestion routing and column-restricted packing problems

TitleApproximating low-congestion routing and column-restricted packing problems
Publication TypeJournal Articles
Year of Publication2000
AuthorsBaveja A, Srinivasan A
JournalInformation Processing Letters
Volume74
Issue1–2
Pagination19 - 25
Date Published2000/04//
ISBN Number0020-0190
Keywordsalgorithms, Approximation algorithms, integer programming, Packing, Routing
Abstract

We contribute to a body of research asserting that the fractional and integral optima of column-sparse integer programs are “nearby”. This yields improved approximation algorithms for some generalizations of the knapsack problem, with applications to low-congestion routing in networks, file replication in distributed databases, and other packing problems.
URLhttp://www.sciencedirect.com/science/article/pii/S0020019000000338
DOI10.1016/S0020-0190(00)00033-8