Many birds with one stone

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Many birds with one stone: multi-objective approximation algorithms

Full text

Pdf (1.02 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing table of contents

San Diego, California, United States

Pages: 438 - 447

Year of Publication: 1993

ISBN:0-89791-591-7

Authors

R. Ravi
M. V. Marathe
S. S. Ravi
D. J. Rosenkrantz
H. B. Hunt, III

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 39, Citation Count: 19

Additional Information:

references cited by 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/167088.167209 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	Ajit Agrawal , Philip Klein , R. Ravi, When trees collide: an approximation algorithm for the generalized Steiner problem on networks, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.134-144, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103437]
	2	A. Agrawal, P. Klein, and R. Ravi, "Near-optimal nested dissection," submitted to SIAM Y. on Computing. A preliminary version appeared as P. Klein, A. Agrawal, R. Ravi, and S. Rao, "Approximation through multicommodity flow," in Proc. 31th Annual IEEE FOCS (1990), pp. 726-737.
	3	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	4	J. Bar-Ilan and D. Peleg, "Approximation algorithms for selecting network centers (Preliminary version)," LNGS 519, Proceedings, #nd Workshop, WADS '91, Algorithms and Data Structures series, Springer- Verlag, pp. 343-354.
	5	C. W. Duin and A. Volgenant, "Some generalizations of the Steiner problem in graphs," Networks, 17, pp. sss-s64, (198r).
	6	J. Edmonds and E. L. Johnson, "Matching, Euler tours and the Chinese postman", Math. Protl. 5, (1973), pp. 88-124.
	7	M. F6rer and B. Raghavachari, "An A/'C approximation algorithm for the minimum degree spanning tree problem," Proc., #Sth Annual Allerton Conference (1990), pp. 274-281.
	8	Martin Fürer , Balaji Raghavachari, Approximating the minimum degree spanning tree to within one from the optimal degree, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.317-324, September 1992, Orlando, Florida, United States
	9	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	10	Michel X. Goemans , David P. Williamson, A general approximation technique for constrained forest problems, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.307-316, September 1992, Orlando, Florida, United States
	11	Dorit S. Hochbaum , David B. Shmoys, A unified approach to approximation algorithms for bottleneck problems, Journal of the ACM (JACM), v.33 n.3, p.533-550, July 1986 [doi>10.1145/5925.5933]
	12	F. K. tiwang and D. S. Richards, "Steiner tree problems," Networks, Vol. 22, No. 1, pp. 55-90 (1992).
	13	A. Iwainsky, E. Canuto, O. Taraszow, and A. Villa, "Network decomposition for the optimization of connection structures," Networks, 16, pp. 205-235, (1986).
	14	Samir Khuller , Balaji Raghavachari , Neal Young, Balancing minimum spanning and shortest path trees, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.243-250, January 25-27, 1993, Austin, Texas, United States
	15	P. Klein and R. Ravi, "A nearly best-possible approximation for node-weighted Steiner trees," to appear in Proc., IPCO III (1993).
	16	F. T. Leighton and S. Rax#, "An approximate maxflow min-cut theorem for uniform multicommodity flow problems with application to approximation algorithms," Proc., 29th Annual IEEE FOCS (1988), pp. 422-431.
	17	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]
	18	L. Lov#sz and M. D. Plummer, Matching theor$t, Akad#miai Kind6, Budapest (1986).
	19	Carsten Lund , Mihalis Yannakakis, On the hardness of approximating minimization problems, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.286-293, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167172]
	20	J. S. B. Mitchell, C. Piatko, and E. M. Arkin, "Computing a shortest k-link path in a polygon", Proco, 33rd Annual IEEE FOCS (1992), pp. 573-582.
	21	R. G. Parker and R. L. Rardin, "Guaranteed performance heuristic for the bottleneck traveling salesman problem," Oper. Res. Left. 6, pp. 269-272, (1982).
	22	R. Ravi , Balaji Raghavachari , Philip N. Klein, Approximation Through Local Optimality: Designing Networks with Small Degree, Proceedings of the 12th Conference on Foundations of Software Technology and Theoretical Computer Science, p.279-290, December 18-20, 1992
	23	D. J. Rosenkrantz, R. E. Stearns and P. M. Lewis II, "An analysis of several heuristics for the traveling salesman problem," SIAM J. Computing, 6(3), pp. 563-581, 1977.
	24	David B. Shmoys , Éva Tardos, Scheduling unrelated machines with costs, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.448-454, January 25-27, 1993, Austin, Texas, United States
	25	Pawel Winter, Generalized Steiner problem in outerplanar networks, BIT, v.25 n.3, p.485-496, 1985 [doi>10.1007/BF01935369]

