Probabilistic Analysis of Optimization Problems on Generalized Random Shortest Path Metrics

Stefan Klootwijk, Bodo Manthey, Sander K. Visser

Research output: Contribution to conferencePaperpeer-review

125 Downloads (Pure)

Abstract

A graph G=(V,E) satisfies the α,β-cut-property if the fraction of edges present in each cut of the graph lies between α and β. The Erdős-Rényi random graph G(n,p) satisfies this property w.h.p. for α=(1-ε)p and β=(1+ε)p whenever p is sufficiently large and ε is a suitably chosen constant.
We study the behavior of random shortest path metrics applied to graphs G that satisfy the α,β-cut-property. These random metrics are defined as follows: Let w(e) be independently drawn random edge weights for all e in E, and define d(u,v) to be the shortest path distance between u and v in G with respect to the weights w.
Using the ideas of Bringmann et al. (Algorithmica, 2015), who studied random shortest path metrics on the complete graph, i.e., the graph that satisfies the 1,1-cut-propertym we derive some properties of the metric and obtain a clustering of the vertices. Using this, we conduct a probabilistic analysis of some simple heuristics on these random shortest path metrics.
Original languageEnglish
Pages147-150
Publication statusPublished - Jun 2018
Event16th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2018 - CNAM, Paris, France
Duration: 18 Jun 201820 Jun 2018
Conference number: 16
http://ctw18.lipn.univ-paris13.fr/

Workshop

Workshop16th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2018
Abbreviated titleCTW 2018
Country/TerritoryFrance
CityParis
Period18/06/1820/06/18
Internet address

Keywords

  • Random shortest paths
  • Random metrics
  • Approximation algorithms
  • Erdős-Rényi random graph

Fingerprint

Dive into the research topics of 'Probabilistic Analysis of Optimization Problems on Generalized Random Shortest Path Metrics'. Together they form a unique fingerprint.

Cite this