Pith. sign in

REVIEW 5 minor 51 references

Simple Approximations for General Spanner Problems

T0 review · 0 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read General spanner problems now have their first unconditional m-approximation.

desk verdict The main theorems hold up, the flagged 'exponent typo' is standard epsilon-absorption, and this is a clean paper that deserves real review. read the letter →

arxiv 2506.23638 v2 pith:ILFXPAOS submitted 2025-06-30 cs.DS cs.DMmath.CO

Fritz Bökler , Markus Chimani , Henning Jasper This is my paper · ORCID
classification cs.DScs.DMmath.CO MSC 68W2505C8568R10
keywords spannerapproximationalgorithmdecoupledweightandlengthfreeformdistancedemandsgreedyrandomizedroundingmulticommodityflowlayeredgraph
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper attacks the most general spanner problem: edges may have independent weights and lengths, and every node pair may demand its own maximum distance. Previously, no nontrivial approximation was known for this full setting. The authors give two simple algorithms. AugmentedGreedy binary-searches the cheapest weight threshold that still permits a feasible spanner, then runs the classic Greedy heuristic on that subgraph; it achieves an unconditional m-approximation, where m is the number of edges, while preserving all of Greedy's known size and lightness guarantees. RandomizedRounding builds a layered graph extension, solves a standard multicommodity flow LP, and rounds it, yielding an O(n log n)-approximation for integer lengths and polynomially bounded distance demands, and an O(log n)-ratio on constant-bounded instances with bounded degree.

What carries the argument

Two mechanisms carry the results. First is a weight-threshold search: binary search over the distinct edge weights finds the smallest weight hat-w such that the subgraph consisting of edges of weight at most hat-w is already a feasible spanner; since hat-w lower-bounds the optimum, the at most m edges in that subgraph give the m-ratio, and running Greedy on it preserves Greedy's known guarantees. Second is the delta-extension, a layered graph with delta+1 copies of V in which arcs advance by l(e) layers and self-arcs advance one layer; distance demands become reachability between specified layer-copies, a multicommodity flow LP is solved and independently rounded with factor gamma, and feasibility is certified by a union bound over ascending cuts.

What would settle it

Take a family of undirected decoupled freeform instances from the distance-preserver construction of [17] with m edges and run AugmentedGreedy: if the returned weight ever exceeds m times the optimum, Theorem 3 is false; conversely, the paper itself shows the analysis is tight on such instances. For RandomizedRounding, run Algorithm 3 on integer-length instances with delta = 2^n and a single terminal pair, and check whether the delta-extension LP can be formulated and solved in polynomial time; failure to scale to super-polynomial delta would confirm the polynomial-boundedness restriction is genuine.

Watch

Extended reading notes

Core claim

The paper's central claim is that the most general spanner problem is approximable by elementary means. Theorem 3 states that AugmentedGreedy is an m-approximation for all (un)directed decoupled freeform spanner problems, with no restrictions on weights, lengths, or demands, and that it simultaneously retains the size and lightness guarantees Greedy enjoys for coupled multiplicative and basic additive spanners. Theorem 15 states that randomized rounding of a multicommodity flow LP on the delta-extension returns a feasible spanner with high probability, with expected approximation ratio gamma = ln(n·mu·|K|) = ln(n·(delta+2)^{n-2}·|K|), which lies in O(n log n); this matches the best known ratio up to a factor of O($n^{{1/5-epsilon}}$) using only standard tools.

Load-bearing premise

The O(n log n) result assumes edge lengths are integers and the maximum distance demand delta is polynomially bounded in n; if delta is super-polynomial, the layered graph has delta+1 layers and both the running time and the rounding failure probability degrade, so the stated ratio no longer holds.

Editorial extensions