CITED BY 19

	J. Könemann , R. Ravi, A matter of degree: improved approximation algorithms for degree-bounded minimum spanning trees, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.537-546, May 21-23, 2000, Portland, Oregon, United States
	Samir Khuller , Balaji Raghavachari , Neal Young, Low degree spanning trees of small weight, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.412-421, May 23-25, 1994, Montreal, Quebec, Canada
	Yevgeniy Dodis , Sanjeev Khanna, Design networks with bounded pairwise distance, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.750-759, May 01-04, 1999, Atlanta, Georgia, United States
	Sherlia Y. Shi , Jonathan S. Turner , Marcel Waldvogel, Dimensioning server access bandwidth and multicast routing in overlay networks, Proceedings of the 11th international workshop on Network and operating systems support for digital audio and video, p.83-91, January 2001, Port Jefferson, New York, United States
	Aravind Srinivasan , Chung-Piaw Teo, A constant-factor approximation algorithm for packet routing, and balancing local vs. global criteria, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.636-643, May 04-06, 1997, El Paso, Texas, United States
	Guy Kortsarz , David Peleg, Approximating shallow-light trees, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.103-110, January 05-07, 1997, New Orleans, Louisiana, United States
	H. Noltemeier , H.-C. Wirth , S. O. Krumke, Network design and improvement, ACM Computing Surveys (CSUR), v.31 n.3es, Sept. 1999
	Jochen Könemann , R. Ravi, Primal-dual meets local search: approximating MST's with nonuniform degree bounds, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Sergei Vassilvitskii , Mihalis Yannakakis, Efficiently computing succinct trade-off curves, Theoretical Computer Science, v.348 n.2, p.334-356, 8 December 2005
	Thang N. Bui , Catherine M. Zrncic, An ant-based algorithm for finding degree-constrained minimum spanning tree, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA
	Rafael Andrade , Abilio Lucena , Nelson Maculan, Using Lagrangian dual information to generate degree constrained spanning trees, Discrete Applied Mathematics, v.154 n.5, p.703-717, 1 April 2006
	Michael Elkin , Guy Kortsarz, Sublogarithmic approximation for telephone multicast, Journal of Computer and System Sciences, v.72 n.4, p.648-659, June 2006
	Hongju Cheng , Qin Liu , Xiaohua Jia, Heuristic algorithms for real-time data aggregation in wireless sensor networks, Proceeding of the 2006 international conference on Communications and mobile computing, July 03-06, 2006, Vancouver, British Columbia, Canada
	Michele Flammini , Gaia Nicosia, Competitive algorithms for the bicriteria k-server problem, Discrete Applied Mathematics, v.154 n.15, p.2117-2127, 1 October 2006
	Mohit Singh , Lap Chi Lau, Approximating minimum bounded degree spanning trees to within one of optimal, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Lap Chi Lau , Joseph (Seffi) Naor , Mohammad R. Salavatipour , Mohit Singh, Survivable network design with degree or order constraints, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Nikhil Bansal , Rohit Khandekar , Viswanath Nagarajan, Additive guarantees for degree bounded directed network design, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Mohammad Ghodsi , Hamid Mahini , Kian Mirjalali , Shayan Oveis Gharan , Amin S. Sayedi R. , Morteza Zadimoghaddam, Spanning trees with minimum weighted degrees, Information Processing Letters, v.104 n.3, p.113-116, October, 2007
	Peter Korteweg , Alberto Marchetti-Spaccamela , Leen Stougie , Andrea Vitaletti, Data aggregation in sensor networks: Balancing communication and delay costs, Theoretical Computer Science, v.410 n.14, p.1346-1354, March, 2009