On properties of geometric random problems in the plane

DOI10.1007/BF02098279zbMATH Open0839.90133MaRDI QIDQ1908291FDOQ1908291

Patrick Jaillet

Publication date: 26 February 1996

Published in: Annals of Operations Research (Search for Journal in Brave)

zbMATH Keywords

minimum spanning treerates of convergenceSteiner tree problemminimum weight matchingtraveling salesmangeometric random problems

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Bounds and Heuristics for Capacitated Routing Problems
• Spacefilling curves and the planar travelling salesman problem
• Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
• On the Travelling Salesperson Problem in Many Dimensions
• The minimum spanning tree constant in geometrical probability and under the independent model: A unified approach
• On the number of leaves of a euclidean minimal spanning tree
• Subadditive Euclidean functionals and nonlinear growth in geometric probability
• Growth rates of Euclidean minimal spanning trees with power weighted edges
• Worst-Case Growth Rates of Some Classical Problems of Combinatorial Optimization
• Cube versus torus models and the Euclidean minimum spanning tree constant
• Martingale Inequalities and NP-Complete Problems
• Random Minimal Trees
• A Fast Algorithm for the Euclidean Traveling Salesman Problem, Optimal with Probability One
• Probabilistic Analyses and Practical Algorithms for the Vehicle Routing Problem with Time Windows
• A sharp deviation inequality for the stochastic traveling salesman problem
• Probabilistic Analysis of the Capacitated Vehicle Routing Problem with Unsplit Demands
• Complete Convergence of Short Paths and Karp's Algorithm for the TSP
• Limit theorems and rates of convergence for Euclidean functionals
• Rate of convergence for the Euclidean minimum spanning tree limit law
• Rates of Convergence for Quasi-Additive Smooth Euclidean Functionals and Application to Combinatorial Optimization Problems
• Boundary domination and the distribution of the largest nearest-neighbor link in higher dimensions
• Analysis of Probabilistic Combinatorial Optimization Problems in Euclidean Spaces
• On the Fluctuations of the Stochastic Traveling Salesperson Problem

Cited In (6)

• Thresholding random geometric graph properties motivated by ad hoc sensor networks
• Probability of occurrence of some planar random quasi-homogeneous vector fields
• Limit theory of combinatorial optimization for random geometric graphs
• A Fractal Dimension for Measures via Persistent Homology
• The effect of dimension on certain geometric problems of irregularities of distribution
• Title not available (Why is that?)

Recommendations

• Probabilistic aspects of some problems in combinatorial geometry 👍 👎
• On the Geometry of Random Polytopes 👍 👎
• Some Dual Problems of Geometric Probability in the Plane 👍 👎
• Some problems of non uniform geometric probability relative to plane lattices 👍 👎
• Some geometric probabilities of lattices in the plane 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎

This page was built for publication: On properties of geometric random problems in the plane

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1908291)