If this is right

  • The m-ratio gives the first provable worst-case guarantee for decoupled freeform spanner instances, where practitioners previously had to force weights and lengths into a coupled format and rely on unproven heuristics.
  • The O(n log n) expected ratio nearly matches the best known O~(n^{4/5+epsilon}) guarantee for this problem class while using only a standard LP solver, making the algorithm implementable.
  • On constant-bounded distance demands with constant (out)degree, the same rounding scheme yields an O(log n) approximation, extending a regime that was previously limited to undirected unit-length multiplicative 2-spanners.
  • AugmentedGreedy inherits Greedy's size O(n^{1+1/k}) and lightness O(n/k) guarantees for coupled multiplicative alpha-spanners, and size O(n^{3/2}) for additive +beta-spanners with any constant beta >= 2.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • In instances where weights and lengths are anti-correlated, the tighter bound O(n^{1+1/k} + sqrt(n)|E^>|) from Lemma 4 is likely the operative guarantee in practice, rather than the worst-case m.
  • The cut-based rounding in a layered extension is a transferable template: other constrained network design problems with distance requirements could be encoded as reachability in layered graphs and rounded the same way.
  • A natural next step is testing whether rational lengths can be scaled to integers with a bounded blow-up, which would extend Theorem 15 to all rational instances at a controlled cost in the ratio.
  • When the number of terminal pairs is constant and demands are constant-bounded, the modified rounding with gamma = ln(2 mu' |K|) achieves a constant expected ratio, a regime that appears in practical networks with few critical node pairs.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 5 minor

Summary. The paper studies the decoupled freeform spanner problem, in which a directed or undirected graph has independent edge weights and edge lengths and arbitrary pairwise distance demands, and the goal is to find a minimum-weight feasible subgraph. It presents two approximation algorithms. AugmentedGreedy first binary-searches for the smallest weight threshold w_hat such that the weight-restricted subgraph G[w_hat] is feasible, then runs the classic Greedy algorithm on G[w_hat]. Theorem 3 proves an unconditional m-approximation for all decoupled freeform spanner problems, and Corollaries 5, 7, and 8 argue that known Greedy size and lightness guarantees are retained for coupled multiplicative, geometric, and unit-length additive spanners. RandomizedRounding solves a standard multicommodity flow LP on a layered delta-extension of the graph and rounds the fractional solution with probabilities proportional to gamma times the LP values. Theorem 15 gives an expected ln(n mu |K|) in O(n log n) approximation under integer lengths and polynomially bounded distance demands, and Corollary 18 gives an O(log n) approximation for constant-bounded demands on bounded-degree graphs.

Significance. If the results stand, they substantially simplify the state of the art for the most general spanner formulation. The m-approximation is the first unconditional guarantee that places no restrictions on weights, lengths, or distance demands, and it is obtained by a very simple modification of Greedy. The O(n log n) randomized rounding result matches the only previous sublinear approximation for this setting up to lower-order factors, while replacing a pipeline of heavy subroutines with a single LP plus a direct rounding argument. The paper also provides the first logarithmic approximation for constant-distance-demand instances on bounded-degree graphs, including directed graphs. The proofs of the two main theorems are clear, self-contained, and involve no fitted parameters; the integer-length and polynomially-bounded-demand assumptions for RandomizedRounding are explicitly stated and coincide with the assumptions of the prior work it improves on. The main limitation that the O(n log n) ratio depends on polynomially bounded delta is properly declared in Section 4 and in Tables 2, so it does not undermine the contribution.

minor comments (5)
  1. [Abstract and Section 4] The comparison statement 'match it up to a factor of O(n^{1/5-eps})' is easy to misread, because the prior guarantee is written as eO(n^{4/5+eps}) and the new ratio is O(n log n); reusing epsilon on both sides makes the exponent appear to have the wrong sign. Please rephrase, for example by writing O(n^{1/5+eps}) or by explicitly saying that epsilon is re-parameterized to absorb the logarithmic factor.
  2. [Appendix B, Eq. (8)] In Eq. (8), the inequality d_H0(u,z)+d_H0(z,v) > delta(u,v)+2 is presented as a consequence of the violated demand d_H0(u,v) > delta(u,v), but the triangle inequality alone gives only d_H0(u,z)+d_H0(z,v) > delta(u,v). The extra '+2' needs a justification using z's adjacency to the added path and the order in which demands were processed; please expand this step.
  3. [Observation 2 proof] In the proof of Observation 2, the assertion that a minimum st-path P in the demand graph can be chosen with P subset of K' is not immediate; a short explanation, for instance by replacing each non-metric demand edge with its witnessing path in D, would improve readability.
  4. [Theorem 15 and Algorithm 3] The phrase 'expected approximation ratio gamma' is slightly ambiguous, since Algorithm 3 may return an infeasible subgraph with probability at most 1/n. Please state explicitly that E[w(H)] <= gamma * OPT and that H is feasible with probability at least 1 - 1/n.
  5. [Abstract] The abstract contains a typo: 'two surprisingly simple approximations algorithms' should read 'two surprisingly simple approximation algorithms'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: both central derivations are self-contained and do not reduce to their inputs.

full rationale

The central claims are derived from first principles. Theorem 3 fixes the smallest weight threshold w_hat for which G[w_hat] is feasible, observes w_hat <= OPT, and bounds the final weight by |E[w_hat]| * w_hat <= m * OPT; this is a direct lower-bound argument, not a circular one. Theorem 15 formulates an independent multicommodity-flow LP in the delta-extension; any feasible spanner yields a feasible LP solution, so the LP optimum lower-bounds OPT, and the randomized rounding analysis uses only a union bound over ascending cuts with gamma = ln(n * mu * |K|). No parameter is fitted to the data being predicted, and no conclusion is assumed as an input. External results such as Althofer et al., Coppersmith and Elkin, and Knudsen are used as standard subroutines and do not carry the central reductions. The paper's self-citations appear only in contextual or practical sentences and are not load-bearing for Theorem 3, Theorem 15, or the corollaries. The explicit assumptions of integer lengths and polynomially bounded distance demands are stated plainly in Section 4 and only shape the O(n log n) regime; they do not make the argument circular.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central results rest on standard tools: the monotonicity of feasibility under weight thresholds, the LP relaxation of the spanner problem via layered graphs, Menger's cut-path equivalence, and the union bound. The paper also invokes external results on Greedy guarantees and pairwise distance preservers. No free parameters are fitted, and no new physical entities are postulated.

assumptions (5)
  • domain assumption The graph G is connected and simple; weights are nonnegative, lengths and demands are positive (Definition 1).
    These are the problem definition assumptions from Section 1.
  • domain assumption Without loss of generality, maximum length l_hat <= delta_hat <= n*l_hat (Section 2).
    Longer edges cannot appear in feasible paths, and demands above n*l_hat are trivially satisfied; this bounds the layered graph size.
  • standard math Any feasible spanner induces a feasible solution to the multicommodity flow LP (MCF) in the layered graph (Section 4).
    This is the standard relaxation argument; a feasible spanner routes one unit of flow per terminal pair along its short path, with self-arcs filling the remaining layers.
  • standard math Known Greedy guarantees for coupled multiplicative and additive spanners (Althofer et al. [5], Knudsen [36], Chandra et al. [11], Elkin et al. [25]) are correct.
    The paper builds on these external results to claim AugmentedGreedy retains Greedy's guarantees.
  • standard math Coppersmith-Elkin pairwise distance preserver bound [17, Corollary 7.8] applies to the union of Greedy paths in Lemma 4.
    Used to bound the number of edges added for high-weight terminal edges.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Simple Approximations for General Spanner Problems." pith.science (2026). https://pith.science/paper/ILFXPAOS

@misc{pith2026250623638,
  author       = {Pith},
  title        = {Pith review of: Simple Approximations for General Spanner Problems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ILFXPAOS}},
  note         = {Machine review of arXiv:2506.23638}
}
read the original abstract

