Pith. sign in

REVIEW 3 major objections 3 minor 73 references

Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth

T0 review · 3 major / 3 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read A new parallel algorithm approximates the Held-Karp TSP bound in near-linear work and polylogarithmic depth.

desk verdict Core-sequence framework is a real contribution, but the main theorem leans on an unproven parallel tree-packing primitive; the paper deserves review and needs that gap closed. read the letter →

arxiv 2411.14745 v2 pith:Z6DBQHJM submitted 2024-11-22 cs.DS

Zhuan Khye Koh , Omri Weinstein , Sorrachai Yingchareonthawornchai This is my paper · ORCID
classification cs.DS MSC 68W1068Q2590C0590C27
keywords Held–KarpboundMetricTSPparallelalgorithmmultiplicativeweightsupdatecore-sequencesminimumcutk-edge-connectedspanningsubgraphwork-depthmodel
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

The paper claims a randomized parallel algorithm that, for any undirected graph with n vertices, m edges and positive edge costs, computes a (1+ε)-approximation to the Held–Karp bound—the value of the subtour-elimination LP behind the best TSP approximation algorithms—in Õ(m/$ε^{4}$) work and Õ(1/$ε^{4}$) depth. If true, this is the first algorithm to achieve both nearly linear total work and polylogarithmic parallel depth for this problem; the previous near-linear algorithm was inherently sequential. The same machinery, combined with a known reduction, also solves the k-edge-connected spanning subgraph LP to (1+ε) accuracy in the same complexity. The central novelty is a notion of core-sequences for the parallel multiplicative weights update method, which lets the algorithm clear each MWU epoch by focusing on a short sequence of small sets of near-minimum cuts rather than touching all quadratic many cuts.

What carries the argument

The core object is a core-sequence: for a fixed MWU epoch, an ordered list of subsets of the active columns (here, cuts of weight below (1+ε)λ) such that clearing each subset in turn with the parallel MWU update clears the whole epoch. The paper proves a general theorem that a core-sequence of sets of size at most n and length ℓ clears an epoch in Õ(Σ f(|B_i|) log(|B_i|)/$ε^{2}$) work and Õ(Σ log(|B_i|)/$ε^{2}$) depth, where f is the cost of updating one set. For the Cut Covering LP the authors find core-sequences of length Õ(1) and sets of size Õ(n) by exploiting submodularity and forbidden-matrix structure of approximate minimum cuts on path minors of Karger's tree packing.

What would settle it

Exhibit a graph family where no O(log n) spanning trees produced in O(1) depth and near-linear work can have every (1+ε)-minimum cut 1-or-2-respecting one of the trees, or exhibit an instance where the epoch algorithm's core-sequence length grows super-polylogarithmically.

Watch

Extended reading notes

Core claim

The authors establish that the Cut Covering LP—equivalent to the Held–Karp bound when k=2—can be solved to (1+ε) accuracy by an epoch-based parallel MWU algorithm whose per-epoch work is near-linear and whose depth is polylogarithmic. They prove that every epoch has a core-sequence of length Õ(1) whose sets each have Õ(n) cuts, and that the canonical cut data structure of Chekuri and Quanrud enables each focus operation in near-linear work. For the k-ECSS LP, the same core-sequence technique combined with the range-mapping theorem of Chalermsook et al. yields a (1+ε)-approximate solution in the same complexity, improving the depth exponentially for large k.

Load-bearing premise

The polylogarithmic depth claim rests on the assumption that Karger's tree-packing theorem can be implemented in near-linear work and O(1) depth to output O(log n) spanning trees that capture all (1+ε)-minimum cuts; the paper cites this as a known primitive but gives no parallel algorithm for it.

Editorial extensions

If this is right

  • A (1+ε)-approximation to the Held–Karp bound can be computed in near-linear work with polylog depth, making the bound practically usable in parallel for large sparse graphs.
  • Combining with the reduction of Chalermsook et al. gives a parallel (1+ε)-approximate solver for the k-ECSS LP with the same complexity, and exponentially better depth when k is large.
  • The core-sequence framework generalizes earlier parallel MWU iteration bounds from polylog(nnz(A)) to polylog in the product of core-sequence cardinalities, improving iteration complexity for implicitly defined LPs.
  • Because the Held–Karp bound is a lower bound for TSP, faster parallel approximation of it directly accelerates parallel approximation algorithms for Metric-TSP that rely on the subtour LP.

