arxiv: 2605.12669 · v1 · submitted 2026-05-12 · 💻 cs.DS

Recognition: 1 theorem link

· Lean Theorem

Thin Trees for Near Minimum Cuts

Nathan Klein , Neil Olver , Zi Song Yeoh

Authors on Pith no claims yet

Pith reviewed 2026-05-14 20:03 UTC · model grok-4.3

classification 💻 cs.DS

keywords thin treesnear minimum cutsspanning treesk-edge connectivitylaminar familiespolygon representationgraph algorithms

0 comments

The pith

Every k-edge-connected graph has a spanning tree that is O(1/k)-thin for its near-minimum cuts with η=1/40, constructible in polynomial time.

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

The authors prove a restricted version of the open strong thin tree conjecture. They show that any k-edge-connected graph admits a spanning tree crossing each cut with fewer than 1.025k edges in at most an O(1/k) fraction of those edges. The tree is found in polynomial time by reducing the near-minimum cuts to a laminar family using their polygon representation. A sympathetic reader cares because this gives an efficient handle on the key connectivity cuts without resolving the full conjecture for all cuts.

Core claim

We demonstrate that the conjecture is true if one only requires thinness for the set of η-near minimum cuts of the graph for η = 1/40, in other words, for the set of cuts with fewer than (1+1/40)k edges. Our approach constructs such a tree in polynomial time. To show this, we utilize the structure of near minimum cuts, and in particular the polygon representation of Benczúr and Goemans, to reduce to the previously solved problem of finding a spanning tree that is O(1/k)-thin for all sets in a laminar family.

What carries the argument

The polygon representation of near-minimum cuts by Benczúr and Goemans, which reduces the thin-tree problem for these cuts to the laminar family case.

Load-bearing premise

The polygon representation of near-minimum cuts due to Benczúr and Goemans allows a clean reduction to the laminar-family case whose thin-tree solution is already known.

What would settle it

A k-edge-connected graph with no O(1/k)-thin spanning tree for its set of cuts having fewer than (1 + 1/40)k edges would falsify the claim.

Figures

Figures reproduced from arXiv: 2605.12669 by Nathan Klein, Neil Olver, Zi Song Yeoh.

