|
|||||
|
|
Partitioning heuristics for two geometric maximization problems |
|
| Authors: | M.E Dyer A.M Frieze C.J.H McDiarmid |
| Affiliation: | Department of Mathematics and Statistics, Teesside Polytechnic, Middlesbrough, Cleveland TS1 3BA, UK;Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PA 15213, USA (on leave from Queen Mary College London);Institute of Economics and Statistics, Oxford University, Oxford OX1 3UL, UK |
| Abstract: | Given n points randomly selected from a uniform distribution on the unit square, we describe linear-time partitioning heuristics which will construct a matching or a tour of these points. We show that the heuristics closely approximate the optimum values as n → ∞. Hence we show that the asymptotic values of the maximum matching and tour are about 0·3826n and twice this value respectively. |
| Keywords: | heuristics partitioning |
| 本文献已被 ScienceDirect 等数据库收录！ | |