pith. sign in

arxiv: 1907.11078 · v1 · pith:ZQBB2PCXnew · submitted 2019-07-25 · 💻 cs.DS · cs.CC

Approximating APSP without Scaling: Equivalence of Approximate Min-Plus and Exact Min-Max

Karl Bringmann , Marvin K\"unnemann , Karol W\k{e}grzycki This is my paper

Pith reviewed 2026-05-24 16:01 UTC · model grok-4.3

classification 💻 cs.DS cs.CC
keywords APSPapproximation algorithmsstrongly polynomial timeMin-Max ProductMin-Plus Productmatrix multiplicationdirected graphsequivalence
0
0 comments X

The pith

Approximating directed APSP to (1+ε) is equivalent to exactly computing the Min-Max matrix product.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper removes the dependence on the largest weight W from approximation algorithms for APSP and related problems, yielding strongly polynomial running times. For undirected graphs and several graph parameters the time matches the matrix-multiplication bound up to polylog factors in n and 1/ε. For directed graphs the time is O(n to the (ω+3)/2 over ε times polylog), which is faster than the best exact algorithm but provably cannot be improved without also improving exact Min-Max Product algorithms. The central result is an equivalence showing that any better directed approximation scheme would immediately give a faster exact algorithm for Min-Max Product.

Core claim

The authors prove that (1+ε)-approximating all-pairs shortest paths on directed graphs is computationally equivalent to exactly computing the Min-Max Product of two n-by-n matrices. They also construct strongly polynomial (1+ε)-approximation schemes running in O(n^ω / ε polylog(n/ε)) time for undirected APSP, diameter, radius, median, minimum-weight triangle and minimum-weight cycle, and in O(n^{(ω+3)/2} ε^{-1} polylog(n/ε)) time for directed APSP.

What carries the argument

The equivalence reduction between approximate directed Min-Plus matrix product and exact Min-Max matrix product, which removes all dependence on the weight bound W while preserving approximation guarantees.

If this is right

  • Undirected APSP and the listed graph parameters admit (1+ε)-approximation schemes whose number of arithmetic operations is independent of W.
  • Directed APSP can be approximated faster than it can be solved exactly, yet the exponent (ω+3)/2 is tight under the equivalence.
  • Any improvement to the directed APSP exponent immediately yields a faster exact algorithm for Min-Max Product.
  • Zwick's scaling technique is not required for these approximation guarantees on undirected graphs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The equivalence may extend to other matrix products or to sparse-graph versions of the same problems.
  • Min-Max Product could serve as a canonical hard problem for studying approximation barriers in weighted graphs.
  • The same reduction technique might separate approximation from exact computation for additional graph parameters on directed graphs.

Load-bearing premise

The reductions between approximate APSP and exact Min-Max Product preserve the approximation ratio and run in time independent of the largest weight.

What would settle it

An algorithm that computes (1+ε)-approximate directed APSP in time o(n^{(ω+3)/2} / ε) without also producing a faster exact Min-Max Product algorithm.

Figures

Figures reproduced from arXiv: 1907.11078 by Karl Bringmann, Karol W\k{e}grzycki, Marvin K\"unnemann.

