Paths, Trees, and Minimum Latency Tours

Cambridge, Massachusettes October 11-October 14

DOI Bookmark:

http://doi.ieeecomputersociety.org/10.1109/SFCS.2003.1238179

44th Annual IEEE Symposium on Foundat ...

	This Article
	PURCHASE ARTICLE: $19 PDF HTML IEEE Xplore Subscribers
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Kamalika Chaudhuri Articles by Brighten Godfrey Articles by Satish Rao Articles by Kunal Talwar

	ASCII Text	x
	Kamalika Chaudhuri, Brighten Godfrey, Satish Rao, Kunal Talwar, "Paths, Trees, and Minimum Latency Tours," Foundations of Computer Science, Annual IEEE Symposium on, pp. 36, 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03), 2003.

	BibTex	x
	@article{ 10.1109/SFCS.2003.1238179, author = {Kamalika Chaudhuri and Brighten Godfrey and Satish Rao and Kunal Talwar}, title = {Paths, Trees, and Minimum Latency Tours}, journal ={Foundations of Computer Science, Annual IEEE Symposium on}, volume = {0}, year = {2003}, issn = {0272-5428}, pages = {36}, doi = {http://doi.ieeecomputersociety.org/10.1109/SFCS.2003.1238179}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Foundations of Computer Science, Annual IEEE Symposium on TI - Paths, Trees, and Minimum Latency Tours SN - 0272-5428 SP EP A1 - Kamalika Chaudhuri, A1 - Brighten Godfrey, A1 - Satish Rao, A1 - Kunal Talwar, PY - 2003 KW - null VL - 0 JA - Foundations of Computer Science, Annual IEEE Symposium on ER -

Kamalika Chaudhuri, University of California at Berkeley

Brighten Godfrey, University of California at Berkeley

Satish Rao, University of California at Berkeley

Kunal Talwar, University of California at Berkeley

We give improved approximation algorithms for a variety of latency minimization problems. In particular, we give a 3.59¹-approximation to the minimum latency problem, improving on previous algorithms by a multiplicative factor of 2. Our techniques also give similar improvements for related problems like k-traveling repairmen and its multiple depot variant. We also observe that standard techniques can be used to speed up the previous and this algorithm by a factor of \bar O(n).

Citation:

Kamalika Chaudhuri, Brighten Godfrey, Satish Rao, Kunal Talwar, "Paths, Trees, and Minimum Latency Tours," focs, pp.36, 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03), 2003

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.