Random shortest paths: non-Euclidean instances for metric optimization problems

DOI10.1007/s00453-014-9901-9zbMath1319.90072arXiv1306.3030OpenAlexW2116039769MaRDI QIDQ494931

Karl Bringmann, Christian Engels, Bodo Manthey, B. V. Raghavendra Rao

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

zbMATH Keywords

approximation algorithmsfirst passage percolationrandom metricsrandom shortest paths

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (2)

Probabilistic analysis of optimization problems on generalized random shortest path metrics ⋮ Probabilistic analysis of optimization problems on sparse random shortest path metrics

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

This page was built for publication: Random shortest paths: non-Euclidean instances for metric optimization problems