| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 1141635 | Discrete Optimization | 2013 | 17 Pages |
Abstract
Jain’s iterative rounding method and its variants give the best approximation guarantees known for many problems in the area of network design. The method has been applied to the mincost kk-connected spanning subgraph problem. We construct a family of examples such that the standard LP relaxation has an extreme-point solution with infinity norm ≤Θ(1)/k, thus showing that the standard iterative rounding method cannot achieve an approximation guarantee better than Ω(k).
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Control and Optimization
Authors
Ashkan Aazami, Joseph Cheriyan, Bundit Laekhanukit,