Network design and improvement

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Network design and improvement

Full text

Pdf (162 KB)

Source

ACM Computing Surveys (CSUR) archive
Volume 31 , Issue 3es (September 1999) table of contents

Article No. 2

Year of Publication: 1999

ISSN:0360-0300

Authors

H. Noltemeier	Department of Computer Science, University of Würzburg, Am Hubland, 97074 Würzburg, Germany
H.-C. Wirth	Department of Computer Science, University of Würzburg, Am Hubland, 97074 Würzburg, Germany
S. O. Krumke	Konrad Zuse Zentrum, Takustrasse 7, 14195 Berlin-Dahlem, Germany

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 71, Citation Count: 0

Additional Information:

references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/333580.333581 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	S. Arora, Polynomial time approximation schemes for Euclidean TSP and other geometric problems, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.2, October 14-16, 1996
	2	CHRISTOFIDES, N. Worst-case analysis of a new heuristic for the traveling salesman problem. Tech. rep., Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PA, 1976.
	3	ESWaRAN, K. P., AND TaRJAN, R. E. Augmentation problems. SIAM Journal on Computing 10, 2 (1976), 270-283.
	4	FREDERICKSON, G. N., AND JJtJJt, J. Approximation algorithms for several graph augmentation problems. SIAM Journal on Computing 10, 2 (1981), 270-283.
	5	Greg N. Frederickson , Roberto Solis-Oba, Increasing the weight of minimum spanning trees, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.539-546, January 28-30, 1996, Atlanta, Georgia, United States
	6	Greg N. Frederickson , Roberto Solis-Oba, Efficient algorithms for robustness in matroid optimization, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.659-668, January 05-07, 1997, New Orleans, Louisiana, United States
	7	M. X. Goemans , A. V. Goldberg , S. Plotkin , D. B. Shmoys , É. Tardos , D. P. Williamson, Improved approximation algorithms for network design problems, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.223-232, January 23-25, 1994, Arlington, Virginia, United States
	8	Michel X. Goemans , David P. Williamson, .879-approximation algorithms for MAX CUT and MAX 2SAT, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.422-431, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195216]
	9	Michel X. Goemans , David P. Williamson, A General Approximation Technique for Constrained Forest Problems, SIAM Journal on Computing, v.24 n.2, p.296-317, April 1995 [doi>10.1137/S0097539793242618]
	10	Dorit S. Hochbaum, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
	11	David Karger , Serge Plotkin, Adding multiple cost constraints to combinatorial optimization problems, with applications to multicommodity flows, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.18-25, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225073]
	12	KARPINSKI, M., AND ZELIKOVSKI~ A. New approximation algorithms for Steiner tree problems. Journal of Combinatorial Optimization 1 (1997), 1-19.
	13	KRUMKE, S. O. On the approximability of location and network design problems. PhD thesis, Lehrstuhl fiir Informatik I, Universitgt Wiirzburg, December 1996.
	14	KRUMKE, S. O., MARATHE~ M. V.~ NOLTEMEIER, H., RAVI, R., AND RAVI~ S. S. Network improvement problems. AMS-DIMACS Volume Series on Discrete Mathematics and Theoretical Computer Science: Workshop on Network Design and Location Theory, 1998.
	15	Sven Oliver Krumke , Madhav V. Marathe , Hartmut Noltemeier , R. Ravi , S. S. Ravi , Ravi Sundaram , Hans-Christoph Wirth, Improving Spanning Trees by Upgrading Nodes, Proceedings of the 24th International Colloquium on Automata, Languages and Programming, p.281-291, July 07-11, 1997
	16	KRUMKE, S. O., NOLTEMEIER~ H.~ RAVI~ R.~ SCHWARZ~ S.~ AND WIRTH~ H.-C. Flow iraprovement and flows with fixed costs. In Proceedings of the International Conference of Operations Research Ziirich (0R'98) (1998), Springer. (to appear).
	17	Kay U. Drangmeister , Sven O. Krumke , Madhav V. Marathe , Hartmut Noltemeier , S. S. Ravi, Modifying edges of a network to obtain short subgraphs, Theoretical Computer Science, v.203 n.1, p.91-121, Aug. 6, 1998 [doi>10.1016/S0304-3975(97)00290-9]
	18	Jyh-Han Lin , Jeffrey Scott Vitter, e-approximations with minimum packing constraint violation (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.771-782, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129787]
	19	Joseph S. B. Mitchell, Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems, SIAM Journal on Computing, v.28 n.4, p.1298-1309, Aug. 1999 [doi>10.1137/S0097539796309764]
	20	Cynthia A. Phillips, The network inhibition problem, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.776-785, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167286]
	21	R. Ravi , M. V. Marathe , S. S. Ravi , D. J. Rosenkrantz , H. B. Hunt, III, Many birds with one stone: multi-objective approximation algorithms, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.438-447, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167209]
	22	David B. Shmoys , Éva Tardos , Karen Aardal, Approximation algorithms for facility location problems (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.265-274, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258600]
	23	ZELIKOVSKY, A. Z. A 11/6-approximation for the Steiner problem on networks. Algorithmica 9 (1994), 463-470.