**Figure 2.** Figure 2: Consider the graph on the left, with minimum cut 7. On the right is the polygon [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗

**Figure 3.** Figure 3: Figures depicting the proof of Lemma 3.6. 3. A = ⟨y,rA⟩ ∖ ⟨x, lA⟩ for some NMIs ⟨y,rA⟩ and ⟨x, lA⟩ with x < y < lA < rA. Then, A ∩ B = ⟨lB,rA⟩ = ⟨y,rA⟩ ∩ B and B ∖ A = ⟨rA,rB⟩ = B ∖ ⟨y,rA⟩ are special. 4. A = ⟨lA, x⟩ ∖ ⟨rA, y⟩ for some NMIs ⟨lA, x⟩ and ⟨rA, y⟩ with lA < rA < x < y. If x < rB, then A ∖ B = ⟨lA, lB⟩ = ⟨lA, x⟩ ∖ B and A ∪ B = ⟨lA,rB⟩ = ⟨lA, x⟩ ∪ B are special. Otherwise, x ≥ rB, so y > rB. Th… view at source ↗

**Figure 4.** Figure 4: shows the relative positions of the defined points. l1 lS i rS r1 j 1 n [PITH_FULL_IMAGE:figures/full_fig_p013_4.png] view at source ↗

**Figure 5.** Figure 5: Figure depicting the proof that ⟨lS, i⟩ is special. The red interval denotes A and the blue interval denotes B. Finally, we prove that the pairs of outside atoms such that one is in ⟨j,rS⟩ and the other is not in ⟨l1,rS⟩ are covered by at most 5 cuts in L. Claim 3.11. There is a collection B ′ of at most 5 cuts in L that covers every pair of outside atoms such that one is in ⟨j,rS⟩ and the other is not in … view at source ↗

**Figure 6.** Figure 6: Figure depicting the proof that ⟨j,rS⟩ is special. The red interval denotes A and the blue interval denotes B. Let ⟨l2,r2⟩ be the active interval at depth depth + 1 such that l2 ≤ rS ≤ r2. Note that l2 = j and since rS > j, l2 < rS ≤ r2 ≤ r1. Let l3 = max{x : l2 ≤ x ≤ rS,⟨x,r2⟩ is special}, r3 = min{x : rS ≤ x ≤ r2,⟨x,r2⟩ is special}, and z = min{x : l2 ≤ x ≤ rS,⟨x,r2⟩ is special}. If l3 does not exist, th… view at source ↗

**Figure 7.** Figure 7: A figure indicating the relative positions of the defined points and the cuts in [PITH_FULL_IMAGE:figures/full_fig_p014_7.png] view at source ↗

**Figure 8.** Figure 8: Figure depicting the proof that ⟨l3,rS⟩ is special. The red interval denotes A and the blue interval denotes B. the desired pairs of atoms. We add cut(l3,rS) to B ′ [PITH_FULL_IMAGE:figures/full_fig_p015_8.png] view at source ↗

**Figure 9.** Figure 9: The blue lines are the diagonals in D and the red line is the representing diagonal of S. In the argument of the proof of Lemma 3.12, we have u ′ = a6 and v ′ = a0. In particular, initialize a cross-free family R. Add to R one side of each η-near minimum cut which is not crossed (i.e. every connected component C with |C| = 1). Then, construct a polygon P for each connected component C of near minimum cuts … view at source ↗

read the original abstract

The strong thin tree conjecture states that every $k$-edge-connected graph $G$ contains an $O(1/k)$-thin spanning tree, meaning a spanning tree which contains at most an $O(1/k)$ fraction of the edges across each cut in $G$. This conjecture is still open despite significant effort; the best current result by Anari and Oveis Gharan shows the existence of an $O(\text{polyloglog}(n)/k)$-thin tree. In this work, we demonstrate that the conjecture is true if one only requires thinness for the set of $\eta$-near minimum cuts of the graph for $\eta = 1/40$, in other words, for the set of cuts with fewer than $(1+1/40)k$ edges. Our approach constructs such a tree in polynomial time. To show this, we utilize the structure of near minimum cuts, and in particular the polygon representation of Bencz\'ur and Goemans, to reduce to the previously solved problem of finding a spanning tree that is $O(1/k)$-thin for all sets in a laminar family.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note private letter to a colleague

The paper gives the first O(1/k) thin-tree result for near-minimum cuts by reducing them to a laminar family via the Benczúr-Goemans polygon representation.

read the letter

The main thing to know is that this paper proves an O(1/k)-thin spanning tree for the η-near-minimum cuts when η=1/40, meaning cuts with at most (1+1/40)k edges, and it builds the tree in polynomial time. This is a direct partial resolution of the strong thin tree conjecture restricted to that subclass, improving on the polyloglog(n)/k bound that holds for all cuts in prior work by Anari and Oveis Gharan. The approach reduces the near-min cuts to a laminar family using the known polygon representation and then applies the existing laminar thin-tree result, which keeps the bound clean without extra factors. That reduction is the core technical step and it appears to go through without introducing circularity or new parameters. The construction is explicit and polynomial-time, which is a practical plus. The argument relies on standard structural facts about near-min cuts, so the soundness rests on how faithfully the polygon representation maps the cuts to laminar sets; the stress-test indicates the bound is preserved directly. There are no load-bearing flaws visible in the setup. The limitation is obvious and stated: it only handles near-min cuts rather than the full conjecture, and the specific 1/40 comes from the representation rather than being optimized further. That is a real but expected restriction for this kind of incremental result. The citations track the relevant prior work on thin trees and the polygon representation without padding. This paper is aimed at people working on approximation algorithms for network design and cut-based problems. A reader following the thin-tree conjecture or looking for better tools on near-min cuts will get concrete value from the reduction technique. It deserves a serious referee because the claim is new, the method is grounded in existing theorems, and the polynomial-time construction makes it usable. I would send it out for review.

Referee Report

0 major / 3 minor

Summary. The manuscript proves that for every k-edge-connected graph, there exists a spanning tree that is O(1/k)-thin specifically with respect to all η-near-minimum cuts where η = 1/40. The tree can be constructed in polynomial time by reducing the problem, using the Benczúr-Goemans polygon representation of near-min cuts, to the laminar-family case whose solution is already known.

Significance. This provides a partial affirmative answer to the strong thin-tree conjecture by focusing on near-minimum cuts, which play a key role in cut-based algorithms and graph connectivity. The polynomial-time construction enhances its algorithmic utility. By leveraging the structural theorem of Benczúr and Goemans, the work demonstrates an effective reduction technique that may extend to other variants of the conjecture.

minor comments (3)

[Introduction] The statement of the main theorem should explicitly state the hidden constant in the O(1/k) thinness to allow precise comparison with prior work such as Anari-Oveis Gharan.
[Section 3] The reduction argument would benefit from a diagram or pseudocode outlining the steps from the polygon representation to the laminar family construction.
[References] Ensure the reference to the laminar thin-tree result includes the full citation details and the specific theorem invoked.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary and recommendation of minor revision. We are pleased that the contribution is recognized as a partial affirmative answer to the strong thin-tree conjecture, with the polynomial-time construction via reduction to the laminar case using the Benczúr-Goemans representation.

Circularity Check

0 steps flagged

No significant circularity: reduction to independent prior laminar result

full rationale

The derivation invokes the Benczúr-Goemans polygon representation (external prior work) to reduce η-near-min-cut thinness to the already-solved O(1/k)-thin spanning tree problem on laminar families. No equation defines the target thinness via a fitted parameter or self-referential ansatz from this paper; the central claim rests on an independent structural theorem and a pre-existing laminar solution rather than reducing to its own inputs by construction. This is the standard honest case of a self-contained reduction to external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claim rests on the polygon representation theorem of Benczúr and Goemans (prior work) and the known existence of O(1/k)-thin trees for laminar families (prior work). No new free parameters or invented entities are introduced.

axioms (1)

standard math Standard definitions of k-edge-connectivity, spanning trees, and cut thinness
The paper uses the usual graph-theoretic definitions without additional assumptions.

pith-pipeline@v0.9.0 · 5495 in / 1269 out tokens · 67498 ms · 2026-05-14T20:03:43.655697+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We utilize the structure of near minimum cuts, and in particular the polygon representation of Benczúr and Goemans, to reduce to the previously solved problem of finding a spanning tree that is O(1/k)-thin for all sets in a laminar family.

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

300 extracted references · 20 canonical work pages · 1 internal anchor

[1]

Algorithmica , year=

Bansal, Ishan and Cheriyan, Joseph and Grout, Logan and Ibrahimpur, Sharat , title=. Algorithmica , year=. doi:10.1007/s00453-024-01235-2 , url=

work page doi:10.1007/s00453-024-01235-2
[2]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC) , pages =

