Approximating low-congestion routing and column-restricted packing problems

Authors
Baveja, A Srinivasan, A
Citation
A. Baveja et A. Srinivasan, Approximating low-congestion routing and column-restricted packing problems, INF PROCESS, 74(1-2), 2000, pp. 19-25
Citations number
5
Categorie Soggetti
Information Tecnology & Communication Systems
Journal title
INFORMATION PROCESSING LETTERS
ISSN journal
00200190 → ACNP
Volume
74
Issue
1-2
Year of publication
2000
Pages
19 - 25
Database
ISI
SICI code
0020-0190(20000430)74:1-2<19:ALRACP>2.0.ZU;2-T
Abstract
We contribute to a body of research asserting that the fractional and integ ral optima of column-sparse integer programs are "nearby". This yields impr oved approximation algorithms for some generalizations of the knapsack prob lem, with applications to low-congestion routing in networks, file replicat ion in distributed databases, and other packing problems. (C) 2000 Elsevier Science B.V. All rights reserved.