Data Structures and Algorithms · arXiv:2611.17201 v1 · submitted 12 Nov 2026 · 46 references
A Little Length Slack Goes a Long Way in Planar Length-Constrained Network Design
The paper says
“Problems in length-constrained network design ask for min-cost subgraphs connecting k input vertex pairs by paths of length at most h.”
more of the abstract
Algorithms that instead connect these pairs by paths of length at most βh are said to have length slack β. Recent work has shown that poly-time polylogarithmic approximations with polylogarithmic length slack are possible for a broad class of both directed and multicommodity length-constrained network design problems on planar graphs. We give the first poly-time polylogarithmic approximations with O(1) length slack for these problems on planar graphs. In particular, for the length-constrained setting, we give LP-competitive algorithms for planar graphs with length slack 1 + ε and approximation ratios of O(log2k/ε) for directed Steiner tree and O(log5k/ε2) for (undirected) Steiner forest. Similarly, for length-constrained directed Steiner forest, we give an O(log6k/ε) approximation on planar graphs with length slack 6 + ε. Our approach is based on a novel charging argument that charges the cost of our solution to the length of the LP and the length of our solution to the cost of the LP. We complement these algorithms with hardness results that separate planar and general graphs for both forest problems: under standard complexity assumptions, we rule out polylogarithmic approximations on general graphs with length slack below 3.
from the abstract
Pith says
Machine review · deepseek-v4-flash · 13 Nov 2026 · what was read was not recorded · not checked by a person
It can be wrong. Challenge this review or reply to it.
Holds up, with conditions. Serious theory paper that likely resolves the stated O(1)-slack open questions; the LC-DST pipeline is clean and checkable, while LC-SF is the dense part a referee must actually sit with. This line is wrong
4 major objections · 7 minor
How often objections from reviews like this one are right: not yet measured
Not checked: figures, code, what the 46 references say.
The paper says, at §4.2, Lemma 4.7 and surrounding text
The review did not quote this passage.
Pith says: Objection 1 of 4 · major
The bound on the number of chunks containing a given vertex is O(log^2 k/(ε log τ)). However, the derivation of the O(1/ε) factor per separator path relies on Lemma 4.3, which states that every path in bucket B_j has mixture cost at most 2γ_j.
more of objection 1
Lemma 4.3 itself depends on the preprocessing step (Lemma 4.2) that discards paths of cost ≥4X and scales the remaining flow by 4/3. After scaling, the LP value X is replaced by (4/3)X, but the bucket definitions γ_j = (X/k) τ^j are not updated accordingly in the text. If the scaling changes the effective γ_j, the bound w_j(p) ≤ 2γ_j may no longer hold for all p in B_j, potentially increasing the number of chunks per vertex beyond O(1/ε). The authors acknowledge the scaling (line after Lemma 4.2: 'the scaled fractional solution supports a flow of 1 between demand pairs') but do not explicitly recompute the mixture-cost bound after scaling. This could affect the O(log^5 k/ε^2) approximation ratio for LC-SF. The authors should clarify whether the bucket definitions are adjusted after scaling, or provide a justification that the bound remains valid.
The paper says, at §4.2, Lemma 4.8
The review did not quote this passage.
Pith says: Objection 2 of 4 · major
The proof of Lemma 4.8 states that 'the recursive process continues until all terminal pairs are separated, therefore every path in P_hi must intersect the separator at some level of recursion.' However, the recursion is on the graph after removing separator paths, and the separator paths are defined with respect to an arbitrary root r.
more of objection 2
It is not guaranteed that every s_i-t_i path in the LP support intersects the separator at some level, because the separator is defined from a fixed root r, not from the terminal pairs. The recursion only separates terminals that lie in different components after removing the separator paths, but a path could potentially avoid all separator paths if it stays entirely within a component that is never separated. The authors should justify that the separator hierarchy eventually separates all terminal pairs, or adjust the argument to account for paths that may not intersect any separator.
The paper says, at §3.2, Lemma 3.9
The review did not quote this passage.
Pith says: Objection 3 of 4 · major
The proof of Lemma 3.9 charges the cost of each shortcut to the improvement in length to reach the final vertex z of the separator. However, the definition of L_i uses d_T(r, a_i) + l(P_i) + l(Q[v_i, z]), where d_T(r, a_i) is the distance in the current solution T before buying P_i.
more of objection 3
The inequality c(P_i)/(X_H log k) ≤ (L_{i-1} - L_i)/(ε h) relies on the assumption that the existing path to v_i before buying P_i is exactly the path through the previous shortcut and the separator subpath. But the solution T may contain multiple paths to v_i; the distance d_T(r, v_i) is the minimum over all paths, not necessarily the one through the previous shortcut. If there is a shorter path to v_i that does not go through the previous shortcut, then the inequality may not hold because the improvement Δ_i could be smaller than claimed. The authors should argue that the path through the previous shortcut is indeed the shortest path to v_i in T before buying P_i, or provide a more careful charging argument that does not rely on this assumption.
The paper says, at §4.1, Step 2: Constructing Candidate Rooted Solutions
The review did not quote this passage.
Pith says: Objection 4 of 4 · major
The construction of candidate solutions uses the median distance a_i from s_i to chunk C along paths in P_hi ∩ P_C, weighted by f_p. The median is defined such that at least half the flow from s_i to C has length ≤ a_i, and at least half the flow from C to t_i has length ≤ h - a_i.
more of objection 4
However, the flow paths in P_hi ∩ P_C are s_i-t_i paths, not s_i-C or C-t_i paths. The subpaths from s_i to C and from C to t_i are not necessarily independent; the flow on a path p is counted in both the s_i-C and C-t_i parts. The median condition ensures that there is a set of paths with total flow at least β/2 from s_i to C of length ≤ a_i, and similarly from C to t_i of length ≤ h - a_i, but these sets may be different. The LC-ST algorithm then connects s_i' and t_i' to the root r_C, but the paths from s_i' to r_C and from r_C to t_i' may use different flow paths, and the concatenation may not correspond to a single s_i-t_i path of length ≤ h. The authors should clarify how the median trick guarantees a feasible s_i-t_i path of length ≤ (1+ε)h, given that the two halves may come from different flow paths.
7 minor objections
The paper says, at Abstract
Pith says: minor objection 1 of 7
The abstract states 'We give the first poly-time polylogarithmic approximations with O(1) length slack for these problems on planar graphs.' This is accurate for the directed and multicommodity problems, but for LC-ST on planar graphs, Hershkowitz and Huang [33] already gave an O(log^{1+ε} k) approximation with 1+ε length slack. The authors should clarify that 'these problems' refers to the directed and multicommodity variants, or adjust the wording to avoid overclaiming.
The paper says, at §1.1, Table 1
Pith says: minor objection 2 of 7
The table lists the LC-DST result from [12] as having cost O(log^2 k) and length slack O(log k), but the text in §1.1 says 'O(log^2 k) LP-competitive approximation with length slack O(log k) for LC-DST'. The table should include a note that the [12] result is LP-competitive, or the text should be consistent.
more of objection 2
Currently the table says 'No' for LP-competitive for the first [12] row, but the second [12] row says 'Yes'. This is confusing; the authors should clarify which result is which.
show 5 more
The paper says, at §3.1, Definition 3.2
Pith says: minor objection 3 of 7
The hierarchical mixture metric w_H(e) = l(e)/(ε h) + c(e)/(X_H log k) uses X_H, which is defined as the sum of c(e) x_e over edges in region H. However, after buying separator edges, their costs are set to 0 for the remainder of the algorithm, but X_H remains its original value. This is stated in the text, but it would be helpful to explicitly note that X_H is not updated after separator edges are bought, to avoid confusion.
The paper says, at §4.1, Algorithm 5
Pith says: minor objection 4 of 7
In Algorithm 5, the recursion on connected components of G \(Q_1 ∪ Q_2 ∪ Q_3) is described, but it is not specified how the root r is chosen for each recursive call. The separator lemma (Lemma 2.3) requires a root, but the algorithm says 'from an arbitrary root r ∈ V'.
more of objection 4
If the root is chosen arbitrarily, the separator paths may not be balanced with respect to the terminal pairs in that component. The authors should specify how the root is chosen in each recursive call, or argue that any root works.
The paper says, at §5, Theorem 1.4
Pith says: minor objection 5 of 7
The hardness result for LC-SF states that there is no polynomial time 2^{log^{1-ε} k} approximation with length slack β < 3. However, the reduction uses a constant δ that depends on β, and the length constraint h = 1 + 4δ. The hardness is for general graphs, not planar graphs. The authors should explicitly state that the hardness is for general graphs, as the rest of the paper focuses on planar graphs.
The paper says, at §6, Acknowledgements
Pith says: minor objection 6 of 7
The AI disclosure is unusual but appreciated. However, the authors state that GPT-6 Astra improved the LC-DST bound from O(log^4 k/ε^3) to O(log^2 k/ε) and provided the path preprocessing and flow threshold arguments for LC-SF. This raises questions about the novelty and attribution of the key ideas. The authors should ensure that the contributions of the AI are clearly delineated and that the authors take full responsibility for correctness, as they do.
The paper says, at General
Pith says: minor objection 7 of 7
The paper uses the term 'LP-competitive' to mean that the cost of the solution is bounded by a polylogarithmic factor times the LP optimum. This is standard, but the authors should define it explicitly in the preliminaries, as it is used throughout.
What would settle it
Recompute Lemma 4.3 and Lemma 4.7 after the 4/3 scaling: define X' = (4/3)X, γ'_j = (X'/k) τ^j, and verify that for every path p in the scaled bucket Bj, w'_j(p) ≤ 2γ'_j still holds. If the inequality fails, recompute the chunk-per-vertex bound in Lemma 4.7 and the total weighted cost in Lemma 4.11; if the exponent of log k increases, the O(log^5 k/ϵ^2) claim may be invalid.
from the skeptic's reading
How the review went
4 readings by deepseek-v4-flash · 13 Nov 2026
- Reader holds up, with conditions
- Skeptic partly agrees
- Editor wrote the verdict above
- Referee major revision: 4 major objections, 7 minor
Not run on this paper: the simulated authors' defence.
Pith did not check this review's objections against the paper.
The review in full
The review in brief, machine-written
This is a serious theory paper and on my reading the main results are real. The headline is LC-DST at O(log2 k/epsilon) with 1+epsilon slack, LP-competitive: it improves Hershkowitz-Huang's O(log3 k/epsilon) undirected LC-ST result and moves to the directed setting, and it tightens Chekuri-Jain's O(log k) slack down to 1+epsilon. The cost-to-length / length-to-cost charging is the genuinely new idea, and I traced it end to end. Lemma 3.8's separator bounds follow from the pruning radius; Lemma 3.9's shortcut cost telescopes against cumulative length improvement toward the separator endpoint with L1 - Lm <= O(h); the canonical-path argument closes the length budget at h + epsilon h. I found no error in that pipeline.
LC-SF is where the work is, and it is dense. The stress-test note flags a scaling inconsistency: after Lemma 4.2 discards paths of cost >= 4X and rescales the flow by 4/3, are the bucket boundaries gamma_j = (X/k) tauj stale? I went back to the text and I think that concern does not land. Bucketing is by actual path cost, which is invariant to flow scaling; Lemma 4.3's bound wj(p) <= 2 gamma_j uses c(p) <= gamma_j and l(p) <= h, both unchanged. The 4/3 enters only the final constant, and the paper says exactly that at the end of Section 4.2. I would not hold that against the authors.
What I would want a referee to sit with: the per-vertex chunk-membership bound in Lemma 4.7, the covering argument in Lemma 4.8, and the weighted averaging hinge (Lemma 4.6 into Lemma 4.11). Those constants are load-bearing and not all fully instantiated. I could not re-derive every inequality in Section 4.2 in one sitting; nothing contradicted itself, but it deserves a careful reader. The LC-DSF result rests on Lemma A.1 quoted from Chekuri-Jain [12], which is published, so that is supported rather than a soft spot. The AI disclosure is honest and argues for a watchful referee, not distrust.
Verdict: send to review. I would want Section 4 checked before signing off, but the LC-DST result alone is a solid contribution worth the reading group.
The strongest objection
The LC-SF cost analysis (Section 4.2) depends on a chain of inequalities whose constants are not fully instantiated. The critical step is Lemma 4.7, which bounds the number of chunks containing a given vertex by O(log^2 k/(ϵ log τ)). This bound multiplies three sources: (i) O(1/ϵ) chunks per separator path (derived from the mixture-cost bound of 4γ_j on the subpath between the first and last intersection points), (ii) O(log k) levels of recursion, and (iii) O(log k / log τ) buckets. The derivation of (i) uses Lemma 4.3, which states that every path in bucket Bj has mixture cost at most 2γ_j. However, Lemma 4.3 relies on the preprocessing step (Lemma 4.2) that discards paths of cost ≥4X and scales the remaining flow by 4/3. After scaling, the LP value X is replaced by (4/3)X, but the bucket definitions (γ_j = (X/k) τ^j) are not updated accordingly in the text. If the scaling changes the effective γ_j, the bound w_j(p) ≤ 2γ_j may no longer hold for all p in Bj, potentially increasing the number of chunks per vertex beyond O(1/ϵ). The subsequent weighted averaging (Lemma 4.6) and the bound on total weighted cost (Lemma 4.11) depend on the chunk-membership bound of Lemma 4.7; if that bound is off by a factor, the final O(log^5 k/ϵ^2) approximation ratio could be understated. The authors acknowledge the preprocessing step (line after Lemma 4.2: 'the scaled fractional solution supports a flow of 1 between demand pairs') but do not explicitly recompute the mixture-cost bound after scaling. This is a concrete gap that could affect the correctness of the LC-SF cost guarantee.
The reader identified the LC-SF small-intersection property and the bucketing as the weakest assumption, which aligns with my concern. However, the reader did not flag the specific interaction between the 4/3 scaling and the mixture-cost bound in Lemma 4.3, which is the precise technical gap I see. The reader's verdict is CONDITIONAL, which I agree with; I do not see a reason to change it to REJECT because the gap may be fixable by adjusting constants or by redefining γ_j after scaling. The paper's own disclosure of AI assistance and the acknowledged complexity of the LC-SF proof further support a CONDITIONAL verdict. I therefore recommend UNCHANGED (i.e., the reader's CONDITIONAL stands). The agreement_with_reader is 'partial' because the reader's weakest_assumption is about the small-intersection property, which is related but not identical to the scaling-mixture interaction I highlight.
The referee's report
If correct, these results resolve open questions about the existence of O(1)-slack polylogarithmic approximations for directed and multicommodity length-constrained problems on planar graphs. The LP-competitive bounds for LC-DST and LC-SF also give the first upper bounds on the integrality gaps of natural LP relaxations for these problems on planar graphs. The techniques, particularly the cost-to-length and length-to-cost charging framework, are novel and may be of independent interest. The hardness results separate planar from general graphs, which is a clean contribution.
Pith's reading of the paper (a machine's summary, not the authors')
Network design problems ask how to build a cheap network that connects specified points. The length-constrained versions add the requirement that each connection is made by a path that is short, not just cheap. On general graphs these problems are very hard, and prior good approximations were allowed to stretch the path-length limit by a logarithmic factor. This paper works on planar graphs, meaning graphs that can be drawn on a flat surface without edges crossing, and shows that for the directed and multi-pair versions the stretch can be reduced to a constant, and even to 1+epsilon for the single-customer directed version.
The core technical trick is a charging argument. When the algorithm buys a shortcut path, it argues that the cost of that shortcut is paid for by the improvement it creates in the total path length to the far end of the separator. Conversely, when the resulting root-terminal paths are too long, each extra unit of length is charged to the cost of a comparison path lying inside the same region. Since the comparison paths are bounded by the linear programming relaxation of the problem, the charges stay small and the length budget closes at (1+epsilon) times the allowed length. The multi-pair version routes demands through junction points, using a median-distance trick so each endpoint keeps half of its flow under a separate length budget.
The paper also proves these problems are genuinely easier on planar graphs. By reducing from the Min-Rep problem, it shows that on general graphs no polylogarithmic approximation is possible with length slack below 3 for Steiner forest, and no length slack at all for its directed version, assuming standard complexity conjectures.
Core claim. Theorem 1.1: for any epsilon in (0,1), there is an LP-competitive O(log^2 k / epsilon) approximation with 1+epsilon length slack for LC-DST in planar graphs, running in poly(n,1/epsilon). Companion Theorems 1.2 and 1.3 give an LP-competitive O(log^5 k / epsilon^2) approximation with 1+epsilon slack for LC-SF and an O(log^6 k / epsilon) approximation with 6+epsilon slack for LC-DSF. If correct, these are the first O(1)-slack polylogarithmic approximations for the directed and multicommodity length-constrained problems on planar graphs, resolving the open questions posed in the introduction.
The premise it rests on. The LC-SF construction rests on the claim (end of Section 1.2.2) that for any separator path Q and terminal pair (s_i,t_i), the LP's s_i-t_i flow intersects Q only on a small subpath, with the paper's own acknowledged caveat that this holds only when all flow paths have roughly the same cost, handled by bucketing paths into (X/k, 4X) cost buckets. This small-intersection property drives the chunk charging (Lemma 4.7's O(log^2 k/(epsilon log tau)) per-vertex chunk-membership bound) and the flow-threshold covering Lemma 4.8; if flow paths spanned long separator subpaths, the chunk count and hence the log^5 k bound would inflate. The fragile step is the fixed-proportion preprocessing (dropping paths of cost at least 4X and scaling the remainder by 4/3, Lemma 4.2), which must preserve at least 3/4 unit of flow per demand.
Check this review
Pith stored no record of this review's passes and took no fingerprint of it. Reviews made by code from 13 Nov 2026 on carry both.
How often reviews like this one are right
Reviews like this one: written by deepseek-v4-flash, where what was read was not recorded.
How often objections from reviews like this one are right: not yet measured
Reviews by people
This review was written by a machine. No person has reviewed this paper on Pith yet. A scientist listed on Pith can review it for a fee, and their review is published here whatever it concludes.
The paper
Abstract
Problems in length-constrained network design ask for min-cost subgraphs connecting k input vertex pairs by paths of length at most h. Algorithms that instead connect these pairs by paths of length at most βh are said to have length slack β. Recent work has shown that poly-time polylogarithmic approximations with polylogarithmic length slack are possible for a broad class of both directed and multicommodity length-constrained network design problems on planar graphs. We give the first poly-time polylogarithmic approximations with O(1) length slack for these problems on planar graphs. In particular, for the length-constrained setting, we give LP-competitive algorithms for planar graphs with length slack 1 + ε and approximation ratios of O(log2k/ε) for directed Steiner tree and O(log5k/ε2) for (undirected) Steiner forest. Similarly, for length-constrained directed Steiner forest, we give an O(log6k/ε) approximation on planar graphs with length slack 6 + ε. Our approach is based on a novel charging argument that charges the cost of our solution to the length of the LP and the length of our solution to the cost of the LP. We complement these algorithms with hardness results that separate planar and general graphs for both forest problems: under standard complexity assumptions, we rule out polylogarithmic approximations on general graphs with length slack below 3.
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. No sentence in this record was written by a model.
abstract compiled · 2026-11-14
The authors' main claim, as the classifier picked it out 1.00
“We give the first poly-time polylogarithmic approximations with $O(1)$ length slack for these problems on planar graphs.”
How the main claim is stated: asserted 1.00
What the abstract itself states, as probabilities: claims first 0.93 · states limitation 0.46 · human participants 0.01 · controlled comparison 0.06 · randomized assignment 0.01 · states quantitative result 0.99 · compares with prior results 0.95 · mentions code or data availability 0.02
The abstract, sentence by sentence
This table labels the abstract only (arXiv listing abstract v1). The number is the probability the classifier gave the label.
| Sentence | Role | The authors' own work | States the main conclusion | Strength |
|---|---|---|---|---|
| Problems in length-constrained network design ask for min-cost subgraphs connecting $k$ input vertex pairs by paths of length at most $h$. | background 1.00 | 0.05 | 0.02 | asserted 0.99 |
| Algorithms that instead connect these pairs by paths of length at most $\beta h$ are said to have length slack $\beta$. | background 1.00 | 0.07 | 0.03 | asserted 0.98 |
| Recent work has shown that poly-time polylogarithmic approximations with polylogarithmic length slack are possible for a broad class of both directed and multicommodity length-constrained network design problems on planar graphs. | background 0.97 | 0.04 | 0.05 | asserted 0.75 |
| We give the first poly-time polylogarithmic approximations with $O(1)$ length slack for these problems on planar graphs. | contribution 0.95 | 0.97 | 0.85 | asserted 1.00 |
| In particular, for the length-constrained setting, we give LP-competitive algorithms for planar graphs with length slack $1+\epsilon$ and approximation ratios of $O(\log^2 k/\epsilon)$ for directed Steiner tree and $O(\log^5 k/\epsilon^2)$ for (undirected) Steiner forest. | result 0.73 | 0.97 | 0.31 | asserted 1.00 |
| Similarly, for length-constrained directed Steiner forest, we give an $O(\log^6 k/\epsilon)$ approximation on planar graphs with length slack $6+\epsilon$. | result 0.79 | 0.97 | 0.11 | asserted 1.00 |
| Our approach is based on a novel charging argument that charges the cost of our solution to the length of the LP and the length of our solution to the cost of the LP. | method 1.00 | 0.94 | 0.04 | asserted 1.00 |
| We complement these algorithms with hardness results that separate planar and general graphs for both forest problems: under standard complexity assumptions, we rule out polylogarithmic approximations on general graphs with length slack below $3$. | result 0.67 | 0.92 | 0.12 | asserted 0.96 |
What kind of paper the classifier reports this is: method or tool 0.51 · evidence from proof or derivation 1.00
What was examined, and what was not
Sources read
- arXiv listing abstract v1
Not examined
- full text
- figures and tables
- references and citing sentences
- relations to other papers
Levels run
- P abstract
Not run
- S sections
- T body sentences
- C citations
- R cross-paper relations
How the labels were made
Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-11-14: 1 request, 6,506 input tokens.
Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. This record as JSON
Figures (10)
Figures are the authors', reproduced from the paper.
References (46)
- [12] Chandra Chekuri and Rhea Jain. Length-Constrained Network Design in Planar Digraphs. InAp- proximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX- /RANDOM), volume 392, pages 15:1–15:24, 2026 on Pith
- [1] Ajit Agrawal, Philip Klein, and Ramamoorthi Ravi. When trees collide: An approximation algorithm for the generalized steiner problem on networks. InAnnual ACM Symposium on Theory of Computing (STOC), pages 134–144, 1991 on Pith
- [2] Ali Ahmadi, Iman Gholami, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, and Mohammad Mah- 29 davi. Breaking a long-standing barrier: 2-εapproximation for steiner forest. InSymposium on Founda- tions of Computer Science (FOCS), pages 373–444, 2025 on Pith
- [3] Ibrahim Akg¨ un and Barbaros C ¸ Tansel. New formulations of the hop-constrained minimum spanning tree problem via miller–tucker–zemlin constraints.European Journal of Operational Research, 212(2): 263–276, 2011 on Pith
- [4] Baruch Awerbuch and Yossi Azar. Buy-at-bulk network design. InSymposium on Foundations of Computer Science (FOCS), pages 542–547, 1997 on Pith
- [5] Amy Babay, Michael Dinitz, and Zeyu Zhang. Characterizing Demand Graphs for (Fixed-Parameter) Shallow-Light Steiner Network. InIARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), volume 122, pages 33:1–33:22, 2018 on Pith
- [6] Anantaram Balakrishnan and Kemal Altinkemer. Using a hop-constrained model to generate alternative communication network design.ORSA Journal on Computing, 4(2):192–205, 1992. doi: 10.1287/ijoc.4. 2.192 on Pithdoi:10.1287/ijoc.4
- [7] Jaros law Byrka, Fabrizio Grandoni, Thomas Rothvoß, and Laura Sanit` a. Steiner tree approximation via iterative randomized rounding.Journal of the ACM (JACM), 60(1):1–33, 2013 on Pith
- [8] Moses Charikar and Adriana Karagiozova. On non-uniform multicommodity buy-at-bulk network design. InProceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, STOC ’05, pages 176–182, New York, NY, USA, 2005. Association for Computing Machinery. doi: 10.114... on Pithdoi:10.1145/1060590.1060617
- [9] Moses Charikar, Chandra Chekuri, To-Yat Cheung, Zuo Dai, Ashish Goel, Sudipto Guha, and Ming Li. Approximation algorithms for directed steiner problems.Journal of Algorithms, 33(1):73–91, 1999 on Pith
- [10] Chandra Chekuri and Rhea Jain. Approximation Algorithms for Hop Constrained and Buy-At-Bulk Network Design via Hop Constrained Oblivious Routing. InAnnual European Symposium on Algorithms (ESA), volume 308, pages 41:1–41:21, 2024 on Pith
- [11] Chandra Chekuri and Rhea Jain. A polylogarithmic approximation for directed steiner forest in planar digraphs. InAnnual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2095–2110, 2025 on Pith
- [13] Chandra Chekuri, Sanjeev Khanna, and Joseph (Seffi) Naor. A deterministic algorithm for the cost- distance problem. InAnnual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 232–233, 2001 on Pith
- [14] Chandra Chekuri, Mohammad Taghi Hajiaghayi, Guy Kortsarz, and Mohammad R Salavatipour. Ap- proximation algorithms for nonuniform buy-at-bulk network design.SIAM Journal on Computing, 39 (5):1772–1798, 2010 on Pith
- [15] Chandra Chekuri, Rhea Jain, Shubhang Kulkarni, Da Wei Zheng, and Weihao Zhu. From Directed Steiner Tree to Directed Polymatroid Steiner Tree in Planar Graphs. InAnnual European Symposium on Algorithms (ESA), volume 308, pages 42:1–42:19, 2024 on Pith
- [16] Erik D Demaine, MohammadTaghi Hajiaghayi, and Philip N Klein. Node-weighted steiner tree and group steiner tree in planar graphs. InInternational Colloquium on Automata, Languages and Pro- gramming (ICALP), pages 328–340, 2009 on Pith
- [17] 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 (TALG), 12(2):1–16, 2015. 30 on Pith
- [18] Arnold Filtser. Hop-constrained metric embeddings and their applications. InSymposium on Founda- tions of Computer Science (FOCS), pages 492–503, 2022 on Pith
- [19] Willem Fletcher and D Ellis Hershkowitz. Spanning tree embeddings are not much harder than hierar- chical partitions. InAnnual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 5344–5373, 2026 on Pith
- [20] Zachary Friggstad and Ramin Mousavi. An O(log k)-Approximation for Directed Steiner Tree in Planar Graphs. InInternational Colloquium on Automata, Languages and Programming (ICALP), volume 261, pages 63:1–63:14, 2023 on Pith
show 26 more
- [21] Zachary Friggstad and Ramin Mousavi. A Constant-Factor Approximation for Quasi-Bipartite Directed Steiner Tree on Minor-Free Graphs. InApproximation, Randomization, and Combinatorial Optimiza- tion. Algorithms and Techniques (APPROX/RANDOM), volume 275, pages 13:1–13:18, 2023 on Pith
- [22] Michael R Garey and David S Johnson.Computers and intractability, volume 29. W. H. Freeman, 2002 on Pith
- [23] Mohsen Ghaffari, Bernhard Haeupler, and Goran Zuzic. Hop-constrained oblivious routing. InPro- ceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1208–1220, 2021 on Pith
- [24] Rohan Ghuge and Viswanath Nagarajan. Quasi-polynomial algorithms for submodular tree orienteering and directed network design problems.Mathematics of Operations Research, 47(2):1612–1630, 2022 on Pith
- [25] Fabrizio Grandoni, Bundit Laekhanukit, and Shi Li. O (log2 k/log log k)-approximation algorithm for directed steiner tree: a tight quasi-polynomial-time algorithm. InAnnual ACM Symposium on Theory of Computing (STOC), pages 253–264, 2019 on Pith
- [26] Anupam Gupta and Amit Kumar. Greedy algorithms for steiner forest. InAnnual ACM Symposium on Theory of Computing (STOC), pages 871–878, 2015 on Pith
- [27] Anupam Gupta and Vera Traub. Steiner forest: A simplified better-than-2 approximation. InAnnual ACM Symposium on Theory of Computing (STOC), pages 943–954, 2026 on Pith
- [28] Bernhard Haeupler, D Ellis Hershkowitz, and Goran Zuzic. Tree embeddings for hop-constrained net- work design. InAnnual ACM Symposium on Theory of Computing (STOC), pages 356–369, 2021 on Pith
- [29] Bernhard Haeupler, D Ellis Hershkowitz, and Zihan Tan. New structures and algorithms for length- constrained expander decompositions. InSymposium on Foundations of Computer Science (FOCS), pages 1634–1645, 2024 on Pith
- [30] Eran Halperin and Robert Krauthgamer. Polylogarithmic inapproximability. InAnnual ACM Sympo- sium on Theory of Computing (STOC), pages 585–594, 2003 on Pith
- [31] Refael Hassin. Approximation schemes for the restricted shortest path problem.Mathematics of Oper- ations research, 17(1):36–42, 1992 on Pith
- [32] D Ellis Hershkowitz and Richard Z Huang. Simple length-constrained minimum spanning trees. In Symposium on Simplicity in Algorithms (SOSA), pages 341–349, 2025 on Pith
- [33] D Ellis Hershkowitz and Richard Z Huang. Planar length-constrained minimum spanning trees. In Annual ACM Symposium on Theory of Computing (STOC), pages 1528–1539, 2026 on Pith
- [34] Jennifer Iglesias, Rajmohan Rajaraman, R Ravi, and Ravi Sundaram. Plane gossip: Approximating rumor spread in planar graphs. InLatin American Symposium on Theoretical Informatics (LATIN), pages 611–624, 2018 on Pith
- [35] Ken-ichi Kawarabayashi and Anastasios Sidiropoulos. Embeddings of planar quasimetrics into directed ℓ1 and polylogarithmic approximation for directed sparsest-cut. InSymposium on Foundations of Com- puter Science (FOCS), pages 480–491, 2021. 31 on Pith
- [36] M Reza Khani and Mohammad R Salavatipour. Improved approximations for buy-at-bulk and shallow- light k-steiner trees and (k, 2)-subgraph.Journal of Combinatorial Optimization, 31(2):669–685, 2016 on Pith
- [37] Lawrence Kou, George Markowsky, and Leonard Berman. A fast algorithm for steiner trees.Acta Informatica, 15(2):141–145, 1981 on Pith
- [38] Shi Li and Bundit Laekhanukit. Polynomial integrality gap of flow lp for directed steiner tree. InAnnual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3230–3236, 2022 on Pith
- [39] Richard J Lipton and Robert Endre Tarjan. A separator theorem for planar graphs.SIAM Journal on Applied Mathematics, 36(2):177–189, 1979 on Pith
- [40] Madhav V Marathe, Ramamoorthi Ravi, Ravi Sundaram, SS Ravi, Daniel J Rosenkrantz, and Harry B Hunt III. Bicriteria network design problems.Journal of Algorithms, 28(1):142–171, 1998 on Pith
- [41] Adam Meyerson, Kamesh Munagala, and Serge Plotkin. Cost-distance: Two metric network design. In Symposium on Foundations of Computer Science (FOCS), pages 624–630, 2000 on Pith
- [42] F Sibel Salman, Joseph Cheriyan, Ramamoorthi Ravi, and Sairam Subramanian. Approximating the single-sink link-installation problem in network design.SIAM Journal on Optimization, 11(3):595–610, on Pith
- [43] Mikkel Thorup. Compact oracles for reachability and approximate distances in planar digraphs.Journal of the ACM (JACM), 51(6):993–1024, 2004 on Pith
- [44] Alexander Zelikovsky. A series of approximation algorithms for the acyclic directed Steiner tree problem. Algorithmica, 18(1):99–110, 1997 on Pith
- [45] Leonid Zosin and Samir Khuller. On directed Steiner trees. InProceedings of ACM-SIAM SODA, pages 59–63, 2002. A Length-Constrained Directed Steiner Forest We use the modularity of the planar LC-DSF algorithm of Chekuri and Jain [12]. Lemma A.1(Theorem 4.1, Lemma 4.12, and Theo... on Pith
- [2001] Preliminary version in Proc. of SODA 1997 on Pith
Challenges and discussion
Disagree with the review, or know something it missed? Leave a comment, or challenge this review formally: a challenge becomes a permanent entry in this paper's record, and its decision is published here.
Come back by email
A short list of the week's newly reviewed papers. Nothing is sent until you confirm from your inbox, and every email has a link that stops it. No account.
No comments yet.
Sign in to comment