Random shortest paths: non-Euclidean instances for metric optimization problems
From MaRDI portal
Publication:494931
DOI10.1007/s00453-014-9901-9zbMath1319.90072arXiv1306.3030MaRDI QIDQ494931
Karl Bringmann, Bodo Manthey, B. V. Raghavendra Rao, Christian Engels
Publication date: 3 September 2015
Published in: Algorithmica, Mathematical Foundations of Computer Science 2013 (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1306.3030
90C35: Programming involving graphs or networks
90C59: Approximation methods and heuristics in mathematical programming
90C27: Combinatorial optimization
68W25: Approximation algorithms
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Short paths for first passage percolation on the complete graph
- The average performance of the greedy matching algorithm
- Average-case approximation ratio of the 2-opt algorithm for the TSP
- The shortest-path problem for graphs with random arc-lengths
- A probabilistic analysis of the switching algorithm for the Euclidean TSP
- The expected length of a shortest path
- Probability theory of classical Euclidean optimization problems
- On patching algorithms for random asymmetric travelling salesman problems
- First passage percolation on random graphs with finite mean degrees
- Universality for first passage percolation on sparse random graphs
- Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP
- FIRST-PASSAGE PERCOLATION ON THE RANDOM GRAPH
- Smoothed Analysis of the 2-Opt Heuristic for the TSP: Polynomial Bounds for Gaussian Noise
- First Passage Percolation on the Erdős–Rényi Random Graph
- Probabilistic Analysis of a Greedy Heuristic for Euclidean Matching
- Size and Weight of Shortest Path Trees with Exponential Link Weights
- The Longest Minimum-Weight Path in a Complete Graph
- On Shortest Paths in Graphs with Random Weights
- Maximum flow in planar networks with exponentially distributed arc capacities
- Shortest paths in networks with exponentially distributed arc lengths
- Minimal spanning trees in undirected networks with exponentially distributed arc weights
- On a Greedy Heuristic for Complete Matching
- An Analysis of Several Heuristics for the Traveling Salesman Problem
- Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
- New Results on the Old k-opt Algorithm for the Traveling Salesman Problem
- Lower Bounds for Insertion Methods for TSP
- Local Search Heuristics for k-Median and Facility Location Problems
- One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights
- Random metric spaces and universality
- First Passage Percolation on Inhomogeneous Random Graphs
- Smoothed Analysis of the k-Means Method
- All-Pairs Shortest Paths in $O(n^2)$ time with high probability
- On Random Symmetric Travelling Salesman Problems
