Random shortest paths: non-Euclidean instances for metric optimization problems (Q494931): Difference between revisions

Revision as of 16:55, 10 July 2024

scientific article; zbMATH DE number 6209973

Random Shortest Paths: Non-euclidean Instances for Metric Optimization Problems

Language	Label	Description	Also known as
English	Random shortest paths: non-Euclidean instances for metric optimization problems	scientific article; zbMATH DE number 6209973	Random Shortest Paths: Non-euclidean Instances for Metric Optimization Problems

Statements

instance of

scholarly article

0 references

title

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

0 references

Random Shortest Paths: Non-euclidean Instances for Metric Optimization Problems (English)

0 references

0 references

0 references

0 references

B. V. Raghavendra Rao

0 references

published in

Algorithmica

0 references

Mathematical Foundations of Computer Science 2013

0 references

publication date

3 September 2015

0 references

20 September 2013

0 references

full work available at URL

https://arxiv.org/abs/1306.3030

0 references

zbMATH Keywords

random shortest paths

0 references

first passage percolation

0 references

approximation algorithms

0 references

random metrics

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

The Longest Minimum-Weight Path in a Complete Graph

0 references

Smoothed Analysis of the k-Means Method

0 references

Local Search Heuristics for k-Median and Facility Location Problems

0 references

Q4258216

0 references

Probabilistic Analysis of a Greedy Heuristic for Euclidean Matching

0 references

Lower Bounds for Insertion Methods for TSP

0 references

First passage percolation on random graphs with finite mean degrees

0 references

First Passage Percolation on the Erdős–Rényi Random Graph

0 references

Universality for first passage percolation on sparse random graphs

0 references

On Shortest Paths in Graphs with Random Weights

0 references

Q3266051

0 references

New Results on the Old k-opt Algorithm for the Traveling Salesman Problem

0 references

The expected length of a shortest path

0 references

The average performance of the greedy matching algorithm

0 references

On patching algorithms for random asymmetric travelling salesman problems

0 references

Short paths for first passage percolation on the complete graph

0 references

Average-case approximation ratio of the 2-opt algorithm for the TSP

0 references

Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP

0 references

On Random Symmetric Travelling Salesman Problems

0 references

The shortest-path problem for graphs with random arc-lengths

0 references

FIRST-PASSAGE PERCOLATION ON THE RANDOM GRAPH

0 references

Size and Weight of Shortest Path Trees with Exponential Link Weights

0 references

One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights

0 references

Q4461911

0 references

Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane

0 references

Q3707785

0 references

A probabilistic analysis of the switching algorithm for the Euclidean TSP

0 references

First Passage Percolation on Inhomogeneous Random Graphs

0 references

Maximum flow in planar networks with exponentially distributed arc capacities

0 references

Shortest paths in networks with exponentially distributed arc lengths

0 references

Minimal spanning trees in undirected networks with exponentially distributed arc weights

0 references

Smoothed Analysis of the 2-Opt Heuristic for the TSP: Polynomial Bounds for Gaussian Noise

0 references

All-Pairs Shortest Paths in $O(n^2)$ time with high probability

0 references

On a Greedy Heuristic for Complete Matching

0 references

An Analysis of Several Heuristics for the Traveling Salesman Problem

0 references

Q5306025

0 references

Random metric spaces and universality

0 references

Probability theory of classical Euclidean optimization problems

0 references

Identifiers

zbMATH Open document ID

1319.90072

0 references

1319.90071

0 references

DOI

10.1007/s00453-014-9901-9

0 references

10.1007/978-3-642-40313-2_21

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:494931

