Worst case asymptotics for some classical optimization problems |
| |
Authors: | J. E. Yukich |
| |
Affiliation: | (1) Department of Mathematics, Lehigh University, 18015 Bethlehem, Pa., USA |
| |
Abstract: | We provide a simple and natural method for obtaining the worst case asymptotics of some of the classical problems in combinatorial optimization and operations research. Worst case asymptotics for the minimal spanning tree, shortest tour, and minimal matching onn points are found. The key simplifying idea involves consideration of the associated boundary processes. The general approach considered here also handles the case of power weighted edges.Research supported in part by NSA grant MDA904-95-H-1005. |
| |
Keywords: | 05 C 35 90 C 10 52 A 40 |
本文献已被 SpringerLink 等数据库收录! |
|