Faster approximation algorithms for the minimum latency problem

ABSTRACT

In this paper, we give a 9.28-approximation algorithm for the minimum latency problem that uses only O(n log n) calls to the prize-collecting Steiner tree (PCST) subroutine of Goemans and Williamson. A previous algorithm of Goemans and Kleinberg for the minimum latency problem requires an approximation algorithm for the k-MST problem which is called as a black box. Their algorithm can achieve a performance guarantee of 10.77 while making O(n² log n) PCST calls (via a k-MST algorithm of Garg), or a performance guarantee of 7.18 + ε while using n^O(1/ε) PCST calls (via a k-MST algorithm of Arora and Karakostas). In order to match our approximation ratio (i.e. setting ε = 2.10), the latter version requires O(n⁵ log² n) PCST calls, so our running time bound is faster by a factor of Θ(n⁴ log n). Since PCST can be implemented to run in O(n²) time, the overall running time of our algorithm is O(n³ log n).The basic idea for our improvement is that we do not treat the k-MST algorithm as a black box. Thus we are able to take advantage of some situations in which the PCST subroutine delivers a k-MST with an improved performance guarantee.

REFERENCES

• 1: F. Afrati, S. Cosmadakis, C. H. Papadimitriou, G. Papageorgiou, and N. Papakostantinou. The complexity of the traveling repairman problem. Informatique Theorique et Applications, 20(1):79--87, 1986.
• 2: S. R. Agnihothri. A mean value analysis of the travelling repairman problem. IIE Trans., 20(2):223--229, June 1988.
• 3: 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 [doi>10.1145/301250.301432]
• 4: 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
• 5: Sunil Arya , H. Ramesh, A 2.5-factor approximation algorithm for the k-MST problem, Information Processing Letters, v.65 n.3, p.117-118, Feb. 1998 [doi>10.1016/S0020-0190(98)00010-6]
• 6: Giorgio Ausiello , Stefano Leonardi , Alberto Marchetti-Spaccamela, On Salesmen, Repairmen, Spiders, and Other Traveling Agents, Proceedings of the 4th Italian Conference on Algorithms and Complexity, p.1-16, March 01, 2000
• 7: I. Averbakh and O. Berman. Sales-delivery man problems on treelike networks. Networks, 25:45--58, 1995.
• 8: L. Bianco, A. Mingozzi, and S. Ricciardelli. The traveling salesman problem with cumulative costs. Networks, 23(2):81--91, 1993.
• 9: Avrim Blum , Prasad Chalasani , Don Coppersmith , Bill Pulleyblank , Prabhakar Raghavan , Madhu Sudan, The minimum latency problem, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.163-171, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195125]
• 10: Fabián A. Chudak , Tim Roughgarden , David P. Williamson, Approximate k-MSTs and k-Steiner Trees via the Primal-Dual Method and Lagrangean Relaxation, Proceedings of the 8th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.60-70, June 13-15, 2001
• 11: 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
• 12: On-line single-server dial-a-ride problems, Theoretical Computer Science, v.268 n.1, p.91-105, 10/06/2001 [doi>10.1016/S0304-3975(00)00261-9]
• 13: Matteo Fischetti , Gilbert Laporte , Silvano Martello, The delivery man problem and cumulative matroids, Operations Research, v.41 n.6, p.1055-1064, Nov.-Dec. 1993 [doi>10.1287/opre.41.6.1055]
• 14: Fedor V. Fomin , Andrej Lilngas, Approximation algorithms for time-dependent orienteering, Information Processing Letters, v.83 n.2, p.57-62, 31 July 2002 [doi>10.1016/S0020-0190(01)00313-1]
• 15: Harold N. Gabow , Seth Pettie, The Dynamic Vertex Minimum Problem and Its Application to Clustering-Type Approximation Algorithms, Proceedings of the 8th Scandinavian Workshop on Algorithm Theory, p.190-199, July 03-05, 2002
• 16: N. Garg, A 3-approximation for the minimum tree spanning k vertices, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.302, October 14-16, 1996
• 17: N. Garg. Personal communication, 1999.
• 18: M. Goemans and J. Kleinberg. An improved approximation ratio for the minimum latency problem. Math. Prog., 82:111--124, 1998.
• 19: Michel X. Goemans , David P. Williamson, A General Approximation Technique for Constrained Forest Problems, SIAM Journal on Computing, v.24 n.2, p.296-317, April 1995 [doi>10.1137/S0097539793242618]
• 20: Elias Koutsoupias , Christos H. Papadimitriou , Mihalis Yannakakis, Searching a Fixed Graph, Proceedings of the 23rd International Colloquium on Automata, Languages and Programming, p.280-289, July 08-12, 1996
• 21: Sven Oliver Krumke , Willem de Paepe , Diana Poensgen , Leen Stougie, News from the Online Traveling Repairman, Proceedings of the 26th International Symposium on Mathematical Foundations of Computer Science, p.487-499, August 27-31, 2001
• 22: A. Lucena. Time-dependent traveling salesman problem--the deliveryman case. Networks, 20(6):753--763, 1990.
• 23: 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]
• 24: 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]
• 25: J.-C. Picard and M. Queyranne. The time-dependent traveling salesman problem and its application to the tardiness problem in one-machine scheduling. Operations Research, 26:86--110, 1978.
• 26: Sartaj Sahni , Teofilo Gonzalez, P-Complete Approximation Problems, Journal of the ACM (JACM), v.23 n.3, p.555-565, July 1976 [doi>10.1145/321958.321975]
• 27: D. Simchi-Levi and O. Berman. Minimizing the total flow time of n jobs on a network. IIE Trans., 23(3):236--244, Sept 1991.
• 28: René Sitters, The Minimum Latency Problem Is NP-Hard for Weighted Trees, Proceedings of the 9th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.230-239, May 27-29, 2002
• 29: J. N. Tsitsiklis. Special cases of traveling salesman and repairman problems with time windows. Networks, 22:263--282, 1992.
• 30: R. J. Vander Wiel and N. V. Sahinidis. Heuristic bounds and test problem generation for the time-dependent traveling salesman problem. Transportation Sci., 29(2):167--183, May 1995.
• 31: R. J. Vander Wiel and N. V. Sahinidis. An exact solution approach for the time-dependent traveling-salesman problem. Naval Research Logistics, 43:797--820, 1996.
• 32: I. R. Webb. Depth-first solutions for the deliveryman problem on tree-like networks: an evaluation using a permutation model. Transportation Sci., 30(2):134--147, May 1996.
• 33: Bang Ye Wu, Polynomial time algorithms for some minimum latency problems, Information Processing Letters, v.75 n.5, p.225-229, Oct. 31, 2000 [doi>10.1016/S0020-0190(00)00102-2]
• 34: C. Yang. A dynamic programming algorithm for the travelling repairman problem. Asia-Pacific J. Operations Research, 6:192--206, 1989.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Theory