Consider a graph with n nodes and m edges, independent edge weights and lengths, and arbitrary distance demands for node pairs. The spanner problem asks for a minimum-weight subgraph that satisfies these demands via sufficiently short paths w.r.t. the edge lengths. For multiplicative alpha-spanners (where demands equal alpha times the original distances) and assuming that each edge's weight equals its length, the simple Greedy heuristic by Alth\"ofer et al. (1993) is known to yield strong solutions, both in theory and practice. To obtain guarantees in more general settings, recent approximations typically abandon this simplicity and practicality. Still, so far, there is no known non-trivial approximation algorithm for the spanner problem in its most general form. We provide two surprisingly simple approximations algorithms. In general, our Augmented Greedy achieves the first unconditional approximation ratio of m, which is non-trivial due to the independence of weights and lengths. Crucially, it maintains all size and weight guarantees Greedy is known for, i.e., in the aforementioned multiplicative alpha-spanner scenario and even for additive +beta-spanners. Further, it generalizes some of these size guarantees to derive new weight guarantees. Our second approach, Randomized Rounding, establishes a graph transformation that allows a simple rounding scheme over a standard multicommodity flow LP. It yields an O(n log n)-approximation, assuming integer lengths and polynomially bounded distance demands. The only other known approximation guarantee in this general setting requires several complex subalgorithms and analyses, yet we match it up to a factor of O(n^{1/5-eps}) using standard tools. Further, on bounded-degree graphs, we yield the first O(log n) approximation ratio for constant-bounded distance demands (beyond multiplicative 2-spanners in unit-length graphs).

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

