The minimum latency problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The minimum latency problem

Full text

Pdf (723 KB)

Source

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

Montreal, Quebec, Canada

Pages: 163 - 171

Year of Publication: 1994

ISBN:0-89791-663-8

Authors

Avrim Blum	School of Computer Science, CMU
Prasad Chalasani	School of Computer Science, CMU
Don Coppersmith	IBM T.J. Watson Research Center
Bill Pulleyblank	IBM T.J. Watson Research Center
Prabhakar Raghavan	IBM T.J. Watson Research Center
Madhu Sudan	IBM T.J. Watson Research Center

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): 48, Citation Count: 28

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/195058.195125 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	F. Afrati, S. Cosmadakis, C. Papadimitriou, G. Papageorgiou, N. Papakostantinou. The Complexity of the Traveling Repairman Problem. informatique Theorique et Applications (Theoretical Informatics and Applications}, Vol. 20, No. 1, pages 79-87, 1986. ALMSS
	2	S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and the intractability of approximation problems. In Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science, pages 14-23, 1992.
	3	R. Baeza-Yates, J. Culberson and G.J. Rawlins. Searching with Uncertainty. To appear in Information and Computation.
	4	Daniel Bienstock , Michel X. Goemans , David Simchi-Levi , David Williamson, A note on the prize collecting traveling salesman problem, Mathematical Programming: Series A and B, v.59 n.3, p.413-420, May 7, 1993 [doi>10.1007/BF01581256]
	5	L. Bianco, A. Mingozzi and S. Ricciardelli. The traveling salesman problem with cumulative costs Networks, vol.23, no.2, pages 81-91, March 1993.
	6	Naveen Garg , Dorit S. Hochbaum, An O(log k) approximation algorithm for the k minimum spanning tree problem in the plane, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.432-438, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195218]
	7	M. Goemans and :I. Kleinberg. Personal Communication. 1994.
	8	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
	9	A. Lucena. Time-dependent traveling salesman problem- the deliveryman case. Networks, vol.20, no.6, pages 753-763, October 1990.
	10	Edward Minieka, The delivery man problem on a tree network, Annals of Operations Research, v.18 n.1-4, p.261-266, Feb. 1989 [doi>10.1007/BF02097807]
	11	Christos H. Papadimitriou , Mihalis Yannakakis, Shortest Paths Without a Map, Proceedings of the 16th International Colloquium on Automata, Languages and Programming, p.610-620, July 11-15, 1989
	12	Christos H. Papadimitriou , Mihalis Yannakakis, The traveling salesman problem with distances one and two, Mathematics of Operations Research, v.18 n.1, p.1-11, Feb. 1993 [doi>10.1287/moor.18.1.1]
	13	R. Reynolds. Personal Communication. 1993.

