Worst-Case Growth Rates of Some Classical Problems of Combinatorial Optimization | Zendy

John Steele | Zendy; Timothy Law Snyder | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Worst-Case Growth Rates of Some Classical Problems of Combinatorial Optimization

Author(s) -

John Steele,

Timothy Law Snyder

Publication year - 1989

Publication title -

siam journal on computing

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.533

H-Index - 122

eISSN - 1095-7111

pISSN - 0097-5397

DOI - 10.1137/0218019

Subject(s) - travelling salesman problem , mathematics , complement (music) , combinatorics , dimension (graph theory) , probabilistic logic , minimum spanning tree , constant (computer programming) , unit cube , steiner tree problem , spanning tree , combinatorial optimization , discrete mathematics , mathematical optimization , statistics , computer science , biochemistry , chemistry , complementation , programming language , gene , phenotype

A method is presented for determining the asymptotic worst-case behavior of quantities like the length of the minimal spanning tree or the length of an optimal traveling salesman tour of n points in the unit d-cube. In each of these classical problems, the worst-case lengths are proved to have the exact asymptotic growth rate of $\beta _n^{{{(d - 1)} / d}} $, where $\beta $ is a positive constant depending on the problem and the dimension. These results complement known results on the growth rates for the analogous quantities under probabilistic assumptions on the points, but the results given here are free of any probabilistic hypotheses.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research