Probabilistic analysis of optimization problems on sparse random shortest path metrics
From MaRDI portal
Publication:6088299
DOI10.1007/s00453-023-01167-3MaRDI QIDQ6088299
Bodo Manthey, Stefan Klootwijk
Publication date: 13 December 2023
Published in: Algorithmica (Search for Journal in Brave)
probabilistic analysisapproximation algorithmsaverage-case analysisfirst-passage percolationrandom shortest path metrics
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Random shortest paths: non-Euclidean instances for metric optimization problems
- Average-case approximation ratio of the 2-opt algorithm for the TSP
- Edge-isoperimetric inequalities in the grid
- The expected length of a shortest path
- Ordering properties of convolutions of exponential random variables
- Not all insertion methods yield constant approximate tours in the Euclidean plane
- The traveling salesman. Computational solutions for RSP applications
- Tail bounds for sums of geometric and exponential variables
- Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP
- Probabilistic analysis of optimization problems on generalized random shortest path metrics
- On the Expected Value of a Random Assignment Problem
- 50 Years of First-Passage Percolation
- Probabilistic Analysis of a Greedy Heuristic for Euclidean Matching
- Expander graphs and their applications
- Upper (lower) bounds on the mean of the maximum (minimum) of a number of random variables
- On Shortest Paths in Graphs with Random Weights
- On a Greedy Heuristic for Complete Matching
- An Analysis of Several Heuristics for the Traveling Salesman Problem
- New Results on the Old k-opt Algorithm for the Traveling Salesman Problem
- One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights
- On Random Symmetric Travelling Salesman Problems
This page was built for publication: Probabilistic analysis of optimization problems on sparse random shortest path metrics