CITED BY 28

	Avrim Blum , R. Ravi , Santosh Vempala, A constant-factor approximation algorithm for the k MST problem (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.442-448, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Sven Koenig , Yury Smirnov, Graph learning with a nearest neighbor approach, Proceedings of the ninth annual conference on Computational learning theory, p.19-28, June 28-July 01, 1996, Desenzano del Garda, Italy
	Aaron Archer , David P. Williamson, Faster approximation algorithms for the minimum latency problem, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Baruch Awerbuch , Yossi Azar , Avrim Blum , Santosh Vempala, Improved approximation guarantees for minimum-weight k-trees and prize-collecting salesmen, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.277-283, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Edward J. Anderson , Sándor P. Fekete, Asymmetric rendezvous on the plane, Proceedings of the fourteenth annual symposium on Computational geometry, p.365-373, June 07-10, 1998, Minneapolis, Minnesota, United States
	Sanjeev Arora , George Karakostas, Approximation schemes for minimum latency problems, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.688-693, May 01-04, 1999, Atlanta, Georgia, United States
	Leslie A. Hall , David B. Shmoys , Joel Wein, Scheduling to minimize average completion time: off-line and on-line algorithms, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.142-151, January 28-30, 1996, Atlanta, Georgia, United States
	Michel Goemans , Jon Kleinberg, An improved approximation ratio for the minimum latency problem, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.152-158, January 28-30, 1996, Atlanta, Georgia, United States
	On-line single-server dial-a-ride problems, Theoretical Computer Science, v.268 n.1, p.91-105, 10/06/2001
	Moses Charikar , Ronald Fagin , Venkatesan Guruswami , Jon Kleinberg , Prabhakar Raghavan , Amit Sahai, Query strategies for priced information (extended abstract), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.582-591, May 21-23, 2000, Portland, Oregon, United States
	Sanjeev Arora , George Karakostas, A 2 + &egr; approximation algorithm for the k-MST problem, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.754-759, January 09-11, 2000, San Francisco, California, United States
	Joseph S. B. Mitchell, Guillotine subdivisions approximate polygonal subdivisions: a simple new method for the geometric k-MST problem, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.402-408, January 28-30, 1996, Atlanta, Georgia, United States
	Xin He , Zhi-Zhong Chen, Shortest path in complete bipartite digraph problem and its applications, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.230-238, January 05-07, 1997, New Orleans, Louisiana, United States
	Jittat Fakcharoenphol , Chris Harrelson , Satish Rao, The k-traveling repairman problem, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Moses Charikar , Ronald Fagin , Venkatesan Guruswami , Jon Kleinberg , Prabhakar Raghavan , Amit Sahai, Query strategies for priced information, Journal of Computer and System Sciences, v.64 n.4, p.785-819, June 2002
	W. Zhao , M. Ammar , E. Zegura, A message ferrying approach for data delivery in sparse mobile ad hoc networks, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan
	Bang Ye Wu , Zheng-Nan Huang , Fu-Jie Zhan, Exact algorithms for the minimum latency problem, Information Processing Letters, v.92 n.6, p.303-309, 31 December 2004
	Sven O. Krumke , Willem E. de Paepe , Diana Poensgen , Leen Stougie, News from the online traveling repairman, Theoretical Computer Science, v.295 n.1-3, p.279-294, 24 February 2003
	Guolong Lin , Chandrashekhar Nagarajan , Rajmohan Rajaraman , David P. Williamson, A general approach for incremental approximation and hierarchical clustering, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1147-1156, January 22-26, 2006, Miami, Florida
	Suman Banerjee , Christopher Kommareddy , Koushik Kar , Bobby Bhattacharjee , Samir Khuller, OMNI: an efficient overlay multicast infrastructure for real-time applications, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.6, p.826-841, 13 April 2006
	Matt Lepinski , David Liben-Nowell , Seth Gilbert , April Rasala Lehman, Playing games in many possible worlds, Proceedings of the 7th ACM conference on Electronic commerce, p.150-159, June 11-15, 2006, Ann Arbor, Michigan, USA
	Marek Chrobak , Claire Kenyon-Mathieu, SIGACT news online algorithms column 10: competitiveness via doubling, ACM SIGACT News, v.37 n.4, December 2006
	Raja Jothi , Balaji Raghavachari, Approximating the k-traveling repairman problem with repairtimes, Journal of Discrete Algorithms, v.5 n.2, p.293-303, June, 2007
	Jittat Fakcharoenphol , Chris Harrelson , Satish Rao, The k-traveling repairmen problem, ACM Transactions on Algorithms (TALG), v.3 n.4, p.40-es, November 2007
	Isabel Méndez-Díaz , Paula Zabala , Abilio Lucena, A new formulation for the Traveling Deliveryman Problem, Discrete Applied Mathematics, v.156 n.17, p.3223-3237, October, 2008
	Yongluan Zhou , Beng Chin Ooi , Kian-Lee Tan, Disseminating streaming data in a dynamic environment: an adaptive and cost-based approach, The VLDB Journal — The International Journal on Very Large Data Bases, v.17 n.6, p.1465-1483, November 2008
	Andreas Spillner , Binh T. Nguyen , Vincent Moulton, Computing Phylogenetic Diversity for Split Systems, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.5 n.2, p.235-244, April 2008
	Ke Liang , Roger Zimmermann, Cross-tree adjustment for spatialized audio streaming over networked virtual environments, Proceedings of the 18th international workshop on Network and operating systems support for digital audio and video, June 03-05, 2009, Williamsburg, VA, USA