@@ Property / cites work @@
+The Longest Minimum-Weight Path in a Complete Graph
+Normal rank
@@ Property / cites work @@
+Smoothed Analysis of the k-Means Method
@@ Property / cites work: Smoothed Analysis of the k-Means Method / rank @@
+Normal rank
@@ Property / cites work @@
+Local Search Heuristics for <i>k</i>-Median and Facility Location Problems
+Normal rank
@@ Property / cites work @@
+Q4258216
@@ Property / cites work: Q4258216 / rank @@
+Normal rank
@@ Property / cites work @@
+Probabilistic Analysis of a Greedy Heuristic for Euclidean Matching
+Normal rank
@@ Property / cites work @@
+Lower Bounds for Insertion Methods for TSP
@@ Property / cites work: Lower Bounds for Insertion Methods for TSP / rank @@
+Normal rank
@@ Property / cites work @@
+First passage percolation on random graphs with finite mean degrees
+Normal rank
@@ Property / cites work @@
+First Passage Percolation on the Erdős–Rényi Random Graph
+Normal rank
@@ Property / cites work @@
+Universality for first passage percolation on sparse random graphs
+Normal rank
@@ Property / cites work @@
+On Shortest Paths in Graphs with Random Weights
@@ Property / cites work: On Shortest Paths in Graphs with Random Weights / rank @@
+Normal rank
@@ Property / cites work @@
+Q3266051
@@ Property / cites work: Q3266051 / rank @@
+Normal rank
@@ Property / cites work @@
+New Results on the Old <i>k</i>-opt Algorithm for the Traveling Salesman Problem
+Normal rank
@@ Property / cites work @@
+The expected length of a shortest path
@@ Property / cites work: The expected length of a shortest path / rank @@
+Normal rank
@@ Property / cites work @@
+The average performance of the greedy matching algorithm
+Normal rank
@@ Property / cites work @@
+On patching algorithms for random asymmetric travelling salesman problems
+Normal rank
@@ Property / cites work @@
+Short paths for first passage percolation on the complete graph
+Normal rank
@@ Property / cites work @@
+Average-case approximation ratio of the 2-opt algorithm for the TSP
+Normal rank
@@ Property / cites work @@
+Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP
+Normal rank
@@ Property / cites work @@
+On Random Symmetric Travelling Salesman Problems
@@ Property / cites work: On Random Symmetric Travelling Salesman Problems / rank @@
+Normal rank
@@ Property / cites work @@
+The shortest-path problem for graphs with random arc-lengths
+Normal rank
@@ Property / cites work @@
+FIRST-PASSAGE PERCOLATION ON THE RANDOM GRAPH
@@ Property / cites work: FIRST-PASSAGE PERCOLATION ON THE RANDOM GRAPH / rank @@
+Normal rank
@@ Property / cites work @@
+Size and Weight of Shortest Path Trees with Exponential Link Weights
+Normal rank
@@ Property / cites work @@
+One, Two and Three Times log <i>n</i>/<i>n</i> for Paths in a  Complete Graph with Random Weights
+Normal rank
@@ Property / cites work @@
+Q4461911
@@ Property / cites work: Q4461911 / rank @@
+Normal rank
@@ Property / cites work @@
+Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
+Normal rank
@@ Property / cites work @@
+Q3707785
@@ Property / cites work: Q3707785 / rank @@
+Normal rank
@@ Property / cites work @@
+A probabilistic analysis of the switching algorithm for the Euclidean TSP
+Normal rank
@@ Property / cites work @@
+First Passage Percolation on Inhomogeneous Random Graphs
+Normal rank
@@ Property / cites work @@
+Maximum flow in planar networks with exponentially distributed arc capacities
+Normal rank
@@ Property / cites work @@
+Shortest paths in networks with exponentially distributed arc lengths
+Normal rank
@@ Property / cites work @@
+Minimal spanning trees in undirected networks with exponentially distributed arc weights
+Normal rank
@@ Property / cites work @@
+Smoothed Analysis of the 2-Opt Heuristic for the TSP: Polynomial Bounds for Gaussian Noise
+Normal rank
@@ Property / cites work @@
+All-Pairs Shortest Paths in $O(n^2)$ time with high probability
+Normal rank
@@ Property / cites work @@
+On a Greedy Heuristic for Complete Matching
@@ Property / cites work: On a Greedy Heuristic for Complete Matching / rank @@
+Normal rank
@@ Property / cites work @@
+An Analysis of Several Heuristics for the Traveling Salesman Problem
+Normal rank
@@ Property / cites work @@
+Q5306025
@@ Property / cites work: Q5306025 / rank @@
+Normal rank
@@ Property / cites work @@
+Random metric spaces and universality
@@ Property / cites work: Random metric spaces and universality / rank @@
+Normal rank
@@ Property / cites work @@
+Probability theory of classical Euclidean optimization problems
+Normal rank