51 extracted references · 34 canonical work pages

  1. [33]

    Approximation algorithms for directed weighted spanners

    Elena Grigorescu, Nithish Kumar, and Young-San Lin. Approximation algorithms for directed weighted spanners. In APPROX/RANDOM 2023, volume 275 of LIPIcs, pages 8:1–8:23. LZI Dagstuhl, 2023. doi: 10.4230/LIPIcs.APPROX/RANDOM.2023.8

    work page doi:10.4230/lipics.approx/random.2023.8 2023

  2. [1]

    Weighted additive spanners

    Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Stephen Kobourov, and Richard Spence. Weighted additive spanners. In Proc. WG 2020, Revised Selected Papers 46 , pages 401–413. Springer, 2020. doi: http://dx.doi.org/10.48550/arXiv.2002.07152

    arXiv doi:10.48550/arxiv.2002.07152 2020

  3. [2]

    On additive span- ners in weighted graphs with local error

    Reyan Ahmed, Greg Bodwin, Keaton Hamm, Stephen Kobourov, and Richard Spence. On additive span- ners in weighted graphs with local error. In Proc. WG 2021, Revised Selected Papers 47 , pages 361–373. Springer, 2021. doi:https://doi.org/10.1007/978-3-030-86838-3_28

    work page doi:10.1007/978-3-030-86838-3_28 2021

  4. [3]

    Graph spanners: A tutorial review

    Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Keaton Hamm, Mohammad Javad Latifi Jebelli, Stephen Kobourov, and Richard Spence. Graph spanners: A tutorial review. Computer Science Review , 37, 2020. doi:10.1016/j.cosrev.2020.100253

    arXiv 2020

  5. [4]

    Fast estimation of diameter and shortest paths (without matrix multiplication)

    Donald Aingworth, Chandra Chekuri, Piotr Indyk, and Rajeev Motwani. Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM Journal on Computing , 28(4):1167–1181, 1999. doi:https://doi.org/10.1137/S0097539796303421

    doi:10.1137/s0097539796303421 1999

  6. [5]

    On sparse spanners of weighted graphs

    Ingo Alth¨ ofer, Gautam Das, David Dobkin, Deborah Joseph, and Jos´ e Soares. On sparse spanners of weighted graphs. Discrete & Computational Geometry , 9(1):81–100, 1993. doi:10.1007/BF02189308

    doi:10.1007/bf02189308 1993

  7. [6]

    Bundling-aware graph drawing

    Daniel Archambault, Giuseppe Liotta, Martin N¨ ollenburg, Tommaso Piselli, Alessandra Tappini, and Markus Wallinger. Bundling-aware graph drawing. In Proc. GD 2024 , volume 320, pages 15:1–15:19. LZI Dagstuhl, 2024. doi:https://doi.org/10.4230/LIPIcs.GD.2024.15

    doi:10.4230/lipics.gd.2024.15 2024

  8. [7]

    New constructions of ( α, β)- spanners and purely additive spanners

    Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, and Seth Pettie. New constructions of ( α, β)- spanners and purely additive spanners. In Proc. ACM-SIAM SODA 2005 , page 672–681. SIAM, 2005

    work page 2005

