Inapproximability of Diameter in super-linear time: Beyond the 5/3 ratio

August 26, 2020 Β· Declared Dead Β· πŸ› Symposium on Theoretical Aspects of Computer Science

πŸ‘» CAUSE OF DEATH: Ghosted
No code link whatsoever

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Γ‰douard Bonnet arXiv ID 2008.11315 Category cs.DS: Data Structures & Algorithms Cross-listed cs.CC, math.CO Citations 8 Venue Symposium on Theoretical Aspects of Computer Science Last Checked 4 months ago
Abstract
We show, assuming the Strong Exponential Time Hypothesis, that for every $\varepsilon > 0$, approximating directed Diameter on $m$-arc graphs within ratio $7/4 - \varepsilon$ requires $m^{4/3 - o(1)}$ time. Our construction uses nonnegative edge weights but even holds for sparse digraphs, i.e., for which the number of vertices $n$ and the number of arcs $m$ satisfy $m = n \log^{O(1)} n$. This is the first result that conditionally rules out a near-linear time $5/3$-approximation for Diameter.
Community shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

πŸ“œ Similar Papers

In the same crypt β€” Data Structures & Algorithms

Died the same way β€” πŸ‘» Ghosted