Boundary effects in the traveling salesperson problem. (English) Zbl 0814.90126
Summary: Consider a subset \(F\) of \([0,1]^ 2\) that is generated by a Poisson point process of constant intensity \(\lambda\). Denote by \(\theta(\lambda)\) the expected length of the shortest tour through \(F\). We prove that for \(\lambda\) large enough, we have \(c\sqrt\lambda+ 1/K\leq \theta(\lambda)\leq c\sqrt\lambda+ K\), where \(c\), \(K\) are universal constants. This settles a conjecture of Karp.
MSC:
| 90C35 | Programming involving graphs or networks |
| 93E03 | Stochastic systems in control theory (general) |
References:
| [1] | K. Alexander, “Rates of convergence of means for distance-minimizing subadditive Euclidean functionals”, to appear in Ann. Appl. Probab.; K. Alexander, “Rates of convergence of means for distance-minimizing subadditive Euclidean functionals”, to appear in Ann. Appl. Probab. · Zbl 0809.60016 |
| [2] | Alexander, K., A note on some rates of convergence in first-passage percolation, Ann. Appl. Probab., 3, 81-90 (1990) · Zbl 0771.60090 |
| [3] | Bearwood, J.; Halton, J. H.; Hammersley, J. M., The shortest path through many points, (Proc. Cambridge Philos. Soc., 55 (1959)), 299-327 · Zbl 0118.35601 |
| [4] | Jaillet, P., Cube versus torus models and the Euclidean minimum spanning tree constant, Ann. Appl. Probab., 3, 582-592 (1992) · Zbl 0781.60016 |
| [5] | Jaillet, P., Rates of convergence for quasi-additive smooth Euclidean functionals and application to combinatorial optimization problems, Math. Oper. Res., 17, 965-980 (1992) · Zbl 0770.90052 |
| [6] | Jaillet, P., Rate of convergence for the Euclidean minimum spanning tree limit law, Oper. Res. Lett., 14, 73-78 (1993) · Zbl 0793.90059 |
| [7] | Karp, R. M., Probabilistic analysis of partitioning algorithms for the traveling-salesman problem in the plane, Math. Oper. Res., 2, 209-224 (1977) · Zbl 0391.90091 |
| [8] | Rhee, W.; Talagrand, M., Martingale inequalities and NP-complete problems, Math. Oper. Res., 12, 177-181 (1987) · Zbl 0718.60040 |
| [9] | Rhee, W.; Talagrand, M., On the \(k\)-center problem with many points, Oper. Res. Lett., 6, 309-314 (1989) · Zbl 0682.90033 |
| [10] | Rhee, W.; Talagrand, M., On the long edges in the shortest tour through \(N\) random points, Combinatorica, 12, 323-330 (1992) · Zbl 0756.60012 |
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.
