loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03)
Paths, Trees, and Minimum Latency Tours
Cambridge, Massachusettes
October 11-October 14
ISBN: 0-7695-2040-5
ASCII Text
x 
 
Kamalika Chaudhuri, Brighten Godfrey, Satish Rao, Kunal Talwar, "Paths, Trees, and Minimum Latency Tours," Foundations of Computer Science, IEEE Annual 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, IEEE Annual 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, IEEE Annual 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, IEEE Annual 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.591-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
Usage of this product signifies your acceptance of the Terms of Use.