Figure 1
Figure 1. Figure 1: An illustration for Algorithm 2. Shown is the posit [PITH_FULL_IMAGE:figures/full_fig_p012_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Illustration of the procedure SplitChunks, which splits and selects chunks of the input numbers on different levels r. Claim 5.4. We have d [PITH_FULL_IMAGE:figures/full_fig_p015_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Illustration of SeparateChunks, which separates the list of chunks Tr on some level r into two sub-lists Tr,1 and Tr,2. The selected chunks are marked in red/light-shaded and blue/dark￾shaded. (In the next step, the red/light-shaded chunks will form a set Xℓ , and the blue/dark-shaded ones will form a set Yℓ . Note that within Tr,1 every red chunk is ε-distant from every blue chunk, except for its right ne… view at source ↗
Figure 4
Figure 4. Figure 4: Illustration of ShiftedTransitions in log-scale. Dashed areas represent the added/removed numbers from iteration t to t + 1. In each iteration, we shift to the right by a factor 2, resulting in at most  log2 1 ε  iterations. Note that in each iteration the red/light-shaded numbers are in distance greater than 1 ε from the blue/dark-shaded numbers. Moreover, the distance between any two numbers in the das… view at source ↗
read the original abstract

Zwick's $(1+\varepsilon)$-approximation algorithm for the All Pairs Shortest Path (APSP) problem runs in time $\widetilde{O}(\frac{n^\omega}{\varepsilon} \log{W})$, where $\omega \le 2.373$ is the exponent of matrix multiplication and $W$ denotes the largest weight. This can be used to approximate several graph characteristics including the diameter, radius, median, minimum-weight triangle, and minimum-weight cycle in the same time bound. Since Zwick's algorithm uses the scaling technique, it has a factor $\log W$ in the running time. In this paper, we study whether APSP and related problems admit approximation schemes avoiding the scaling technique. That is, the number of arithmetic operations should be independent of $W$; this is called strongly polynomial. Our main results are as follows. - We design approximation schemes in strongly polynomial time $O(\frac{n^\omega}{\varepsilon} \text{polylog}(\frac{n}{\varepsilon}))$ for APSP on undirected graphs as well as for the graph characteristics diameter, radius, median, minimum-weight triangle, and minimum-weight cycle on directed or undirected graphs. - For APSP on directed graphs we design an approximation scheme in strongly polynomial time $O(n^{\frac{\omega + 3}{2}} \varepsilon^{-1} \text{polylog}(\frac{n}{\varepsilon}))$. This is significantly faster than the best exact algorithm. - We explain why our approximation scheme for APSP on directed graphs has a worse exponent than $\omega$: Any improvement over our exponent $\frac{\omega + 3}{2}$ would improve the best known algorithm for Min-Max Product In fact, we prove that approximating directed APSP and exactly computing the Min-Max Product are equivalent.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript claims to develop the first strongly polynomial (1+ε)-approximation algorithms for APSP and related problems (diameter, radius, median, min-weight triangle/cycle). For undirected graphs these run in O(n^ω/ε polylog(n/ε)) time; for directed APSP the time is O(n^{(ω+3)/2} ε^{-1} polylog(n/ε)). It further proves an equivalence: any improvement to the directed exponent would yield a faster exact algorithm for Min-Max Product, and conversely an exact Min-Max algorithm yields the stated directed APSP approximation.

Significance. If the reductions and algorithms are correct, the results are significant: they remove all dependence on log W from prior scaling-based approximations, yielding the first strongly polynomial schemes for these problems. The equivalence supplies a fine-grained explanation for why the directed APSP approximation exponent remains (ω+3)/2 rather than ω, linking it directly to the complexity of exact Min-Max Product. This is a substantive contribution to the fine-grained complexity of approximation algorithms.

minor comments (3)
  1. The abstract states the equivalence but the introduction or §1 should explicitly flag that both directions of the reduction are shown to be strongly polynomial and approximation-preserving; this would help readers immediately see why the equivalence is load-bearing for the exponent claim.
  2. Notation for the Min-Max Product (definition of the operation and the matrix) should be introduced once in a dedicated preliminary subsection rather than scattered across the equivalence proof.
  3. Figure 1 (or the comparison table of running times) would benefit from an additional column showing the dependence on W in prior work versus the new strongly polynomial bounds.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary of our results and the recommendation for minor revision. The referee's description accurately captures the contributions regarding strongly polynomial approximation schemes for APSP and related problems, as well as the equivalence to Min-Max Product. No specific major comments were enumerated in the report.

Circularity Check

0 steps flagged

No circularity; equivalence established by explicit reductions

full rationale

The paper's central results consist of new strongly polynomial approximation algorithms for undirected APSP and related problems, a directed APSP algorithm with exponent (ω+3)/2, and a proved equivalence between (1+ε)-approximate directed APSP and exact Min-Max Product. No self-definitional steps, fitted parameters renamed as predictions, or load-bearing self-citations appear in the abstract or described claims. The equivalence is presented as a theorem proved within the paper via reductions that map instances while preserving approximation guarantees and independence from W. This is a standard self-contained derivation with no reduction of outputs to inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The results rest on the standard fast matrix multiplication exponent and on the correctness of the new reductions; no free parameters or invented entities are introduced in the abstract.

axioms (1)
  • standard math Matrix multiplication exponent ω ≤ 2.373
    Invoked to express the running times of the approximation schemes.

pith-pipeline@v0.9.0 · 5879 in / 1061 out tokens · 26239 ms · 2026-05-24T16:01:58.220410+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

62 extracted references · 62 canonical work pages · 1 internal anchor

  1. [1]

    Abboud and A

    A. Abboud and A. Rubinstein. Fast and deterministic cons tant factor approximation algorithms for LCS imply new circuit lower bounds. In Proc. 9th Innovations in Theoretical Computer Science Conference (ITCS’18) , volume 94, pages 35:1–35:14, 2018

    work page 2018

  2. [2]

    Abboud, F

    A. Abboud, F. Grandoni, and V. V. Williams. Subcubic equi valences between graph centrality problems, APSP and diameter. In Proc. 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’15) , pages 1681–1697, 2015

    work page 2015

  3. [3]

    Abboud, A

    A. Abboud, A. Rubinstein, and R. R. Williams. Distribute d PCP theorems for hardness of approximation in P. In Proc. 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS’17) , pages 25–36, 2017

    work page 2017

  4. [4]

    Allender, P

    E. Allender, P. Bürgisser, J. Kjeldgaard-Pedersen, and P . B. Miltersen. On the complexity of numerical analysis. SIAM J. Comput. , 38(5):1987–2006, 2009

    work page 1987

  5. [5]

    N. Alon, Z. Galil, and O. Margalit. On the exponent of the a ll pairs shortest path problem. J. Comput. Syst. Sci. , 54(2):255–262, 1997

    work page 1997

  6. [6]

    S. Arya, G. Das, D. M. Mount, J. S. Salowe, and M. H. M. Smid. Euclidean spanners: short, thin, and lanky. In Proc. 27th Annual ACM Symposium on Theory of Computing (STOC ’95), pages 489–498, 1995

    work page 1995

  7. [7]

    Backurs, P

    A. Backurs, P. Indyk, and L. Schmidt. Better approximation s for tree sparsity in nearly-linear time. In Proc. 28th Annual ACM-SIAM Symposium on Discrete Algorithm s (SODA’17) , pages 2215–2229, 2017

    work page 2017

  8. [8]

    L. Blum, F. Cucker, M. Shub, and S. Smale. Complexity and real computation . Springer Science & Business Media, 2012

    work page 2012

  9. [9]

    P. B. Callahan and S. R. Kosaraju. A decomposition of multi dimensional point sets with applications to k-nearest-neighbors and n-body potential fields. J. ACM , 42(1):67–90, 1995

    work page 1995

  10. [10]

    Chalermsook, M

    P. Chalermsook, M. Cygan, G. Kortsarz, B. Laekhanukit, P . Manurangsi, D. Nanongkai, and L. Trevisan. From Gap-ETH to FPT-inapproximability: Cliqu e, dominating set, and more. In Proc. 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS’17) , pages 743–754, 2017

    work page 2017

  11. [11]

    L. Chen. On the hardness of approximate and exact (bichr omatic) maximum inner product. In Proc. 33rd Computational Complexity Conference (CCC’18) , volume 102, pages 14:1–14:45, 2018. 28

    work page 2018

  12. [12]

    E. Cohen. Using selective path-doubling for parallel s hortest-path computations. J. Algorithms, 22(1):30–56, 1997

    work page 1997

  13. [13]

    Cohen and U

    E. Cohen and U. Zwick. All-pairs small-stretch paths. J. Algorithms , 38(2):335–353, 2001

    work page 2001

  14. [14]

    Cygan, M

    M. Cygan, M. Mucha, K. Wegrzycki, and M. Wlodarczyk. On p roblems equivalent to (min, +)-convolution. ACM Trans. Algorithms , 15(1):14:1–14:25, 2019

    work page 2019

  15. [15]

    Duan and S

    R. Duan and S. Pettie. Fast algorithms for (max,min)-ma trix multiplication and bottle- neck shortest paths. In Proc. 20th Annual ACM-SIAM Symposium on Discrete Algorithm s (SODA’09), pages 384–391, 2009

    work page 2009

  16. [16]

    Duan and H

    R. Duan and H. Ren. Approximating all-pair bounded-leg shortest path and APSP-AF in truly-subcubic time. In Proc. 45th International Colloquium on Automata, Language s, and Programming (ICALP’18), pages 42:1–42:12, 2018

    work page 2018

  17. [17]

    R. Duan, S. Pettie, and H. Su. Scaling algorithms for wei ghted matching in general graphs. In Proc. 28th Annual ACM-SIAM Symposium on Discrete Algorithm s (SODA’17), pages 781–800, 2017

    work page 2017

  18. [18]

    Edmonds and R

    J. Edmonds and R. M. Karp. Theoretical improvements in a lgorithmic efficiency for network flow problems. J. ACM , 19(2):248–264, 1972

    work page 1972

  19. [19]

    R. W. Floyd. Algorithm 97: Shortest path. Commun. ACM , 5(6):345, 1962

    work page 1962

  20. [20]

    L. C. Freeman. Centrality in social networks conceptua l clarification. Social networks , 1(3): 215–239, 1978

    work page 1978

  21. [21]

    H. N. Gabow and R. E. Tarjan. Faster scaling algorithms f or network problems. SIAM J. Comput., 18(5):1013–1036, 1989

    work page 1989

  22. [22]

    H. N. Gabow and R. E. Tarjan. Faster scaling algorithms f or general graph-matching problems. J. ACM , 38(4):815–853, 1991

    work page 1991

  23. [23]

    Galil and O

    Z. Galil and O. Margalit. All pairs shortest paths for gr aphs with small integer length edges. J. Comput. Syst. Sci. , 54(2):243–254, 1997

    work page 1997

  24. [24]

    F. L. Gall. Faster algorithms for rectangular matrix mu ltiplication. In Proc. 53rd Annual IEEE Symposium on Foundations of Computer Science, (FOCS 2012) , pages 514–523, 2012

    work page 2012

  25. [25]

    F. L. Gall. Powers of tensors and fast matrix multiplica tion. In Proc. 39th International Symposium on Symbolic and Algebraic Computation (ISSAC’14 ), pages 296–303, 2014

    work page 2014

  26. [26]

    F. L. Gall and F. Urrutia. Improved rectangular matrix m ultiplication using powers of the coppersmith-winograd tensor. In Proc. 29th Annual ACM-SIAM Symposium on Discrete Al- gorithms (SODA’18) , pages 1029–1046, 2018

    work page 2018

  27. [27]

    A. V. Goldberg. Scaling algorithms for the shortest pat hs problem. SIAM J. Comput. , 24(3): 494–504, 1995

    work page 1995

  28. [28]

    D. S. Hochbaum. Lower and upper bounds for the allocatio n problem and other nonlinear optimization problems. Math. Oper. Res. , 19(2):390–409, 1994. 29

    work page 1994

  29. [29]

    Karthik C. S., B. Laekhanukit, and P. Manurangsi. On the p arameterized complexity of approx- imating dominating set. In Proc. 50th Annual Symposium on Theory of Computing (STOC’18 ), pages 1283–1296, 2018

    work page 2018

  30. [30]

    P. N. Klein and S. Sairam. A parallel randomized approxi mation scheme for shortest paths. In Proc. 24th Annual ACM Symposium on Theory of Computing (STOC ’92), pages 750–758, 1992

    work page 1992

  31. [31]

    S. R. Kosaraju. Efficient tree pattern matching (prelimi nary version). In Proc. 30th Annual Symposium on Foundations of Computer Science (FOCS’89) , pages 178–183, 1989

    work page 1989

  32. [32]

    Künnemann, R

    M. Künnemann, R. Paturi, and S. Schneider. On the fine-gr ained complexity of one-dimensional dynamic programming. In Proc. 44th International Colloquium on Automata, Language s, and Programming (ICALP’17), pages 21:1–21:15, 2017

    work page 2017

  33. [33]

    Le Gall and H

    F. Le Gall and H. Nishimura. Quantum algorithms for matr ix products over semirings. Chicago J. Theor. Comput. Sci. , 2017, 2017

    work page 2017

  34. [34]

    Mucha, K

    M. Mucha, K. Wegrzycki, and M. Wlodarczyk. A subquadrat ic approximation scheme for partition. In Proc. 30th Annual ACM-SIAM Symposium on Discrete Algorithm s (SODA’19) , pages 70–88, 2019

    work page 2019

  35. [35]

    Quantum algorithms for shortest paths problems in structured instances

    A. Nayebi and V. V. Williams. Quantum algorithms for sho rtest paths problems in structured instances. CoRR, 2014. URL http://arxiv.org/abs/1410.6220

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  36. [36]

    Opsahl, F

    T. Opsahl, F. Agneessens, and J. Skvoretz. Node central ity in weighted networks: Generalizing degree and shortest paths. Social Networks, 32(3):245–251, 2010

    work page 2010

  37. [37]

    J. B. Orlin. A faster strongly polynomial minimum cost flo w algorithm. Operations Research, 41(2):338–350, 1993

    work page 1993

  38. [38]

    J. B. Orlin and R. K. Ahuja. New scaling algorithms for the assignment and minimum mean cycle problems. Math. Program., 54:41–56, 1992

    work page 1992

  39. [39]

    Roditty and A

    L. Roditty and A. Shapira. All-pairs shortest paths wit h a sublinear additive error. In Proc. 35th International Colloquium on Automata, Languages and P rogramming (ICALP’08), pages 622–633, 2008

    work page 2008

  40. [40]

    Roditty and V

    L. Roditty and V. V. Williams. Minimum weight cycles and triangles: Equivalences and algorithms. In Proc. 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS’11), pages 180–189, 2011

    work page 2011

  41. [41]

    Rubinstein

    A. Rubinstein. Hardness of approximate nearest neighb or search. In Proc. 50th Annual Sym- posium on Theory of Computing (STOC’18) , pages 1260–1268, 2018

    work page 2018

  42. [42]

    L. Schmidt. personal communication, 2017

    work page 2017

  43. [43]

    Schönhage

    A. Schönhage. On the power of random access machines. In Proc. 6th International Colloquium on Automata, Languages, and Programming (ICALP’79) , volume 71, pages 520–529, 1979. 30

    work page 1979

  44. [44]

    Schrijver

    A. Schrijver. A combinatorial algorithm minimizing su bmodular functions in strongly polyno- mial time. J. Comb. Theory, Ser. B , 80(2):346–355, 2000

    work page 2000

  45. [45]

    R. Seidel. On the all-pairs-shortest-path problem. In Proc. 24th Annual ACM Symposium on Theory of Computing (STOC’92) , pages 745–749, 1992

    work page 1992

  46. [46]

    O. Serang. A fast numerical method for max-convolution and the application to efficient max- product inference in Bayesian networks. Journal of Computational Biology , 22(8):770–783, 2015

    work page 2015

  47. [47]

    Shapira, R

    A. Shapira, R. Yuster, and U. Zwick. All-pairs bottlene ck paths in vertex weighted graphs. In Proc. 18th Annual ACM-SIAM Symposium on Discrete Algorithm s (SODA’07), pages 978–985, 2007

    work page 2007

  48. [48]

    Shoshan and U

    A. Shoshan and U. Zwick. All pairs shortest paths in undi rected graphs with integer weights. In Proc. 40th Annual IEE Symposium on Foundations of Computer S cience (FOCS’99), pages 605–615, 1999

    work page 1999

  49. [49]

    É. Tardos. A strongly polynomial minimum cost circulat ion algorithm. Combinatorica, 5(3): 247–256, 1985

    work page 1985

  50. [50]

    M. Thorup. Floats, integers, and single source shortes t paths. J. Algorithms , 35(2):189–201, 2000

    work page 2000

  51. [51]

    M. Thorup. Equivalence between priority queues and sor ting. In Proc. 43rd Symposium on Foundations of Computer Science (FOCS’02) , pages 125–134, 2002

    work page 2002

  52. [52]

    Thorup and U

    M. Thorup and U. Zwick. Approximate distance oracles. J. ACM , 52(1):1–24, 2005

    work page 2005

  53. [53]

    Vassilevska

    V. Vassilevska. Efficient algorithms for path problems i n weighted graphs. Carnegie Mellon University, 2008. PhD Thesis

    work page 2008

  54. [54]

    Vassilevska and R

    V. Vassilevska and R. Williams. Finding a maximum weigh t triangle in O(n3− δ) time, with applications. In Proc. 38th Annual ACM Symposium on Theory of Computing (STOC ’06), pages 225–231, 2006

    work page 2006

  55. [55]

    Vassilevska, R

    V. Vassilevska, R. Williams, and R. Yuster. All pairs bo ttleneck paths and max-min matrix products in truly subcubic time. Theory of Computing , 5(1):173–189, 2009

    work page 2009

  56. [56]

    L. A. Végh. A strongly polynomial algorithm for general ized flow maximization. Math. Oper. Res., 42(1):179–211, 2017

    work page 2017

  57. [57]

    Warshall

    S. Warshall. A theorem on Boolean matrices. J. ACM , 9(1):11–12, 1962

    work page 1962

  58. [58]

    R. R. Williams. Faster all-pairs shortest paths via cir cuit complexity. SIAM J. Comput. , 47 (5):1965–1985, 2018

    work page 1965

  59. [59]

    V. V. Williams and R. R. Williams. Subcubic equivalence s between path, matrix, and triangle problems. J. ACM , 65(5):27:1–27:38, 2018. 31

    work page 2018

  60. [60]

    R. Yuster. Efficient algorithms on sets of permutations, dominance, and real-weighted APSP. In Proc. 20th Annual ACM-SIAM Symposium on Discrete Algorithm s (SODA’09), pages 950–957, 2009

    work page 2009

  61. [61]

    R. Yuster. Approximate shortest paths in weighted grap hs. J. Comput. Syst. Sci. , 78(2): 632–637, 2012

    work page 2012

  62. [62]

    U. Zwick. All pairs shortest paths using bridging sets a nd rectangular matrix multiplication. J. ACM , 49(3):289–317, 2002. A Problem Definitions For an edge-weighted (directed or undirected) graph G, dG(u, v ) denotes the minimal total weight of any path from u to v in G. Directed/Undirected All-Pairs Shortest Path (APSP) Input: An edge-weighed directed/...

    work page 2002