1 Search Results for "Klootwijk, Stefan"


Document
Probabilistic Analysis of Optimization Problems on Sparse Random Shortest Path Metrics

Authors: Stefan Klootwijk and Bodo Manthey

Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)


Abstract
Simple heuristics for (combinatorial) optimization problems often show a remarkable performance in practice. Worst-case analysis often falls short of explaining this performance. Because of this, "beyond worst-case analysis" of algorithms has recently gained a lot of attention, including probabilistic analysis of algorithms. The instances of many (combinatorial) optimization problems are essentially a discrete metric space. Probabilistic analysis for such metric optimization problems has nevertheless mostly been conducted on instances drawn from Euclidean space, which provides a structure that is usually heavily exploited in the analysis. However, most instances from practice are not Euclidean. Little work has been done on metric instances drawn from other, more realistic, distributions. Some initial results have been obtained in recent years, where random shortest path metrics generated from dense graphs (either complete graphs or Erdős - Rényi random graphs) have been used so far. In this paper we extend these findings to sparse graphs, with a focus on grid graphs. A random shortest path metric is constructed by drawing independent random edge weights for each edge in the graph and setting the distance between every pair of vertices to the length of a shortest path between them with respect to the drawn weights. For such instances generated from a grid graph, we prove that the greedy heuristic for the minimum distance maximum matching problem, and the nearest neighbor and insertion heuristics for the traveling salesman problem all achieve a constant expected approximation ratio. Additionally, for instances generated from an arbitrary sparse graph, we show that the 2-opt heuristic for the traveling salesman problem also achieves a constant expected approximation ratio.

Cite as

Stefan Klootwijk and Bodo Manthey. Probabilistic Analysis of Optimization Problems on Sparse Random Shortest Path Metrics. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{klootwijk_et_al:LIPIcs.AofA.2020.19,
  author =	{Klootwijk, Stefan and Manthey, Bodo},
  title =	{{Probabilistic Analysis of Optimization Problems on Sparse Random Shortest Path Metrics}},
  booktitle =	{31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
  pages =	{19:1--19:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-147-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{159},
  editor =	{Drmota, Michael and Heuberger, Clemens},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.19},
  URN =		{urn:nbn:de:0030-drops-120494},
  doi =		{10.4230/LIPIcs.AofA.2020.19},
  annote =	{Keywords: Random shortest paths, Random metrics, Approximation algorithms, First-passage percolation}
}
  • Refine by Author
  • 1 Klootwijk, Stefan
  • 1 Manthey, Bodo

  • Refine by Classification
  • 1 Mathematics of computing → Approximation algorithms
  • 1 Mathematics of computing → Combinatorial optimization
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Random network models

  • Refine by Keyword
  • 1 Approximation algorithms
  • 1 First-passage percolation
  • 1 Random metrics
  • 1 Random shortest paths

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2020

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail