TY - CONF
T1 - Probabilistic Analysis of Optimization Problems on Generalized Random Shortest Path Metrics
AU - Klootwijk, Stefan
AU - Manthey, Bodo
AU - Visser, Sander K.
N1 - Conference code: 16
PY - 2018/6
Y1 - 2018/6
N2 - 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.
AB - 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.
KW - Random shortest paths
KW - Random metrics
KW - Approximation algorithms
KW - Erdős-Rényi random graph
UR - http://www.scopus.com/inward/record.url?scp=85075915785&partnerID=8YFLogxK
M3 - Paper
SP - 147
EP - 150
T2 - 16th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2018
Y2 - 18 June 2018 through 20 June 2018
ER -