Reading between the lines

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

  • The core-sequence idea may apply to other packing/covering LPs whose constraint columns have strong combinatorial structure beyond cut problems; a testable extension is survivable network design LPs other than k-ECSS.
  • If the tree-packing primitive is the actual bottleneck, a deterministic or simpler parallel replacement for it would immediately strengthen the practicality of the result.
  • The depth bound Õ(1/ε^4) is independent of graph size, so with enough processors the runtime is governed only by accuracy—a property potentially valuable for very large sparse graphs.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 3 minor

Summary. The paper presents a parallel approximation algorithm for the Cut Covering LP whose optimal value gives the Held-Karp bound for metric TSP, and an extension to the k-edge-connected spanning subgraph LP relaxation. The main technical innovation is a "core-sequence" framework for parallel multiplicative weights update (MWU): instead of updating all active coordinates in an epoch, the algorithm clears a carefully chosen sequence of small subsets. For metric TSP the paper proves the existence of core-sequences of length O(log n) with sets of size O~(n) using Karger tree-packing, forbidden-matrix arguments, path decompositions, and canonical cuts, yielding O~(m/epsilon^4) work and O~(1/epsilon^4) depth for a (1+epsilon)-approximation to the Held-Karp bound (Theorem 1.1). For k-ECSS, the paper uses knapsack-cover constraints and a range-mapping theorem to obtain a similar parallel guarantee (Theorem 1.2). The paper contains detailed proofs of the core-sequence machinery, the path/interval extraction lemmas, and the cut-oracle data structures, and it identifies several external results on which the algorithm depends.

Significance. If the main theorems are correct, this is the first algorithm to approximate the Held-Karp bound in nearly linear work and polylogarithmic depth, answering an open question raised by the sequential algorithm of Chekuri and Quanrud. The core-sequence framework is a genuinely new and broadly applicable tool for parallelizing MWU on implicitly defined packing/covering LPs; the claimed improvement in iteration complexity for such LPs is substantial and of independent interest. The forbidden-matrix arguments used to construct short core-sequences are elegant and, for the most part, carefully proved. The paper also gives explicit credit to the parallel primitives it builds on, though, as detailed below, several of those primitives are not established in the manuscript itself.

