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

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