Show all 51 references
  1. [8]

    Additive spanners and ( α, β)- spanners

    Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, and Seth Pettie. Additive spanners and ( α, β)- spanners. ACM Transactions on Algorithms , 7(1), 2010. doi:10.1145/1868237.1868242

    2010

  2. [9]

    Approximation algorithms for spanner problems and directed steiner forest

    Piotr Berman, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova, and Grigory Yaroslavtsev. Approximation algorithms for spanner problems and directed steiner forest. Information and Computation , 222:93–107, 2013. ICALP 2011. doi:https://doi.org/10.1016/j.ic.2012.10.007

    2013 doi

  3. [10]

    Fritz B¨ okler, Markus Chimani, Henning Jasper, and Mirko H. Wagner. Exact minimum weight spanners via column generation. In Proc. Algorithms–ESA 2024, volume 308 of LIPIcs, pages 30:1–30:17. LZI Dagstuhl,

    2024

  4. [11]

    New sparseness results on graph spanners

    Barun Chandra, Gautam Das, Giri Narasimhan, and Jos´ e Soares. New sparseness results on graph spanners. In Proc. SoCG 1992, pages 192–201. ACM, 1992. doi:http://dx.doi.org/10.1142/S0218195995000088

    1992 doi

  5. [12]

    New additive spanners

    Shiri Chechik. New additive spanners. In Proc. ACM-SIAM SODA 2013 , page 498–512. SIAM, 2013. doi:https://doi.org/10.1137/1.9781611973105.36

    2013 doi

  6. [13]

    Approx- imation algorithms for nonuniform buy-at-bulk network design

    Chandra Chekuri, Mohammad Taghi Hajiaghayi, Guy Kortsarz, and Mohammad R Salavatipour. Approx- imation algorithms for nonuniform buy-at-bulk network design. SIAM Journal on Computing , 39(5):1772– 1798, 2010. doi:https://doi.org/10.1137/090750317

    2010 doi

  7. [14]

    Network design problems with bounded distances via shallow- light steiner trees

    Markus Chimani and Joachim Spoerhase. Network design problems with bounded distances via shallow- light steiner trees. In Proc. STACS 2015 , volume 30 of LIPIcs, pages 238–248. LZI Dagstuhl, 2015. doi:10.4230/LIPIcs.STACS.2015.238

    2015 doi

  8. [15]

    Spanner approximations in practice

    Markus Chimani and Finn Stutzenstein. Spanner approximations in practice. In Proc. Algorithms–ESA 2022, volume 244 of LIPIcs, pages 37:1–37:15. LZI Dagstuhl, 2022. doi:10.4230/LIPIcs.ESA.2022.37

    2022 doi

  9. [16]

    Approximating spanners and directed steiner forest: Upper and lower bounds

    Eden Chlamt´ aˇ c, Michael Dinitz, Guy Kortsarz, and Bundit Laekhanukit. Approximating spanners and directed steiner forest: Upper and lower bounds. ACM Transactions on Algorithms , 16(3), 2020. doi: 10.1145/3381451

    2020 doi

  10. [17]

    Sparse sourcewise and pairwise distance preservers

    Don Coppersmith and Michael Elkin. Sparse sourcewise and pairwise distance preservers. SIAM Journal on Discrete Mathematics , 20(2):463–501, 2006. doi:https://doi.org/10.1137/050630696. 11

    2006 doi

  11. [18]

    Label cover instances with large girth and the hardness of approximating basic k-spanner

    Michael Dinitz, Guy Kortsarz, and Ran Raz. Label cover instances with large girth and the hardness of approximating basic k-spanner. ACM Transactions on Algorithms , 12(2):1–16, 2015. doi:https://doi. org/10.1145/2818375

    2015 doi

  12. [19]

    Directed spanners via flow-based linear programs

    Michael Dinitz and Robert Krauthgamer. Directed spanners via flow-based linear programs. In Proc. STOC 2011 , page 323–332. ACM, 2011. doi:10.1145/1993636.1993680

    2011

  13. [20]

    Approximating low-stretch spanners

    Michael Dinitz and Zeyu Zhang. Approximating low-stretch spanners. In Proc. ACM-SIAM SODA 2016 , pages 821–840. SIAM, 2016. doi:https://doi.org/10.1137/1.9781611974331.ch59

    2016 doi

  14. [21]

    Design networks with bounded pairwise distance

    Yevgeniy Dodis and Sanjeev Khanna. Design networks with bounded pairwise distance. In Proc. STOC 1999, pages 750–759. ACM, 1999. doi:https://doi.org/10.1145/301250.301447

    1999

  15. [22]

    Computing almost shortest paths

    Michael Elkin. Computing almost shortest paths. ACM Transactions on Algorithms , 1(2):283–323, 2005. doi:10.1145/1103963.1103968

    2005

  16. [23]

    Almost shortest paths and PRAM distance oracles in weighted graphs

    Michael Elkin, Yuval Gitlitz, and Ofer Neiman. Almost shortest paths and PRAM distance oracles in weighted graphs. arXiv preprint 1907.11422, 2019. doi:https://doi.org/10.48550/arXiv.1907.11422

    1907 doi arXiv

  17. [24]

    Improved weighted additive spanners

    Michael Elkin, Yuval Gitlitz, and Ofer Neiman. Improved weighted additive spanners. Distributed Com- puting, 36(3):385–394, 2023. doi:https://doi.org/10.1007/s00446-022-00433-x

    2023 doi

  18. [25]

    Light spanners

    Michael Elkin, Ofer Neiman, and Shay Solomon. Light spanners. SIAM Journal on Discrete Mathematics , 29(3):1312–1321, 2015

    2015

  19. [26]

    (1+ ε,β)-spanner constructions for general graphs

    Michael Elkin and David Peleg. (1+ ε,β)-spanner constructions for general graphs. In Proc. STOC 2001 , page 173–182. ACM, 2001. doi:10.1145/380752.380797

    2001

  20. [27]

    The hardness of approximating spanner problems

    Michael Elkin and David Peleg. The hardness of approximating spanner problems. Theory of Computing Systems, 41(4):691–729, 2007. doi:https://doi.org/10.1007/s00224-006-1266-2

    2007 doi

  21. [28]

    Extremal problems in graph theory

    Paul Erd¨ os. Extremal problems in graph theory. In Proc. Symposium on Theory of Graphs and its Applications, page 2936, 1963

    1963

  22. [29]

    Computers and Intractability: A Guide to the Theory of NP-Completeness

    Michael Robert Garey and David Stifler Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. A Series of Books in the Mathematical Sciences. W. H. Freeman and Company, New York, 1979

    1979

  23. [30]

    A polylogarithmic approximation algorithm for the group steiner tree problem

    Naveen Garg, Goran Konjevod, and Ramamoorthi Ravi. A polylogarithmic approximation algorithm for the group steiner tree problem. Journal of Algorithms , 37(1):66–84, 2000. doi:https://doi.org/10. 1006/jagm.2000.1096

  24. [31]

    Lightweight near-additive spanners

    Yuval Gitlitz, Ofer Neiman, and Richard Spence. Lightweight near-additive spanners. In WG 2024, Revised Selected Papers, page 236–250. Springer Nature, 2024. doi:10.1007/978-3-031-75409-8_17

    2024 doi

  25. [32]

    Improved NP-hardness results for the minimum t-spanner problem on bounded-degree graphs

    Renzo G´ omez, Fl´ avio Keidi Miyazawa, and Yoshiko Wakabayashi. Improved NP-hardness results for the minimum t-spanner problem on bounded-degree graphs. Theoretical Computer Science, 947:113691, 2023. doi:https://doi.org/10.1016/j.tcs.2023.113691

    2023

  26. [34]

    Using light spanning graphs for passenger assignment in public transport

    Irene Heinrich, Olli Herrala, Philine Schiewe, and Topias Terho. Using light spanning graphs for passenger assignment in public transport. In ATMOS 2023, volume 115 of OASIcs, pages 2:1–2:16. LZI Dagstuhl,

    2023

  27. [35]

    Multi-criteria approximation schemes for the resource constrained shortest path problem

    Mark´ o Horv´ ath and Tam´ as Kis. Multi-criteria approximation schemes for the resource constrained shortest path problem. Optimization Letters , 12(3):475–483, 2018. doi:https://doi.org/10.1007/ s11590-017-1212-z

    2018

  28. [36]

    Additive spanners: A simple construction

    Mathias Bæk Tejs Knudsen. Additive spanners: A simple construction. In Scandinavian Workshop on Algorithm Theory, pages 277–281. Springer, 2014. doi:https://doi.org/10.1007/978-3-319-08404-6_ 24. 12

    2014 doi

  29. [37]

    On the hardness of approximating spanners

    Guy Kortsarz. On the hardness of approximating spanners. Algorithmica, 30:432–450, 2001. doi:https: //doi.org/10.1007/s00453-001-0021-y

    2001 doi

  30. [38]

    Generating sparse 2-spanners

    Guy Kortsarz and David Peleg. Generating sparse 2-spanners. Journal of Algorithms, 17(2):222–236, 1994. doi:https://doi.org/10.1006/jagm.1994.1032

    1994

  31. [39]

    On the minimum-cardinality-bounded- diameter and the bounded-cardinality-minimum-diameter edge addition problems

    Chung-Lun Li, S Thomas McCormick, and David Simchi-Levi. On the minimum-cardinality-bounded- diameter and the bounded-cardinality-minimum-diameter edge addition problems. Operations Research Letters, 11(5):303–308, 1992. doi:https://doi.org/10.1016/0167-6377(92)90007-P

    1992 doi

  32. [40]

    Additive graph spanners

    Arthur L Liestman and Thomas C Shermer. Additive graph spanners. Networks, 23(4):343–363, 1993. doi:https://doi.org/10.1002/net.3230230417

    1993 doi

  33. [41]

    Lorenz and Danny Raz

    Dean H. Lorenz and Danny Raz. A simple efficient approximation scheme for the restricted shortest path problem. OPERRL, 28(5):213–219, 2001. doi:10.1016/S0167-6377(01)00069-4

    2001 doi

  34. [42]

    Proximity-preserving labeling schemes and their applications

    David Peleg. Proximity-preserving labeling schemes and their applications. In WG 1999 , volume 1665 of LNCS, pages 30–41. Springer, 1999. doi:https://doi.org/10.1007/3-540-46784-X_5

    1999 doi

  35. [43]

    Sch¨ affer

    David Peleg and Alejandro A. Sch¨ affer. Graph spanners. Journal of graph theory , 13(1):99–116, 1989. doi:10.1002/jgt.3190130114

    1989 doi

  36. [44]

    David Peleg and Jeffrey D. Ullman. An optimal synchronizer for the hypercube. In Proc. PODC 1987 , pages 77–85. ACM, 1987. doi:10.1145/41840.41847

    1987

  37. [45]

    Construction of minimum-weight spanners

    Mikkel Sigurd and Martin Zachariasen. Construction of minimum-weight spanners. In Proc. Algorithms– ESA 2004 , pages 797–808. Springer, 2004. doi:10.1007/978-3-540-30140-0_70

    2004 doi

  38. [46]

    Approximate distance oracles

    Mikkel Thorup and Uri Zwick. Approximate distance oracles. Journal of the ACM , 52(1):1–24, 2005. doi:10.1145/1044731.1044732

    2005

  39. [47]

    Faster edge-path bundling through graph spanners

    Markus Wallinger, Daniel Archambault, David Auber, Martin N¨ ollenburg, and Jaakko Peltonen. Faster edge-path bundling through graph spanners. Computer Graphics Forum , 42(6):e14789, 2023. doi:10. 1111/CGF.14789

    2023

  40. [48]

    On strong np-completeness of rational problems

    Dominik Wojtczak. On strong np-completeness of rational problems. In Proc. CSR 2018, volume 10846 of LNCS, pages 308–320, 2018. doi:https://doi.org/10.1007/978-3-319-90530-3_26

    2018 doi

  41. [49]

    Woodruff

    David P. Woodruff. Lower bounds for additive spanners, emulators, and more. In IEEE FOCS 2006 , pages 389–398. IEEE, 2006. doi:10.1109/FOCS.2006.45. 13 APPENDIX A. Error in [21] In [21], the authors give a (sound) O(n log α)-approximation for directed unit-length multiplicativ...

    2006 doi

  42. [2023]

    doi:10.4230/OASIcs.ATMOS.2023.2

    2023 doi

  43. [2024]

    doi:10.4230/LIPIcs.ESA.2024.30

    2024 doi

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.