Traub, Vera and Vygen, Jens , title =. Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC) , pages =. 2020 , doi =

2020
[3]

2023 , pages =

Klein, Nathan and Olver, Neil , booktitle =. 2023 , pages =

2023
[4]

2012 , howpublished=

Thin spanning trees , author=. 2012 , howpublished=

2012
[5]

and Singh, Mohit , title =

Lau, Lap Chi and Naor, Joseph (Seffi) and Salavatipour, Mohammad R. and Singh, Mohit , title =. SIAM Journal on Computing , volume =. 2009 , doi =. https://doi.org/10.1137/070700620 , abstract =

work page doi:10.1137/070700620 2009
[6]

SIAM Journal on Computing , volume =

Lau, Lap Chi and Singh, Mohit , title =. SIAM Journal on Computing , volume =. 2013 , doi =. https://doi.org/10.1137/110854461 , abstract =

work page doi:10.1137/110854461 2013
[7]

Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing , pages =

Ene, Alina and Vakilian, Ali , title =. Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing , pages =. 2014 , isbn =. doi:10.1145/2591796.2591837 , abstract =

work page doi:10.1145/2591796.2591837 2014
[8]

Approximate multi-matroid intersection via iterative refinement , journal=

Linhares, Andr. Approximate multi-matroid intersection via iterative refinement , journal=. 2020 , day=. doi:10.1007/s10107-020-01524-y , url=

work page doi:10.1007/s10107-020-01524-y 2020
[9]

On generalizations of network design problems with degree bounds , journal=

Bansal, Nikhil and Khandekar, Rohit and K. On generalizations of network design problems with degree bounds , journal=. 2013 , day=. doi:10.1007/s10107-012-0537-8 , url=

work page doi:10.1007/s10107-012-0537-8 2013
[10]

Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures , year=

Chekuri, Chandra and Vondrak, Jan and Zenklusen, Rico , booktitle=. Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures , year=
[11]

, title =

An, Hyung-Chan and Kleinberg, Robert and Shmoys, David B. , title =. ACM Transactions on Algorithms , articleno =. 2021 , issue_date =. doi:10.1145/3478537 , abstract =

