Paper Info
Title
Approximating low-congestion routing and column-restricted packing problems
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. (C) 2000 Elsevier Science B.V. All rights reserved.
Year
DOI
Venue
2000
10.1016/S0020-0190(00)00033-8
Inf. Process. Lett.
Keywords
Field
DocType
low-congestion routing,column-restricted packing problem,routing,approximation algorithms,knapsack problem,integer programming,algorithms,distributed database
Integer,Approximation algorithm,Mathematical optimization,Combinatorics,Packing problems,Generalization,Hypergraph,Integer programming,Knapsack problem,Distributed database,Mathematics
Journal
Volume
Issue
ISSN
74
1-2
0020-0190
Citations 
PageRank 
References 
4
0.83
2
Authors
2
Name
Order
Citations
PageRank
Alok Baveja112011.99
Aravind Srinivasan23531291.42