View source for (5/3)-approximate ap-shortest paths

{{DISPLAYTITLE:(5/3)-approximate ap-shortest paths (All-Pairs Shortest Paths (APSP))}}
== Description == 

Approximate APSP within a factor of 5/3.

== Related Problems == 

Generalizations: [[APSP]]

Related: [[APSP on Dense Directed Graphs with Arbitrary Weights]], [[APSP on Dense Undirected Graphs with Arbitrary Weights]], [[APSP on Geometrically Weighted Graphs]], [[APSP on Dense Undirected Graphs with Positive Integer Weights]], [[APSP on Sparse Directed Graphs with Arbitrary Weights]], [[APSP on Sparse Undirected Graphs with Positive Integer Weights]], [[APSP on Sparse Undirected Graphs with Arbitrary Weights]], [[APSP on Dense Directed Unweighted Graphs]], [[APSP on Dense Undirected Unweighted Graphs]], [[APSP on Sparse Directed Unweighted Graphs]], [[APSP on Sparse Undirected Unweighted Graphs]]

== Parameters == 

<pre>n: number of vertices
m: number of edges</pre>

== Table of Algorithms == 

Currently no algorithms in our database for the given problem.

== Reductions FROM Problem == 

{| class="wikitable sortable"  style="text-align:center;" width="100%"

! Problem !! Implication !! Year !! Citation !! Reduction

|-

| [[BMM]] ||  style="text-align:left;" | assume: BMM<br/>then: combinatorial algorithms cannot solve target with preprocessing time $O(n^{3-\epsilon})$, and update and query times $O(n^{2-\epsilon})$ for any $\epsilon > {0}$ || 2017 || https://arxiv.org/pdf/1703.01638.pdf || [[Reduction from BMM to (5/3)-approximate ap-shortest paths|link]]
|-
|}