Reduction from Triangle Collection* to dynamic 4/3-Diameter: Difference between revisions
Jump to navigation
Jump to search
No edit summary Tags: Manual revert Reverted |
No edit summary Tag: Manual revert |
||
| (4 intermediate revisions by the same user not shown) | |||
| Line 7: | Line 7: | ||
== Implications == | == Implications == | ||
assume: SETH or {3}SUM Hypothesis or APSP Hypothesis<br/>then: there exists no | assume: SETH or {3}SUM Hypothesis or APSP Hypothesis<br/>then: there exists no static ${4}/{3}-\epsilon$ approximation with additive error $O(m^\delta)$ with running time $O(m^{\frac{3}{2}({1}-\delta)-\epsilon'})$ or incremental/decremental algorithm with amortized time $O(m^{\frac{1}{2}-\frac{3\delta}{2}-\epsilon'})$ for any $\epsilon,\epsilon' > {0}$ | ||
== Year == | == Year == | ||
Latest revision as of 10:47, 28 April 2023
FROM: Triangle Collection* TO: dynamic 4/3-Diameter
Description
Implications
assume: SETH or {3}SUM Hypothesis or APSP Hypothesis
then: there exists no static ${4}/{3}-\epsilon$ approximation with additive error $O(m^\delta)$ with running time $O(m^{\frac{3}{2}({1}-\delta)-\epsilon'})$ or incremental/decremental algorithm with amortized time $O(m^{\frac{1}{2}-\frac{3\delta}{2}-\epsilon'})$ for any $\epsilon,\epsilon' > {0}$
Year
2016
Reference
Dahlgaard, S. (2016). On the hardness of partially dynamic graph problems and connections to diameter. arXiv preprint arXiv:1602.06705.