Online ISSN:1349-8606
Progress in Informatics  
No.10 March 2013  
Page 167-174  
 
An efficient exact algorithm for the Minimum Latency Problem
Ha BANG BAN, Kien NGUYEN, Manh CUONG NGO and Duc NGHIA NGUYEN

LINK [1] F. Afrati, S. Cosmadakis, C. Papadimitriou, G. Papageorgiou, and N. Papakostantinou, “The complexity of the traveling repairman problem,” J. ITA, vol.20, no.1, pp.79-87, 1986.

LINK [2] A. Archer, A. Levin, and D. Williamson, “A faster, better approximation algorithm for the minimum latency problem,” J. SIAM, vol.37, no.1, pp.1472-1498, 2007.

LINK [3] A. Archer and Anna Blasiak, “Improved approximation algorithms for the minimum latency problem via prize-collecting stroll,” Proc. ACM-SIAM SODA, pp.429-447, 2010.

LINK [4] S. Arora and G. Karakostas, “Approximation schemes for minimum latency problems,” Proc. ACM STOC, pp.688-693, 1999.

LINK [5] H.B. Ban and D.N. Nguyen, “Improved genetic algorithm for minimum latency problem,” Proc. ACM SOICT, pp.9-15, 2010.

LINK [6] A. Blum, P. Chalasani, D. Coppersmith, W. Pulleyblank, P. Raghavan, and M. Sudan, “The minimum latency problem,” Proc. ACM STOC, pp.163-171, 1994.

LINK [7] K. Chaudhuri, B. Goldfrey, S. Rao, and K. Talwar, “Path, tree and minimum latency tour,” Proc. IEEE FOCS, pp.36-45, 2003.

LINK [8] A. Garcia, P. Jodr, and J. Tejel, “A note on the traveling repairmen problem,” J. Networks, vol.40, no.1, pp.27-31, 2002.

LINK [9] M. Goemans and J. Kleinberg, “An improved approximation ratio for the minimum latency problem,” Proc. ACM-SIAM SODA, pp.152-158, 1996.

LINK [10] E. Koutsoupias, C. Papadimitriou, and M. Yannakakis, “Searching a fixed graph,” Proc. ICALP, LNCS, vol.1099, pp.280-289, 1996.

LINK [11] E. Minieka, “The delivery man problem on a tree network,” J. AOR, vol.18, no.1, pp.261-266, 1989.

LINK [12] S. Sahni and T. Gonzalez, “P-complete approximation problem,” J. ACM, vol.23, no.3, pp.555-565, 1976.

LINK [13] D.S. Johnson and L.A. McGeoch, “The traveling salesman problem: A case study in local optimization,” Local Search in Combinatorial Optimization, John Wiley and Sons, Ltd., pp.215-310, 1997.

LINK [14] B.Y. Wu, “Polynomial time algorithms for some minimum latency problems,” Inform. Proc. Letters, vol.75, no.5, pp.225-229, 2000.

LINK [15] B.Y. Wu, Z.-N. Huang, and F.-J. Zhan, “Exact algorithms for the minimum latency problem,” Inform. Proc. Letters, vol.92, no.6, pp.303-309, 2004.

LINK [16] http://www.iwr.uniheidelberg.de/groups/comopt/software/TSPLIB95