Buchumschlag

A simpler and parallelizable $O(\sqrt{\log n})$-approximation algorithm for Sparsest Cut

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
1. Verfasser:	Kolmogorov, Vladimir
Format:	Preprint
Veröffentlicht:	2023
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

OrderedCuts: A new approach for computing Gomory-Hu tree
von: Kolmogorov, Vladimir
Veröffentlicht: (2022)

A computational study of Gomory-Hu construction tree algorithms
von: Kolmogorov, Vladimir
Veröffentlicht: (2022)

Distributed Sparsest Cut via Eigenvalue Estimation
von: Maus, Yannic, et al.
Veröffentlicht: (2025)

On Sparsest Cut and Conductance in Directed Polymatroidal Networks
von: Chekuri, Chandra, et al.
Veröffentlicht: (2024)

Faster algorithms for packing forests in graphs and related problems
von: Arkhipov, Pavel, et al.
Veröffentlicht: (2024)

Approximating Sparsest Cut in Low-Treewidth Graphs via Combinatorial Diameter
von: Chalermsook, Parinya, et al.
Veröffentlicht: (2021)

On the Hardness Hierarchy for the $O(n \sqrt{\log n})$ Complexity in the Word RAM
von: Kempa, Dominik, et al.
Veröffentlicht: (2025)

A new notion of commutativity for the algorithmic Lovász Local Lemma
von: Harris, David G., et al.
Veröffentlicht: (2020)

Blossom VI: A Practical Minimum Weight Perfect Matching Algorithm
von: Arkhipov, Pavel, et al.
Veröffentlicht: (2026)

Greedy matroid base packings with applications to dynamic graph density and orientations
von: Arkhipov, Pavel, et al.
Veröffentlicht: (2025)

Bounded indegree $k$-forests problem and a faster algorithm for directed graph augmentation
von: Arkhipov, Pavel, et al.
Veröffentlicht: (2024)

A Fast Approximation Algorithm for the Minimum Balanced Vertex Separator in a Graph
von: Kolmogorov, Vladimir, et al.
Veröffentlicht: (2026)

An approximation algorithm for Maximum DiCut vs. Cut
von: Nakajima, Tamio-Vesa, et al.
Veröffentlicht: (2024)

Simple parallel estimation of the partition ratio for Gibbs distributions
von: Harris, David G., et al.
Veröffentlicht: (2025)

A simpler QPTAS for scheduling jobs with precedence constraints
von: Das, Syamantak, et al.
Veröffentlicht: (2025)

Tighter relaxations for MAP-MRF optimization via Singleton Arc Consistency
von: Lev-Ran, Asaf, et al.
Veröffentlicht: (2026)

Fully Dynamic Connectivity in $O(\log n(\log\log n)^2)$ Amortized Expected Time
von: Huang, Shang-En, et al.
Veröffentlicht: (2016)

An $2\sqrt{k}$-approximation algorithm for minimum power $k$ edge disjoint $st$ -paths
von: Nutov, Zeev
Veröffentlicht: (2022)

Faster and simpler online/sliding rightmost Lempel-Ziv factorizations
von: Sumiyoshi, Wataru, et al.
Veröffentlicht: (2024)

Finding a solution to the Erdős-Ginzburg-Ziv theorem in $O(n\log\log\log n)$ time
von: Leung, Yui Hin Arvin
Veröffentlicht: (2025)

$O(\log n)$-Approximation Algorithms for Bipartiteness Ratio
von: Soma, Tasuku, et al.
Veröffentlicht: (2025)

All-Pairs Minimum Cut using $\tilde{O}(n^{7/4})$ Cut Queries
von: Kenneth-Mordoch, Yotam, et al.
Veröffentlicht: (2025)

An FPT algorithm for Matching Cut and d-cut
von: Aravind, N R, et al.
Veröffentlicht: (2021)

An $Ω(n \log n)$ Randomized Lower Bound for Cutting a Cake into Proportionally Fair Pieces
von: Arndt, Stephen, et al.
Veröffentlicht: (2026)

Embedding Planar Graphs into Graphs of Treewidth $O(\log^{3} n)$
von: Chang, Hsien-Chih, et al.
Veröffentlicht: (2024)

Gabow's $O(\sqrt{n}m)$ Maximum Cardinality Matching Algorithm, Revisited
von: Mehlhorn, Kurt, et al.
Veröffentlicht: (2026)

Fully dynamic biconnectivity in $\tilde{\mathcal{O}}(\log^2 n)$ time
von: Holm, Jacob, et al.
Veröffentlicht: (2025)

Functional design of efficient and parallelizable combinatorial generators using convolution
von: He, Xi, et al.
Veröffentlicht: (2025)

Building a Balanced k-d Tree in O(kn log n) Time
von: Brown, Russell A.
Veröffentlicht: (2014)

LZBE: an LZ-style compressor supporting $O(\log n)$-time random access
von: Shibata, Hiroki, et al.
Veröffentlicht: (2025)

A Refutation of Elmasry's $\tilde{O}(m \sqrt{n})$-Time Algorithm for Single-Source Shortest Paths
von: Atalig, Sunny, et al.
Veröffentlicht: (2025)

Sparsest cut and eigenvalue multiplicities on low degree Abelian Cayley graphs
von: d'Orsi, Tommaso, et al.
Veröffentlicht: (2024)

Near-Optimal Parallel Approximate Counting via Sampling
von: Harris, David G., et al.
Veröffentlicht: (2026)

Folklore Sampling is Optimal for Exact Hopsets: Confirming the $\sqrt{n}$ Barrier
von: Bodwin, Greg, et al.
Veröffentlicht: (2023)

An $O(n\log n)$ Algorithm for Single-Item Lot Sizing with a One-Breakpoint All-Units Discount and Non-Increasing Prices
von: Papadopoulos, Kleitos
Veröffentlicht: (2025)

PCF Learned Sort: a Learning Augmented Sort Algorithm with $O(n \log\log n)$ Expected Complexity
von: Sato, Atsuki, et al.
Veröffentlicht: (2024)

A $(2+\varepsilon)$-approximation algorithm for the general scheduling problem in quasipolynomial time
von: Armbruster, Alexander, et al.
Veröffentlicht: (2025)

Parameter estimation for Gibbs distributions
von: Harris, David G., et al.
Veröffentlicht: (2020)

Faster $(Δ+ 1)$-Edge Coloring: Breaking the $m \sqrt{n}$ Time Barrier
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2024)

Testable algorithms for approximately counting edges and triangles in sublinear time and space
von: Eden, Talya, et al.
Veröffentlicht: (2025)