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

zbMATH Keywords

approximation algorithms; first passage percolation; random metrics; random shortest paths

Mathematics Subject Classification ID

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