Probabilistic analysis of optimization problems on generalized random shortest path metrics
DOI10.1016/j.tcs.2021.03.016zbMath1477.68562arXiv1810.11232OpenAlexW2952576310MaRDI QIDQ2662688
Stefan Klootwijk, Sander K. Visser, Bodo Manthey
Publication date: 14 April 2021
Published in: Theoretical Computer Science, WALCOM: Algorithms and Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1810.11232
approximation algorithmsfirst-passage percolationErdős-Rényi random graphrandom metricsrandom shortest paths
Programming involving graphs or networks (90C35) Analysis of algorithms (68W40) Random graphs (graph-theoretic aspects) (05C80) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Random shortest paths: non-Euclidean instances for metric optimization problems
- Stochastic orders
- The expected length of a shortest path
- Tail bounds for sums of geometric and exponential variables
- Probabilistic analysis of optimization problems on generalized random shortest path metrics
- First Passage Percolation on the Erdős–Rényi Random Graph
- On Shortest Paths in Graphs with Random Weights
- Probabilistic Analysis of a Relaxation for the k-Median Problem
- On a Greedy Heuristic for Complete Matching
- An Analysis of Several Heuristics for the Traveling Salesman Problem
- One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights
- An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization
- Probability and Computing
This page was built for publication: Probabilistic analysis of optimization problems on generalized random shortest path metrics