work page doi:10.1145/3478537 2021
[12]

Approximating minimum bounded degree spanning trees to within one of optimal , volume =

Mohit Singh and Lap Chi Lau , doi =. Approximating minimum bounded degree spanning trees to within one of optimal , volume =. Journal of the ACM , keywords =
[13]

k-Edge-Connectivity: Approximation and LP Relaxation

Pritchard, David. k-Edge-Connectivity: Approximation and LP Relaxation. Proceedings of the Ninth International Workshop on Approximation and Online Algorithms (WAOA). 2011

2011
[14]

Separating from the dominant of the spanning tree polytope , journal =

Francisco Barahona , keywords =. Separating from the dominant of the spanning tree polytope , journal =. 1992 , doi =

1992
[15]

A New Dynamic Programming Approach for Spanning Trees with Chain Constraints and Beyond , year =

N\". A New Dynamic Programming Approach for Spanning Trees with Chain Constraints and Beyond , year =. Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages =
[16]

Degree Bounded Matroids and Submodular Flows

Kir \'a ly, Tam \'a s and Lau, Lap Chi and Singh, Mohit. Degree Bounded Matroids and Submodular Flows. Combinatorica , volume=. 2012 , doi =

2012
[17]

Approximating Min-Cost Chain-Constrained Spanning Trees: A Reduction from Weighted to Unweighted Problems

Linhares, Andr \'e and Swamy, Chaitanya. Approximating Min-Cost Chain-Constrained Spanning Trees: A Reduction from Weighted to Unweighted Problems. Mathematical Programming , volume=. 2018 , doi =

2018
[18]

A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem , year =

Svensson, Ola and Tarnawski, Jakub and V\'. A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem , year =. doi:10.1145/3424306 , journal =

work page doi:10.1145/3424306
[19]

The weak 3-flow conjecture and the weak circular flow conjecture , journal =

Carsten Thomassen , keywords =. The weak 3-flow conjecture and the weak circular flow conjecture , journal =. 2012 , doi =

2012
[20]

Approximating the Minimum Degree Spanning Tree to Within One from the Optimal Degree , booktitle =

Fürer, Martin and Raghavachari, Balaji , year =. Approximating the Minimum Degree Spanning Tree to Within One from the Optimal Degree , booktitle =
[21]

Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages =

The Asymmetric Traveling Salesman Problem on Graphs with Bounded Genus , year =. Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages =
[22]

Chain-Constrained Spanning Trees

Olver, Neil and Zenklusen, Rico. Chain-Constrained Spanning Trees. Mathematical Programming , volume=. 2018 , doi =

2018
[23]

Discrete Applied Mathematics , volume=

Sylvia Boyd and Yao Fu and Yu Sun , title=. Discrete Applied Mathematics , volume=
[24]

Goemans, M. X. and Ramakrishnan, V. S. , title=. Combinatorica , year=
[25]

Karger and Debmalya Panigrahi , title =

David R. Karger and Debmalya Panigrahi , title =. SODA , chapter =
[26]

Oberwolfach Workshop on Combinatorial Optimization (hybrid meeting) , note=

Michel Goemans , year=. Oberwolfach Workshop on Combinatorial Optimization (hybrid meeting) , note=
[27]

Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree , year =

Byrka, Jaros. Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree , year =. STOC , pages =
[28]

Ravi , title =

Arash Haddadan and Alantha Newman and R. Ravi , title =. Math. Program. , volume =. 2021 , url =. doi:10.1007/s10107-019-01426-8 , timestamp =

work page doi:10.1007/s10107-019-01426-8 2021
[29]

APPROX/RANDOM , pages =

Sylvia Boyd and Joseph Cheriyan and Robert Cummings and Logan Grout and Sharat Ibrahimpur and Zolt. APPROX/RANDOM , pages =. 2020 , volume =

2020
[30]

Combinatorica , volume=

Andr\'as Seb\"o and Jens Vygen , title=. Combinatorica , volume=
[31]

and Klein, Nathan and Oveis Gharan, Shayan and Zhang, Xinzhi , keywords =

Karlin, Anna R. and Klein, Nathan and Oveis Gharan, Shayan and Zhang, Xinzhi , keywords =. An Improved Approximation Algorithm for the Minimum k -Edge Connected Multi-Subgraph Problem , publisher =. 2021 , copyright =. doi:10.48550/ARXIV.2101.05921 , url =

