Image de couverture de livre

Improved Lower Bounds on Multiflow-Multicut Gaps

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Kalantarzadeh, Sina, Kumar, Nikhil
Format:	Preprint
Publié:	2025
Sujets:	Discrete Mathematics
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

On the Gap between Hereditary Discrepancy and the Determinant Lower Bound
par: Li, Lily, et autres
Publié: (2023)

Box Facets and Cut Facets of Lifted Multicut Polytopes
par: Naumann, Lucas Fabian, et autres
Publié: (2024)

Weighted Group Search on the Disk & Improved Lower Bounds for Priority Evacuation
par: Georgiou, Konstantinos, et autres
Publié: (2024)

Another Way to Lower the Bound for Distinct Squares
par: Tomita, Eitatsu, et autres
Publié: (2026)

An Improved Bound for the Beck-Fiala Conjecture
par: Bansal, Nikhil, et autres
Publié: (2025)

Lower Bounds for the Minimum Spanning Tree Cycle Intersection Problem
par: Dubinsky, Manuel, et autres
Publié: (2024)

Lower Bounds for Maximum Weight Bisections of Graphs with Bounded Degrees
par: Gerke, Stefanie, et autres
Publié: (2024)

Lower Bounds for Induced-Universal Graphs
par: Gavoille, Cyril, et autres
Publié: (2025)

Lower Bounds for Maximum Weighted Cut
par: Gutin, Gregory, et autres
Publié: (2021)

An Integer Linear Program for Periodic Scheduling in Universities
par: Moradi, Sina
Publié: (2024)

Lower Bounds and properties for the average number of colors in the non-equivalent colorings of a graph
par: Hertz, Alain, et autres
Publié: (2021)

An Approximate Generalization of the Okamura-Seymour Theorem
par: Kumar, Nikhil
Publié: (2022)

An Improved Lower Bound on the Number of Pseudoline Arrangements
par: Kühnast, Fernando Cortés, et autres
Publié: (2024)

Lower Bound on Howard Policy Iteration for Deterministic Markov Decision Processes
par: Asadi, Ali, et autres
Publié: (2025)

Optimal Padded Decomposition For Bounded Treewidth Graphs
par: Filtser, Arnold, et autres
Publié: (2024)

Ramanujan Graphs and Interlacing Families
par: Srivastava, Nikhil
Publié: (2024)

Computing Lower Bounds on the Nonnegative Rank via Non-Convex Optimization Solvers
par: Baeckelant, Timothy, et autres
Publié: (2026)

Tight Lower Bound for Multicolor Discrepancy
par: Manurangsi, Pasin, et autres
Publié: (2025)

Linear Exact Repair in MDS Array Codes: A General Lower Bound and Its Attainability
par: Liu, Hai, et autres
Publié: (2026)

Lower Bounds for Linear Operators
par: Ko, Young Kun
Publié: (2025)

Lower bounds for dominating set reconfiguration on sparse (directed) graphs
par: Dirks, Jona, et autres
Publié: (2025)

Weighted Treedepth is NP-complete on Graphs of Bounded Degree
par: Dirks, Jona, et autres
Publié: (2025)

A Lower Bound on the Competitive Ratio of the Permutation Algorithm for Online Facility Assignment on a Line
par: Harada, Tsubasa
Publié: (2024)

Decoupling via Affine Spectral-Independence: Beck-Fiala and Komlós Bounds Beyond Banaszczyk
par: Bansal, Nikhil, et autres
Publié: (2025)

A Computer-Assisted Proof of the Optimal Density Bound for Pinwheel Covering
par: Kawamura, Akitoshi, et autres
Publié: (2025)

Circulant TSP: Vertices of the Edge-Length Polytope and Superpolynomial Lower Bounds
par: Gutekunst, Samuel C.
Publié: (2025)

A Tight Lower Bound on Cubic Vertices and Upper Bounds on Thin and Non-thin edges in Planar Braces
par: De, Koustav
Publié: (2025)

An $Ω(n \log n)$ Randomized Lower Bound for Cutting a Cake into Proportionally Fair Pieces
par: Arndt, Stephen, et autres
Publié: (2026)

Improved Upper Bound for the Size of a Trifferent Code
par: Bhandari, Siddharth, et autres
Publié: (2024)

Dual Bounded Generation: Polynomial, Second-order Cone and Positive Semidefinite Matrix Inequalities
par: Elbassioni, Khaled
Publié: (2024)

Bounds on Path Energy of Graphs
par: Narke, Amol P., et autres
Publié: (2022)

Accelerated Evaluation of Ollivier-Ricci Curvature Lower Bounds: Bridging Theory and Computation
par: Kang, Wonwoo, et autres
Publié: (2024)

Super-linear Lower Bounds for CSP Non-Redundancy via Shrinking Instances
par: Brakensiek, Joshua, et autres
Publié: (2026)

Polynomial Bounds in the Apex Minor Theorem
par: Hendrey, Kevin, et autres
Publié: (2025)

Supports for Outerplanar and Bounded Treewidth Graphs
par: Raman, Rajiv, et autres
Publié: (2025)

Bounds on Linear Turán Number for Trees
par: Adak, Rajat, et autres
Publié: (2026)

Bounds on the Complete Forcing Number of Graphs
par: Ebrahimi, Javad B., et autres
Publié: (2024)

Multi-Pass Streaming Lower Bounds for Approximating Max-Cut
par: Fei, Yumou, et autres
Publié: (2025)

On Obtaining New MUBs by Finding Points on Complete Intersection Varieties over $\mathbb{R}$
par: Banerjee, Arindam, et autres
Publié: (2025)

Optimal Tree-Decompositions with Bags of Bounded Treewidth
par: Hendrey, Kevin, et autres
Publié: (2025)