major comments (3)
  1. [§2, Theorem 2.3] Theorem 2.3 is stated as a "Fast Parallel Tree-Packing" algorithm with O~(m) work and O~(1) depth and is attributed to [Kar00]. However, [Kar00] presents a sequential near-linear-time minimum-cut algorithm; it does not state or prove a parallel tree-packing procedure. This theorem is used at the top of every epoch in Theorem 4.2 and is inherited by Theorem 1.1 (and by the k-ECSS extension in Section 5), so without a proof or a correct parallel citation the polylogarithmic-depth claim is conditional. The paper already cites [GG18] in the same section for a parallel minimum-cut result; a parallel tree-packing guarantee may be obtainable from that work, but it must be stated and proved or cited precisely.
  2. [§4.6, Lemma 4.7; also §5.1, Lemma 5.4] There is a mismatch between the LP matrix and the oracle's cut-weight computation. Lemma 4.7 defines A_{e,S}=1/(k c_e), so the column weight is (A^T w)_S=(1/k) sum_{e in delta(S)} w_e/c_e. The described data structure stores and sums unmodified edge weights w(e), and CutValue returns w(cut_T(s)); this is correct only if all costs c_e are equal. The same issue appears in Lemma 5.4 and in Definition 5.2, where the normalized free-cut weight is w(delta(S)\F)/(k-|F|) with no 1/c_e factor. Since Theorems 1.1 and 1.2 are for arbitrary positive costs, the oracle must maintain w_e/c_e or an equivalent scaling to implement Focus for the stated LP. The proof of Lemma 5.4 contains a related symptom: the first-iteration value g_{s'} = (k-|F_s|)/|B| * epsilon is not epsilon/(|B_0| max_i A_{i,s'}) unless all c_e are equal. Please correct the scaling or the matrix definition.
  3. [§4.6, Lemma 4.25] Lemma 4.25 attributes a canonical-cuts data structure to [CQ17] with O~(|E|) work and poly log|V| depth preprocessing. Reference [CQ17] is a sequential paper, and the cited lemma is not proved in the present manuscript; the parallel preprocessing and query guarantees are therefore unsupported as written. This matters because Lemma 4.7 (the MWU Cut Oracle) and hence Lemma 4.8 and Theorem 4.2 all depend on this data structure. A parallel derivation or a correct citation to a parallel construction is needed.
minor comments (3)
  1. [§3.2, Algorithm 3] Line 5 of Algorithm 3 says "Select a subset tildeB" at each iteration, but Definition 1.3 and Theorem 3.7 are stated in terms of a precomputed core-sequence. Please clarify that in the epoch applications the caller supplies the next member of a fixed core-sequence in order, or update the definition and proofs to allow online selection of the sequence.
  2. [§4.3, Claim 4.12] The proof that B'_r avoids Z3 asserts "Then 1 < j < ell-k" for the center of the forbidden pattern, but the boundary cases where the center lies in the first or last column are not addressed; these cases should be handled explicitly or the argument modified.
  3. [§4.6, proof of Lemma 4.7] The symbol k is used both for the k in k-ECSS and for the number of canonical pieces in the decomposition of a cut; consider renaming the latter to avoid ambiguity.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the core-sequence derivation is synthetic and the cited primitives are external, not self-referential.

full rationale

The paper's central claim, Theorem 1.1, does not reduce to a fitted value, a renamed input, or a self-referential definition. The core-sequence framework in Section 3 is proven in the manuscript itself: Lemmas 3.1, 3.2, 3.4, and Theorem 3.3 establish the MWU correctness, and Theorem 3.7 derives the iteration bound from Lemma 3.6. The existence of short core-sequences for the Cut Covering LP is proved structurally in Section 4.1 using submodularity, posimodularity, and forbidden-matrix bounds (Lemmas 4.3, 4.5, Claim 4.4), rather than being assumed from the target result. The epoch algorithm's reliance on Theorem 2.3 (tree packing) is an external cited primitive from Karger; even if the parallel version is not re-proved in the manuscript, that is a correctness or attribution risk, not circularity, because the paper does not derive Theorem 2.3 from its own algorithm. Similarly, the k-ECSS result imports the Range Mapping Theorem and the reduction from [CHN+22], which includes a co-author of the present paper, but that prior theorem is an independent published result used as a black box, and the present paper does not define any of its own quantities in terms of the k-ECSS target. No equation in the paper is equivalent by construction to an output it claims to predict, and no parameter is fit to make the theorem true. The derivation chain is therefore self-contained apart from external lemmas, which does not constitute circularity under the stated rules.

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

The paper introduces the concept of a core-sequence, but this is a mathematical definition rather than an invented physical entity. It introduces no free parameters: the only input constants are the accuracy ε and the graph, and no constants are fitted to data. The assumptions listed are external theorems and data structures whose proofs are cited rather than repeated here; some of these carry parallel complexity guarantees that are not fully derived in the paper.

assumptions (6)
  • standard math Submodularity and posimodularity of the cut function (Proposition 2.1).
    Used in Lemmas 4.5 and 4.11 to bound the size of core-sequences via forbidden matrix patterns.
  • domain assumption Karger's tree-packing theorem as stated in Theorem 2.3, with parallel work and depth guarantees.
    The epoch algorithm reduces clearing all cuts to clearing 1-or-2-respecting cuts of each tree in the packing; the parallel complexity of the packing is cited, not proven.
  • domain assumption Canonical cuts data structure (Lemma 4.25) from Chekuri and Quanrud [CQ17] with parallel construction in near-linear work and polylog depth.
    The MWU Cut Oracle's CutValue and Focus operations rely on this data structure; the parallel construction is asserted via a citation.
  • domain assumption Bough decomposition (Lemma 4.18) from Geissmann and Gianinazzi [GG18]: rooted tree decomposes into edge-disjoint paths satisfying Property 4.17 in O(n log n) work and O(log^2 n) depth.
    Used to decompose the spanning tree into paths for the path-clearing algorithm.
  • domain assumption Parallel algorithm for interested path pairs (Lemma 4.24) from Lopez-Martinez, Mukhopadhyay and Nanongkai [LMN21].
    Used to find path pairs that need clearing; its work and depth bounds are cited, not proven.
  • domain assumption Range Mapping Theorem (Theorem 5.3) from Chalermsook et al. [CHN+22] for the k-ECSS LP.
    Bridges normalized free cuts and truncated cut weights; used in the k-ECSS extension.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth." pith.science (2026). https://pith.science/paper/Z6DBQHJM

@misc{pith2026241114745,
  author       = {Pith},
  title        = {Pith review of: Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/Z6DBQHJM}},
  note         = {Machine review of arXiv:2411.14745}
}
abstract

We present a nearly linear work parallel algorithm for approximating the Held-Karp bound for the Metric TSP problem. Given an edge-weighted undirected graph $G=(V,E)$ on $m$ edges and $\epsilon>0$, it returns a $(1+\epsilon)$-approximation to the Held-Karp bound with high probability, in $\tilde{O}(m/\epsilon^4)$ work and $\tilde{O}(1/\epsilon^4)$ depth. While a nearly linear time sequential algorithm was known for almost a decade (Chekuri and Quanrud'17), it was not known how to simultaneously achieve nearly linear work alongside polylogarithmic depth. Using a reduction by Chalermsook et al.'22, we also give a parallel algorithm for computing a $(1+\epsilon)$-approximate fractional solution to the $k$-edge-connected spanning subgraph (kECSS) problem, with similar complexity. To obtain these results, we introduce a notion of core-sequences for the parallel Multiplicative Weights Update (MWU) framework (Luby-Nisan'93, Young'01). For the Metric TSP and kECSS problems, core-sequences enable us to exploit the structure of approximate minimum cuts to reduce the cost per iteration and/or the number of iterations. The acceleration technique via core-sequences is generic and of independent interest. In particular, it improves the best-known iteration complexity of MWU algorithms for packing/covering LPs from $poly(\log nnz(A))$ to polylogarithmic in the product of cardinalities of the core-sequence sets, where $A$ is the constraint matrix of the LP. For certain implicitly defined LPs such as the kECSS LP, this yields an exponential improvement in depth.

Figures

Figures reproduced from arXiv: 2411.14745 by the authors.

Figure 1
Figure 1. The matrix Mr formed by the path P given a node r ∈ V (P). (Left) The intervals A and B (blue and red, respectively) contain r and do not share the same endpoints. (Right) The intervals A \ B and B \ A are nonempty and do not contain r. We have established that for every 1 ≤ i ≤ k, there are at most |E(P)| intervals in SP for every path P ∈ Pi . However, we also need to efficiently find them in order to form the set… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

73 extracted references · 71 canonical work pages

  1. [1]

    Applegate, Robert E

    David L. Applegate, Robert E. Bixby, Vasek Chv \' a tal, and William J. Cook. Implementing the dantzig-fulkerson-johnson algorithm for large traveling salesman problems. Math. Program. , 97(1-2):91--153, 2003

    work page 2003

  2. [2]

    Applegate, Robert E

    David L. Applegate, Robert E. Bixby, Vašek Chvatál, and William J. Cook. The Traveling Salesman Problem: A Computational Study . Princeton University Press, 2006

    work page 2006

  3. [3]

    Beating approximation factor two for weighted tree augmentation with bounded costs

    David Adjiashvili. Beating approximation factor two for weighted tree augmentation with bounded costs. ACM Transactions on Algorithms (TALG) , 15(2):1--26, 2018

    work page 2018

  4. [4]

    The multiplicative weights update method: a meta-algorithm and applications

    Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: a meta-algorithm and applications. Theory Comput. , 8:121--164, 2012

    work page 2012

  5. [5]

    Stateless distributed gradient descent for positive linear programs

    Baruch Awerbuch and Rohit Khandekar. Stateless distributed gradient descent for positive linear programs. In STOC , 2008

    work page 2008

  6. [6]

    Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems

    Sanjeev Arora. Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems. J. ACM , 45(5):753--782, 1998

    work page 1998

  7. [7]

    Atallah and Uzi Vishkin

    Mikhail J. Atallah and Uzi Vishkin. Finding euler tours in parallel. J. Comput. Syst. Sci. , 29(3):330--337, 1984

    work page 1984

  8. [8]

    Using optimization to break the epsilon barrier: A faster and simpler width-independent algorithm for solving positive linear programs in parallel

    Zeyuan Allen-Zhu and Lorenzo Orecchia. Using optimization to break the epsilon barrier: A faster and simpler width-independent algorithm for solving positive linear programs in parallel. In SODA

    work page

Show all 73 references
  1. [9]

    Nearly-linear time positive lp solver with faster convergence rate

    Zeyuan Allen-Zhu and Lorenzo Orecchia. Nearly-linear time positive lp solver with faster convergence rate. In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing , page 229–236, New York, NY, USA, 2015. Association for Computing Machinery

    2015

  2. [10]

    Byers, and Danny Raz

    Yair Bartal, John W. Byers, and Danny Raz. Global optimization using local information with applications to flow control. In Proceedings 38th Annual Symposium on Foundations of Computer Science , pages 303--312. IEEE Computer Society, 1997

    1997

  3. [11]

    Byers, and Danny Raz

    Yair Bartal, John W. Byers, and Danny Raz. Fast, distributed approximation algorithms for positive linear programming with applications to flow control. SIAM Journal on Computing , 33(6):1261--1279, January 2005

    2005

  4. [12]

    Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs

    Glencora Borradaile, Erik D Demaine, and Siamak Tazari. Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs. Algorithmica , 68(2):287--311, 2014

    2014

  5. [13]

    Minimum weight 2-edge-connected spanning subgraphs in planar graphs

    Andr \'e Berger and Michelangelo Grigni. Minimum weight 2-edge-connected spanning subgraphs in planar graphs. In International Colloquium on Automata, Languages, and Programming , pages 90--101. Springer, 2007

    2007

  6. [14]

    Blelloch

    Guy E. Blelloch. Programming parallel algorithms. Commun. ACM , 39(3):85--97, 1996

    1996

  7. [15]

    A simple algorithm for minimum cuts in near-linear time

    Nalin Bhardwaj, Antonio Molina Lovett, and Bryce Sandlund. A simple algorithm for minimum cuts in near-linear time. In SWAT , volume 162 of LIPIcs , pages 12:1--12:18. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2020

    2020

  8. [16]

    Survivable network design for group connectivity in low-treewidth graphs

    Parinya Chalermsook, Syamantak Das, Guy Even, Bundit Laekhanukit, and Daniel Vaz. Survivable network design for group connectivity in low-treewidth graphs. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques , 2018

    2018

  9. [17]

    Carr, Lisa Fleischer, Vitus J

    Robert D. Carr, Lisa Fleischer, Vitus J. Leung, and Cynthia A. Phillips. Strengthening integrality gaps for capacitated network design and covering problems. In Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, January 9-11, 2000, San Francisco, CA,...

    2000

  10. [18]

    Approximation schemes for minimum 2-edge-connected and biconnected subgraphs in planar graphs

    Artur Czumaj, Michelangelo Grigni, Papa Sissokho, and Hairong Zhao. Approximation schemes for minimum 2-edge-connected and biconnected subgraphs in planar graphs. In Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms , pages 496--505. Society for Ind...

    2004

  11. [19]

    Approximating k-edge-connected spanning subgraphs via a near-linear time LP solver

    Parinya Chalermsook, Chien - Chung Huang, Danupon Nanongkai, Thatchaphol Saranurak, Pattara Sukprasert, and Sorrachai Yingchareonthawornchai. Approximating k-edge-connected spanning subgraphs via a near-linear time LP solver. In 49th International Colloquium on Automata, Langu...

    2022

  12. [20]

    Worst-case analysis of a new heuristic for the traveling salesman

    Nicos Christofides. Worst-case analysis of a new heuristic for the traveling salesman. Technical Report 388, Carnegie Mellon University, 1976

    1976

  13. [21]

    Approximability of dense and sparse instances of minimum 2-connectivity, tsp and path problems

    B \'e la Csaba, Marek Karpinski, and Piotr Krysta. Approximability of dense and sparse instances of minimum 2-connectivity, tsp and path problems. In Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms , pages 74--83. Society for Industrial and Appli...

    2002

  14. [22]

    On approximability of the minimum-cost k-connected spanning subgraph problem

    Artur Czumaj and Andrzej Lingas. On approximability of the minimum-cost k-connected spanning subgraph problem. In Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms , pages 281--290. Citeseer, 1999

    1999

  15. [23]

    Fast approximation schemes for euclidean multi-connectivity problems

    Artur Czumaj and Andrzej Lingas. Fast approximation schemes for euclidean multi-connectivity problems. In International Colloquium on Automata, Languages, and Programming , pages 856--868. Springer, 2000

    2000

  16. [24]

    Carr and Giuseppe Lancia

    Robert D. Carr and Giuseppe Lancia. Compact vs. exponential-size LP relaxations. Oper. Res. Lett. , 30(1):57--65, 2002

    2002

  17. [25]

    William J. Cook. In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation . Princeton University Press, 2012

    2012

  18. [26]

    Approximating the H eld- K arp bound for metric TSP in nearly-linear time

    Chandra Chekuri and Kent Quanrud. Approximating the H eld- K arp bound for metric TSP in nearly-linear time. 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages 789--800, 2017

    2017

  19. [27]

    Fast approximations for metric- TSP via linear programming

    Chandra Chekuri and Kent Quanrud. Fast approximations for metric- TSP via linear programming. CoRR , abs/1802.01242, 2018

    2018 arXiv

  20. [28]

    Dantzig, D

    George B. Dantzig, D. Ray Fulkerson, and Selmer M. Johnson. Solution of a large-scale traveling-salesman problem. Oper. Res. , 2(4):393--410, 1954

    1954

  21. [29]

    A better approximation ratio for the minimum sizek-edge-connected spanning subgraph problem

    Cristina G Fernandes. A better approximation ratio for the minimum sizek-edge-connected spanning subgraph problem. Journal of Algorithms , 28(1):105--124, 1998

    1998

  22. [30]

    Approximating weighted tree augmentation via chv \'a tal-gomory cuts

    Samuel Fiorini, Martin Gro , Jochen K \"o nemann, and Laura Sanit \`a . Approximating weighted tree augmentation via chv \'a tal-gomory cuts. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 817--831. SIAM, 2018

    2018

  23. [31]

    Davenport-schinzel theory of matrices

    Zolt \' a n F \" u redi and P \' e ter Hajnal. Davenport-schinzel theory of matrices. Discret. Math. , 103(3):233--251, 1992

    1992

  24. [32]

    Frederickson and Joseph J \' a J \' a

    Greg N. Frederickson and Joseph J \' a J \' a . Approximation algorithms for several graph augmentation problems. SIAM J. Comput. , 10(2):270--283, 1981

    1981

  25. [33]

    Frederickson and Joseph F

    Greg N. Frederickson and Joseph F. J \' a J \' a . On the relationship between the biconnectivity augmentation and traveling salesman problems. Theor. Comput. Sci. , 19:189--201, 1982

    1982

  26. [34]

    Approximating fractional multicommodity flow independent of the number of commodities

    Lisa Fleischer. Approximating fractional multicommodity flow independent of the number of commodities. SIAM J. Discret. Math. , 13(4):505--520, 2000

    2000

  27. [35]

    Goemans and Dimitris Bertsimas

    Michel X. Goemans and Dimitris Bertsimas. Survivable networks, linear programming relaxations and the parsimonious property. Math. Program. , 60:145--166, 1993

    1993

  28. [36]

    Parallel minimum cuts in near-linear work and low depth

    Barbara Geissmann and Lukas Gianinazzi. Parallel minimum cuts in near-linear work and low depth. In Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, SPAA 2018, Vienna, Austria, July 16-18, 2018 , pages 1--11. ACM , 2018

    2018

  29. [37]

    Approximating the smallest k-edge connected spanning subgraph by lp-rounding

    Harold N Gabow, Michel X Goemans, \'E va Tardos, and David P Williamson. Approximating the smallest k-edge connected spanning subgraph by lp-rounding. Networks: An International Journal , 53(4):345--357, 2009

    2009

  30. [38]

    Faster and simpler algorithms for multicommodity flow and other fractional packing problems

    Naveen Garg and Jochen K \" o nemann. Faster and simpler algorithms for multicommodity flow and other fractional packing problems. SIAM J. Comput. , 37(2):630--652, 2007

    2007

  31. [39]

    From trees to polynomials and back again: New capacity bounds with applications to TSP

    Leonid Gurvits, Nathan Klein, and Jonathan Leake. From trees to polynomials and back again: New capacity bounds with applications to TSP . In 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8-12, 2024, Tallinn, Estonia , volume 297 of LI...

    2024

  32. [40]

    Improved approximation for tree augmentation: saving by rewiring

    Fabrizio Grandoni, Christos Kalaitzis, and Rico Zenklusen. Improved approximation for tree augmentation: saving by rewiring. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing , pages 632--645, 2018

    2018

  33. [41]

    A note on a recent algorithm for minimum cut

    Pawel Gawrychowski, Shay Mozes, and Oren Weimann. A note on a recent algorithm for minimum cut. In 4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtual Conference, January 11-12, 2021 , pages 74--79. SIAM , 2021

    2021

  34. [42]

    Michel X. Goemans. Worst-case comparison of valid inequalities for the TSP . Math. Program. , 69:335--349, 1995

    1995

  35. [43]

    Gregory Gutin and Abraham P. Punnen. The Traveling Salesman Problem and Its Variations , volume 12 of Combinatorial Optimization . Springer Science+Business Media, 2007

    2007

  36. [44]

    Michael Held and Richard M. Karp. The traveling-salesman problem and minimum spanning trees. Oper. Res. , 18(6):1138--1162, 1970

    1970

  37. [45]

    Ellis Hershkowitz, Nathan Klein, and Rico Zenklusen

    D. Ellis Hershkowitz, Nathan Klein, and Rico Zenklusen. Ghost value augmentation for k-edge-connectivity. In Bojan Mohar, Igor Shinkar, and Ryan O'Donnell, editors, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-2...

    2024

  38. [46]

    Deterministic near-linear time minimum cut in weighted graphs

    Monika Henzinger, Jason Li, Satish Rao, and Di Wang. Deterministic near-linear time minimum cut in weighted graphs. In Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024 , pages 3089--3139. SIAM , 2024

    2024

  39. [47]

    Williamson

    Monika Henzinger and David P. Williamson. On the number of small cuts in a graph. Inf. Process. Lett. , 59(1):41--44, 1996

    1996

  40. [48]

    David R. Karger. Minimum cuts in near-linear time. J. ACM , 47(1):46--76, 2000

    2000

  41. [49]

    Lagrangian relaxation based algorithms for convex programming problems

    Rohit Khandekar. Lagrangian relaxation based algorithms for convex programming problems . PhD thesis, Indian Institute of Technology Delhi, 2004

    2004

  42. [50]

    Karlin, Nathan Klein, Shayan Oveis Gharan, and Xinzhi Zhang

    Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan, and Xinzhi Zhang. An improved approximation algorithm for the minimum k-edge connected multi-subgraph problem. In Stefano Leonardi and Anupam Gupta, editors, STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, R...

    2022

  43. [51]

    Karlin, Nathan Klein, and Shayan Oveis Gharan

    Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan. A (slightly) improved approximation algorithm for metric TSP . In STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021 , pages 32--45. ACM , 2021

    2021

  44. [52]

    Karlin, Nathan Klein, and Shayan Oveis Gharan

    Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan. A (slightly) improved bound on the integrality gap of the subtour LP for TSP . In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022 , pages 832--843. I...

    2022

  45. [53]

    Biconnectivity approximations and graph carvings

    Samir Khuller and Uzi Vishkin. Biconnectivity approximations and graph carvings. J. ACM , 41(2):214--235, 1994. announced at STOC'92

    1994

  46. [54]

    Improved inapproximability for TSP

    Michael Lampis. Improved inapproximability for TSP . Theory Comput. , 10:217--236, 2014

    2014

  47. [55]

    A rounding by sampling approach to the minimum size k-arc connected subgraph problem

    Bundit Laekhanukit, Shayan Oveis Gharan, and Mohit Singh. A rounding by sampling approach to the minimum size k-arc connected subgraph problem. In International Colloquium on Automata, Languages, and Programming , pages 606--616. Springer, 2012

    2012

  48. [56]

    E. L. Lawler, Jan Karel Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization . John Wiley & Sons, 1991

    1991

  49. [57]

    Work-optimal parallel minimum cuts for non-sparse graphs

    Andr \' e s L \' o pez - Mart \' nez, Sagnik Mukhopadhyay, and Danupon Nanongkai. Work-optimal parallel minimum cuts for non-sparse graphs. In SPAA '21: 33rd ACM Symposium on Parallelism in Algorithms and Architectures, Virtual Event, USA, 6-8 July, 2021 , pages 351--361. ACM , 2021

    2021

  50. [58]

    A parallel approximation algorithm for positive linear programming

    Michael Luby and Noam Nisan. A parallel approximation algorithm for positive linear programming. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing , STOC '93, page 448–457, New York, NY, USA, 1993. Association for Computing Machinery

    1993

  51. [59]

    Joseph S. B. Mitchell. Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric tsp, k-mst, and related problems. SIAM J. Comput. , 28(4):1298--1309, 1999

    1999

  52. [60]

    Monma, Beth Spellman Munson, and William R

    Clyde L. Monma, Beth Spellman Munson, and William R. Pulleyblank. Minimum-weight two-connected spanning networks. Math. Program. , 46:153--171, 1990

    1990

  53. [61]

    Weighted min-cut: sequential, cut-query, and streaming algorithms

    Sagnik Mukhopadhyay and Danupon Nanongkai. Weighted min-cut: sequential, cut-query, and streaming algorithms. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020 , pages 496--509. ACM , 2020

    2020

  54. [62]

    Mahoney, Satish Rao, Di Wang, and Peng Zhang

    Michael W. Mahoney, Satish Rao, Di Wang, and Peng Zhang. Approximating the solution to mixed packing and covering lps in parallel o (epsilon \^ \ -3\ ) time. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy , v...

    2016

  55. [63]

    Nesterov

    Yu. Nesterov. Smooth minimization of non-smooth functions. Mathematical Programming , 103(1):127--152, 2005

    2005

  56. [64]

    Polyhedral structure of submodular and posi-modular systems

    Hiroshi Nagamochi and Toshihide Ibaraki. Polyhedral structure of submodular and posi-modular systems. Discret. Appl. Math. , 107(1-3):165--189, 2000

    2000

  57. [65]

    C. St.J. A. Nash-Williams. Edge-Disjoint Spanning Trees of Finite Graphs . Journal of the London Mathematical Society , s1-36(1):445--450, 01 1961

    1961

  58. [66]

    k-edge-connectivity: Approximation and LP relaxation

    David Pritchard. k-edge-connectivity: Approximation and LP relaxation. In WAOA , volume 6534 of Lecture Notes in Computer Science , pages 225--236. Springer, 2010

    2010

  59. [67]

    Plotkin, David B

    Serge A. Plotkin, David B. Shmoys, and \' E va Tardos. Fast approximation algorithms for fractional packing and covering problems. Math. Oper. Res. , 20(2):257--301, 1995

    1995

  60. [68]

    A. I. Serdyukov. O nekotorykh ekstremal’nykh obkhodakh v grafakh. Upravlyaemye sistemy , 17:76--79, 1978

    1978

  61. [69]

    An o(n \( ^2 \) log n) parallel MAX-FLOW algorithm

    Yossi Shiloach and Uzi Vishkin. An o(n \( ^2 \) log n) parallel MAX-FLOW algorithm. J. Algorithms , 3(2):128--146, 1982

    1982

  62. [70]

    Shmoys and David P

    David B. Shmoys and David P. Williamson. Analyzing the held-karp TSP bound: A monotonicity property with application. Inf. Process. Lett. , 35(6):281--285, 1990

    1990

  63. [71]

    Laurence A. Wolsey. Heuristic analysis, linear programming and branch and bound , pages 121--134. Springer Berlin Heidelberg, 1980

    1980

  64. [72]

    Neal E. Young. Sequential and parallel algorithms for mixed packing and covering. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA , pages 538--546. IEEE Computer Society, 2001

    2001

  65. [73]

    Neal E. Young. Nearly linear-time approximation schemes for mixed packing/covering and facility-location linear programs. CoRR , abs/1407.3015, 2014

    2014 arXiv

Pith tools

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