@article {17555, title = {Approximating low-congestion routing and column-restricted packing problems}, journal = {Information Processing Letters}, volume = {74}, year = {2000}, month = {2000/04//}, pages = {19 - 25}, abstract = {We contribute to a body of research asserting that the fractional and integral optima of column-sparse integer programs are {\textquotedblleft}nearby{\textquotedblright}. 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.}, keywords = {algorithms, Approximation algorithms, integer programming, Packing, Routing}, isbn = {0020-0190}, doi = {10.1016/S0020-0190(00)00033-8}, url = {http://www.sciencedirect.com/science/article/pii/S0020019000000338}, author = {Baveja,Alok and Srinivasan, Aravind} }