Can I read Towards Tight Approximation Bounds for Graph Diameter and Eccentricities on EtoBox?

Towards Tight Approximation Bounds for Graph Diameter and Eccentricities by Backurs, Arturs; Roditty, Liam; Segal, Gilad; Williams, Virginia Vassilevska; Wein, Nicole is a scholarly article available to read on EtoBox.

What is Towards Tight Approximation Bounds for Graph Diameter and Eccentricities about?

Among the most important graph parameters is the Diameter, the largest distance between any two vertices. There are no known very efficient algorithms for computing the Diameter exactly. Thus, much research has been devoted to how fast this parameter can be approximated. Chechik et al. showed that the diameter can be approximated within a multiplicative factor of $3/2$ in $\tilde{O}(m^{3/2})$ time. Furthermore, Roditty and Vassilevska W. showed that unless the Strong Exponential Time Hypothesis (SETH) fails, no $O(n^{2-\epsilon})$ time algorithm can achieve an approximation factor better than $3/2$ in sparse graphs. Thus the above algorithm is essentially optimal for sparse graphs for approximation factors less than $3/2$. It was, however, completely plausible that a $3/2$-approximation is possible in linear time. In this work we conditionally rule out such a possibility by showing that unless SETH fails no $O(m^{3/2-\epsilon})$ time algorithm can achieve an approximation factor better than $5/3$. Another fundamental set of graph parameters are the Eccentricities. The Eccentricity of a vertex $v$ is the distance between $v$ and the farthest vertex from $v$. Chechik et al. showed th

Author

Backurs, Arturs; Roditty, Liam; Segal, Gilad; Williams, Virginia Vassilevska; Wein, Nicole

Published

2018

Language

EN