Carnegie Mellon University
Browse
file.pdf (370.55 kB)

Separating subadditive Euclidean functionals

Download (370.55 kB)
journal contribution
posted on 2015-01-13, 00:00 authored by Alan FriezeAlan Frieze, Wesley Pegden

If we are given n random points in the hypercube [0,1]d, then the minimum length of a Traveling Salesperson Tour through the points, the minimum length of a spanning tree, and the minimum length of a matching, etc., are known to be asymptotically βnd−1d a.s., where β is an absolute constant in each case. We prove separation results for these constants. In particular, concerning the constants βdTSP, βdMST, βdMM, and βdTF from the asymptotic formulas for the minimum length TSP, spanning tree, matching, and 2-factor, respectively, we prove that βdMST<βdTSP, 2βdMM<βdTSP, and βdTF<βdTSP for all d≥2. We also asymptotically separate the TSP from its linear programming relaxation in this setting. Our results have some computational relevance, showing that a certain natural class of simple algorithms cannot solve the random Euclidean TSP efficiently.

History

Date

2015-01-13

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC