Probability Theory of Classical Euclidean Optimization Problems
This monograph describes the stochastic behavior of the solutions to the classic problems of Euclidean combinatorial optimization, computational geometry, and operations research. Using two-sided additivity and isoperimetry, it formulates general methods
- PDF / 10,716,128 Bytes
- 162 Pages / 432 x 666 pts Page_size
- 5 Downloads / 205 Views
1675
Lecture Notes in Mathematics Editors: A. Dold, Heidelberg F. Takens, Groningen
1675
Springer Berlin Heidelberg New York Barcelona Budapest Hong Kong London Milan Paris Santa Clara Singapore Tokyo
Joseph E. Yukich
Probability Theory of Classical Euclidean Optimization Problems
Springer
Author Joseph E. Yukich Department of Mathematics Lehigh University Bethlehem, PA 18015, USA e-mail: [email protected]
Cataloging-in-Publication Data applied for Die Deutsche Bibliothek - CIP-Einheitsaufnahme Yukich, Joseph E.: Probability theory of classical euclidean optimization problems / J. E. Yukich. - Berlin; Heidelberg; New York; Barcelona; Budapest; Hong Kong; London; Milan; Paris; Santa Clara; Singapore; Tokyo: Springer, 1998 (Lecture notes in mathematics; 1675) ISBN 3-540-63666-8
Mathematics Subject Classification (1991): 60C05, 60D05, 60F15, 60FlO, OSC80 ISSN 0075-8434 ISBN 3-540-63666-8 Springer-Verlag Berlin Heidelberg New York This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer-Verlag. Violations are liable for prosecution under the German Copyright Law. © Springer-Verlag Berlin Heidelberg 1998 Printed in Germany
The use of general descriptive names, registered names, trademarks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. Typesetting: Camera-ready TEX output by the author SPIN: 10553398 46/3143-543210 - Printed on acid-free paper
To Rahul, Nicholas, and Arati
PREFACE This monograph aims to develop the probability theory of solutions to the classic problems in Euclidean combinatorial optimization, computational geometry, and operations research. These problems are naturally associated with graphs and our chief goal is to describe the almost sure (a.s.) behavior of the total edge length of these graphs. We do this by formulating a general approach which describes the total edge length behavior of graphs on random point sets in Euclidean space. Many random Euclidean graphs, especially those motivated by some of the classic problems of discrete mathematics, have intrinsic similarities including self-similarity, subadditivity, and superadditivity. We use these similarities to prove laws of large numbers, rates of convergence, and large deviation principles for the solutions of the classic problems in combinatorial optimization. We prove limit theorems for the length of the shortest tour on a random sample, the minimal length of a tree spanned by a random sample, and the length of a minimal Eucli
Data Loading...
