NDLI: A General Approximation Technique for Constrained Forest Problems

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Williamson, David P. Goemans, Michel X.
Copyright Year	1995
Abstract	We present a general approximation technique for a large class of graph problems. Our technique mostly applies to problems of covering, at minimum cost, the vertices of a graph with trees, cycles, or paths satisfying certain requirements. In particular, many basic combinatorial optimization problems fit in this framework, including the shortest path, minimum-cost spanning tree, minimum-weight perfect matching, traveling salesman, and Steiner tree problems.Our technique produces approximation algorithms that run in $O(n^{2} \log n)$ time and come within a factor of 2 of optimal for most of these problems. For instance, we obtain a 2-approximation algorithm for the minimum-weight perfect matching problem under the triangle inequality. Our running time of $O(n^{2} \log n)$ time compares favorably with the best strongly polynomial exact algorithms running in $O(n^{3})$ time for dense graphs. A similar result is obtained for the 2-matching problem and its variants. We also derive the first approximation algorithms for many NP-complete problems, including the nonfixed point-to-point connection problem, the exact path partitioning problem, and complex location-design problems. Moreover, for the prize-collecting traveling salesman or Steiner tree problems, we obtain 2-approximation algorithms, therefore improving the previously best-known performance guarantees of 2.5 and 3, respectively [Math. Programming, 59 (1993), pp. 4134201.
Starting Page	296
Ending Page	317
Page Count	22
File Format	PDF
ISSN	00975397
DOI	10.1137/S0097539793242618
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	2
Volume Number	24
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2006-07-31
Access Restriction	Subscribed
Subject Keyword	combinatorial optimization Analysis of algorithms and problem complexity traveling salesman problem T -joins approximation algorithms Steiner tree problem Combinatorial optimization matching
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in