Approximation schemes for minimum latency problems. (English) Zbl 1345.90110
Vitter, Jeffrey Scott (ed.) et al., Proceedings of the 31st annual ACM symposium on theory of computing, STOC 1999. Atlanta, GA, USA, May 1–4, 1999. New York, NY: ACM, Association for Computing Machinery (ISBN 1-58113-067-8). 688-693 (1999).
MSC:
| 90C59 | Approximation methods and heuristics in mathematical programming |
| 68W25 | Approximation algorithms |
| 90C27 | Combinatorial optimization |
| 90C35 | Programming involving graphs or networks |
References:
| [1] | F. Afrati, S. Cosmadakis, C. Papadimitriou, G. Papageorgiou, and N. Papakc tantinou. The complexity of the traveling repairman problem, lnforrnatique Theorique et Applications, 20(1):79-87, 1986. · Zbl 0585.68057 |
| [2] | S. Arora. Polynomial-time approximation schemes for Euclidean TSP and other geometric problems. Journal of the A CM 45(5) pp 1-30, Sep. 1998. Preliminary version in Proceedings of 37th IEEE Syrnp. on Foundations of Computer Science(FOC’S), pp 2- 12, 1996. 10.1145/290179.290180 · Zbl 0911.90333 |
| [3] | S. Arora, C. Lund, R. Motward, M. Sudan, M. Szegedy. Proof Verification and the Hardness of Approximation for Problems. Journal of the A CM 45(3) pp 501-555, May 1998. 10.1145/278298.278306 · Zbl 1065.68570 |
| [4] | A. Blum, P. Chalaaani, D. Coppersmith, B. Pulleyblank, P. Raghavan and M. Sudan. The minimum latency problem. Proceedings of 6th A CM Syrup. on Theory Of Computing(STOC), pp 163-171, 1994. 10.1145/195058.195125 · Zbl 1345.90073 |
| [5] | X. Deng nd C. Papadimitriou. Exploring an unknown graph. Proc. 31st IEEE Syrup. on Foundations of Computer Science(FOGS), pp. 355-361, 1990. |
| [6] | N. Gaxg. A 3-approximation for the minimum tree spanning k vertices. Proc. 37th IEEE Syrup. on Foundations of Computer \(cience(FOCS), pp.302- 309~ 1996\) |
| [7] | M. Goemans and J. Kleinberg. An improved approximation ratio for the minimum latency problem. Proc. 7th A CM-SIAM Symposium on Discrete Algorithms(SODA), pp 152-158, 1996. · Zbl 0845.90122 |
| [8] | M. GrStschel, L. Lov sz, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization. Springer Verlag, Berlin 1988. · Zbl 0634.05001 |
| [9] | E. Koutsoupias, C. Papadimitriou and M. Yannakakis. Searching a fixed graph. Lecture Not in Computer Science(LNCS) 1099, pp.280-289, Springer Verlag, 1996. · Zbl 1045.90532 |
| [10] | J. Mitchell. Guillotine subdivisions approximate polygonal subdivisions: Part II- A simple PTAS for the geometric k MST, TSP and related problems. Preliminary manuscript, April 30, 1996. To appear in SIAM J. Computing. 10.1137/S0097539796309764 |
| [11] | C. Papadimitriou and M. Yannakakis. The traveling salesman problem with distances one and two. Mathematics o/ Operations Research, 18(1):1-11, Feb. 1993. 10.1287/moor.18.1.1 · Zbl 0778.90057 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