work page doi:10.48550/arxiv.2101.05921 2021
[32]

Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages =

Cecchetto, Federica and Traub, Vera and Zenklusen, Rico , title =. Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages =. 2021 , publisher =

2021
[33]

CoRR , volume =

Anupam Gupta and Euiwoong Lee and Jason Li and Marcin Mucha and Heather Newman and Sherry Sarkar , title =. CoRR , volume =. 2021 , url =. 2111.09290 , timestamp =

work page arXiv 2021
[34]

Leonid Gurvits , title =. Electr. J. Comb. , volume =. 2008 , url =

2008
[35]

2020 , url=

A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem , author=. 2020 , url=

2020
[36]

Vishnoi , editor =

Damian Straszak and Nisheeth K. Vishnoi , editor =. Maximum Entropy Distributions: Bit Complexity and Stability , booktitle =
[37]

Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , title=

Anari, Nima and. Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , title=. 2015 , volume=

2015
[38]

Log-Concave Polynomials, Entropy, and a Deterministic Approximation Algorithm for Counting Bases of Matroids , booktitle =

Nima Anari and Shayan. Log-Concave Polynomials, Entropy, and a Deterministic Approximation Algorithm for Counting Bases of Matroids , booktitle =
[39]

Williamson , title =

Kyle Genova and David P. Williamson , title =. Algorithmica , volume =
[40]

New inapproximability bounds for TSP

Marek Karpinski and Michael Lampis and Richard Schmied. New inapproximability bounds for TSP. Journal of Computer and System Sciences. 2015

2015
[41]

1978 , author=

O nekotorykh ekstremal’nykh obkhodakh v grafakh , journal=. 1978 , author=

1978
[42]

Hyperbolic polynomials approach to Van der Waerden/Schrijver-Valiant like conjectures: sharper bounds, simpler proofs and algorithmic applications , booktitle =

Leonid Gurvits , editor =. Hyperbolic polynomials approach to Van der Waerden/Schrijver-Valiant like conjectures: sharper bounds, simpler proofs and algorithmic applications , booktitle =
[43]

Reducing path

Vera Traub and Jens Vygen and Rico Zenklusen , editor =. Reducing path. STOC , pages =
[44]

Ravi , title =

Arash Haddadan and Alantha Newman and R. Ravi , title =. 2017 , url =

2017
[45]

Ravi , title =

Robert Carr and R. Ravi , title =. IPCO , pages =
[46]

Boyd and Andr

Sylvia C. Boyd and Andr. The Saleman's Improved Tours for Fundamental Classes , booktitle =
[47]

Towards Improving Christofides Algorithm for Half-Integer

Arash Haddadan and Alantha Newman , editor =. Towards Improving Christofides Algorithm for Half-Integer. ESA , series =
[48]

osung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Str\

Ueber die Aufl\"osung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Str\"ome gef\"uhrt wird , author=. Annalen der Physik , volume=. 1847 , publisher=
[49]

Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices

Sylvia Boyd and Robert Carr. Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices. Discrete Optimization. 2011

2011
[50]

Mathematics of Operations Research , volume=

2-Matchings, the Traveling Salesman Problem, and the Subtour LP: A Proof of the Boyd-Carr Conjecture , author=. Mathematics of Operations Research , volume=. 2013 , pages=

2013
[51]

2011 , pages =

A Randomized Rounding Approach to the Traveling Salesman Problem , booktitle =. 2011 , pages =

2011
[52]

2013 , publisher=

Algebraic graph theory , author=. 2013 , publisher=

2013
[53]

SODA , pages=

Fast generation of random spanning trees and the effective resistance metric , author=. SODA , pages=
[54]

Information Processing Letters , volume=

Analyzing the Held-Karp TSP bound: A monotonicity property with application , author=. Information Processing Letters , volume=. 1990 , publisher=

1990
[55]

SIAM Journal on Computing , volume=

Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems , author=. SIAM Journal on Computing , volume=. 1999 , publisher=

1999
[56]

Towards a theory of negative dependence , Volume =

Robin Pemantle , Date-Added =. Towards a theory of negative dependence , Volume =. J. Math. Phys. , Pages =
[57]

An approximation algorithm for max-min fair allocation of indivisible goods , Year =

Arash Asadpour and Amin Saberi , Booktitle =. An approximation algorithm for max-min fair allocation of indivisible goods , Year =
[58]

Sushant Sachdeva and Nisheeth Vishnoi , Date-Added =
[59]

