Imagen de Portada

Improved Upper Bounds for the Directed Flow-Cut Gap

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Bodwin, Greg, Samborska, Luba
Formato:	Preprint
Publicado:	2026
Materias:	Data Structures and Algorithms Combinatorics
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Improved Shortest Path Restoration Lemmas for Multiple Edge Failures: Trade-offs Between Fault-tolerance and Subpaths
por: Bodwin, Greg, et al.
Publicado: (2023)

A Unified View of Graph Regularity via Matrix Decompositions
por: Bodwin, Greg, et al.
Publicado: (2019)

Notes on the Linear Algebraic View of Regularity Lemmas
por: Bodwin, Greg, et al.
Publicado: (2025)

An Alternate Proof of Near-Optimal Light Spanners
por: Bodwin, Greg
Publicado: (2023)

A Lower Bound for Light Spanners in General Graphs
por: Bodwin, Greg, et al.
Publicado: (2024)

Light Edge Fault Tolerant Graph Spanners
por: Bodwin, Greg, et al.
Publicado: (2025)

Improved Online Reachability Preservers
por: Bodwin, Greg, et al.
Publicado: (2024)

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

An Improved Upper Bound for the Euclidean TSP Constant Using Band Crossovers
por: Gaudio, Julia, et al.
Publicado: (2026)

Oblivious Algorithms for Maximum Directed Cut: New Upper and Lower Bounds
por: Hwang, Samuel, et al.
Publicado: (2024)

Sharp Bounds on the Eigenvalues of Kikuchi Graphs and Applications to Quantum Max Cut
por: Bakshi, Ainesh, et al.
Publicado: (2026)

Multiplicative Spanners in Minor-Free Graphs
por: Bodwin, Greg, et al.
Publicado: (2025)

Are there graphs whose shortest path structure requires large edge weights?
por: Bernstein, Aaron, et al.
Publicado: (2023)

Additive Spanner Lower Bounds with Optimal Inner Graph Structure
por: Bodwin, Greg, et al.
Publicado: (2024)

Minimum Cost Nowhere-zero Flows and Cut-balanced Orientations
por: Chandrasekaran, Karthekeyan, et al.
Publicado: (2025)

Optimal Bounds for Distinct Quartics
por: Charalampopoulos, Panagiotis, et al.
Publicado: (2024)

Lower Bounds on Tree Covers
por: Chen, Yu, et al.
Publicado: (2025)

An Improved Bound for the Beck-Fiala Conjecture
por: Bansal, Nikhil, et al.
Publicado: (2025)

Optimal Bounds for Open Addressing Without Reordering
por: Farach-Colton, Martin, et al.
Publicado: (2025)

A Lower Bound for the Max Entropy Algorithm for TSP
por: Jin, Billy, et al.
Publicado: (2023)

Complexity Gaps between Point and Interval Temporal Graphs for some Reachability Problems
por: Aubian, Guillaume, et al.
Publicado: (2025)

A Simple and Combinatorial Approach to Proving Chernoff Bounds and Their Generalizations
por: Kuszmaul, William
Publicado: (2025)

Dichotomies for Maximum Matching Cut: $H$-Freeness, Bounded Diameter, Bounded Radius
por: Lucke, Felicia, et al.
Publicado: (2023)

A Maximum Linear Arrangement Problem on Directed Graphs
por: DeVos, Matt, et al.
Publicado: (2018)

Improved exploration of temporal graphs
por: Bastide, Paul, et al.
Publicado: (2025)

Cuts in Graphs with Matroid Constraints
por: Banik, Aritra, et al.
Publicado: (2024)

Simple Length-Constrained Expander Decompositions
por: Bodwin, Greg, et al.
Publicado: (2025)

Finding d-Cuts in Graphs of Bounded Diameter, Graphs of Bounded Radius and H-Free Graphs
por: Lucke, Felicia, et al.
Publicado: (2024)

Min-Max Connected Multiway Cut
por: Tiwary, Hans Raj, et al.
Publicado: (2026)

Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut
por: Cheng, Yu, et al.
Publicado: (2024)

Opponent Indifference in Rating Systems: A Theoretical Case for Sonas
por: Bodwin, Greg, et al.
Publicado: (2022)

Improved space-time tradeoff for TSP via extremal set systems
por: Dallant, Justin, et al.
Publicado: (2026)

EPTAS for Hard Graph Cut Problems for Dense Graphs
por: Deguchi, Kaisei, et al.
Publicado: (2026)

Thin Trees via $k$-Respecting Cut Identities
por: Daga, Mohit
Publicado: (2025)

Towards the Characterization of Terminal Cut Functions: a Condition for Laminar Families
por: Chen, Yu, et al.
Publicado: (2023)

Subsequences With Generalised Gap Constraints: Upper and Lower Complexity Bounds
por: Manea, Florin, et al.
Publicado: (2024)

The Discrepancy of Shortest Paths
por: Bodwin, Greg, et al.
Publicado: (2024)

Comparison of Hyperplane Rounding for Max-Cut and Quantum Approximate Optimization Algorithm over Certain Regular Graph Families
por: Tate, Reuben, et al.
Publicado: (2025)

Forest Covers and Bounded Forest Covers
por: Gaur, Daya Ram, et al.
Publicado: (2024)

Tight Bounds for Sparsifying Random CSPs
por: Brakensiek, Joshua, et al.
Publicado: (2025)