Improving on the 1.5-approximation of a smallest 2-edge connected spanningsubgraph

Authors
Cheriyan, J Sebo, A Szigeti, Z
Citation
J. Cheriyan et al., Improving on the 1.5-approximation of a smallest 2-edge connected spanningsubgraph, SIAM J DISC, 14(2), 2001, pp. 170-180
Citations number
18
Categorie Soggetti
Engineering Mathematics
Journal title
SIAM JOURNAL ON DISCRETE MATHEMATICS
ISSN journal
08954801 → ACNP
Volume
14
Issue
2
Year of publication
2001
Pages
170 - 180
Database
ISI
SICI code
0895-4801(2001)14:2<170:IOT1OA>2.0.ZU;2-6
Abstract
We give a 17/12-approximation algorithm for the following NP-hard problem: Given a simple undirected graph, find a 2-edge connected spanning subgraph that has the minimum number of edges. The best previous approximation guarantee was 3/2. If the well-known 4/3 co njecture for the metric traveling salesman problem holds, then the optimal value ( minimum number of edges) is at most 4/3 times the optimal value of a linear programming relaxation. Thus our main result gets halfway to this target.