Harvey, Nicholas J. A. and Olver, Neil , title =. Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages =. 2014 , abstract =

2014
[60]

A unifying theorem for spectral embedding and clustering , Year =

Matthew Brand and Kun Huang , Date-Added =. A unifying theorem for spectral embedding and clustering , Year =
[61]

A. Gu. Random Spanning Tree , Volume =. J. Algorithms , Number =
[62]

Kulkarni, V. G. , Date-Added =. Generating random combinatorial objects , Volume =. J. Algorithms , Number =. 1990 , Bdsk-Url-1 =

1990
[63]

Spielman and Nikhil Srivastava , journal =

Adam Marcus and Daniel A. Spielman and Nikhil Srivastava , journal =. Interlacing Families II: Mixed Characteristic Polynomials and the Kadison-Singer Problem , Year =
[64]

Approximation Algorithm for Sparsest k-Partitioning , Year =

Anand Louis and Konstantin Makarychev , Date-Added =. Approximation Algorithm for Sparsest k-Partitioning , Year =
[65]

Spectral Partitioning of Random Graphs , Year =

Frank McSherry , Booktitle =. Spectral Partitioning of Random Graphs , Year =
[66]

Undirected ST-connectivity in log-space , Year =

Omer Reingold , Booktitle =. Undirected ST-connectivity in log-space , Year =
[67]

Vadhan and Avi Wigderson , Booktitle =

Omer Reingold and Salil P. Vadhan and Avi Wigderson , Booktitle =. Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors , Year =
[68]

Kelner and Lorenzo Orecchia and Aaron Sidford and Zeyuan Allen Zhu , Booktitle =

Jonathan A. Kelner and Lorenzo Orecchia and Aaron Sidford and Zeyuan Allen Zhu , Booktitle =. A simple, combinatorial algorithm for solving SDD systems in nearly-linear time , Year =
[69]

Miller and Richard Peng , Booktitle =

Ioannis Koutis and Gary L. Miller and Richard Peng , Booktitle =. A Nearly-m log n Time Solver for SDD Linear Systems , Year =
[70]

Miller and Richard Peng , Booktitle =

Ioannis Koutis and Gary L. Miller and Richard Peng , Booktitle =. Approaching Optimality for Solving SDD Linear Systems , Year =
[71]

Boyd and P

S. Boyd and P. Elliott-Magwood , Booktitle =. Structure of the extreme points of the subtour elimination polytope of the STSP , Volume =
[72]

An improved upper bound for the TSP in cubic 3-edge-connected graphs , Volume =

Gamarnik, David and Lewenstein, Moshe and Sviridenko, Maxim , Date-Added =. An improved upper bound for the TSP in cubic 3-edge-connected graphs , Volume =. Oper. Res. Lett. , Month = sep, Number =. 2005 , Bdsk-Url-1 =

2005
[73]

Goemans , Date-Added =

Michel X. Goemans , Date-Added =. Worst-Case Comparison of Valid Inequalities for the TSP , Volume =. MATH. PROG , Pages =
[74]

Shmoys, D. B. and Williamson, D. P. , Date-Added =. Analyzing the Held-Karp TSP bound: a monotonicity property with application , Volume =. Inf. Process. Lett. , Month = sep, Number =. 1990 , Bdsk-Url-1 =

1990
[75]

Karp , Date-Added =

Richard M. Karp , Date-Added =. A Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem , Volume =. SIAM J. Comput. , Number =
[76]

Karp , Date-Added =

Richard M. Karp , Date-Added =. Probabilistic analysis of partitioning algorithms for the traveling-salesman in the plane , Volume =. MOR , Pages =
[77]

Karp , Booktitle =

Richard M. Karp , Booktitle =. Reducibility Among Combinatorial Problems , Year =
[78]

Dantzig and D.R

G.B. Dantzig and D.R. Fulkerson and S. Johnson , Date-Added =. On a Linear Programming Combinatorial Approach to the Traveling Salesman Problem , Volume =. OR , Pages =
[79]

Biggs, N. L. , Date-Added =. T. P. Kirkman, mathematician , Volume =. The Bulletin of the London Mathematical Society , Number =
[80]

Spielman , Date-Added =

Daniel A. Spielman , Date-Added =. Linear-Time Encodable and Decodable Error-Correcting Codes , Volume =. IEEE Transactions on Information Theory , Pages =

Showing first 80 references.