Cover Image

Minimum Cost Nowhere-zero Flows and Cut-balanced Orientations

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chandrasekaran, Karthekeyan, Liu, Siyue, Ravi, R.
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Combinatorics Optimization and Control
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On the Congruency-Constrained Matroid Base
by: Liu, Siyue, et al.
Published: (2023)

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

Automated Discovery of Branching Rules with Optimal Complexity for the Maximum Independent Set Problem
by: Gao, Xuan-Zhao, et al.
Published: (2024)

Totally $Δ$-modular IPs with two non-zeros in most rows
by: Kober, Stefan
Published: (2024)

A Threshold Phenomenon for the Shortest Lattice Vector Problem in the Infinity Norm
by: Kuhlmann, Stefan, et al.
Published: (2025)

On Matrices over a Polynomial Ring with Restricted Subdeterminants
by: Celaya, Marcel, et al.
Published: (2023)

Lattice Structure and Efficient Basis Construction for Strongly Connected Orientations
by: Liu, Siyue, et al.
Published: (2026)

Theoretical Approximation Ratios for Warm-Started QAOA on 3-Regular Max-Cut Instances at Depth $p=1$
by: Tate, Reuben, et al.
Published: (2024)

Improved Speed via Regional Fulfillment
by: Hathcock, Daniel, et al.
Published: (2026)

Vertex-ordering and arc-partitioning problems
by: Borsik, Nóra A., et al.
Published: (2025)

Max-Min and 1-Bounded Space Algorithms for the Bin Packing Problem
by: Fujiwara, Hiroshi, et al.
Published: (2025)

Separable convex optimization over indegree polytopes
by: Borsik, Nóra A., et al.
Published: (2025)

Prefix-bounded matrices
by: Borsik, Nóra A., et al.
Published: (2025)

The Lovász Theta Function for Recovering Planted Clique Covers and Graph Colorings
by: Hou, Jiaxin, et al.
Published: (2023)

Integer programs with bounded subdeterminants and two nonzeros per row
by: Fiorini, Samuel, et al.
Published: (2021)

Complexity of polytope diameters via perfect matchings
by: Nöbel, Christian, et al.
Published: (2024)

Integer programs with nearly totally unimodular matrices: the cographic case
by: Aprile, Manuel, et al.
Published: (2024)

Total Matching and Subdeterminants
by: Ferrarini, Luca, et al.
Published: (2023)

On Approximation of Robust Max-Cut and Related Problems using Randomized Rounding Algorithms
by: Shi, Haoyan, et al.
Published: (2024)

A Decomposition Theorem for Dynamic Flows
by: Graf, Lukas, et al.
Published: (2024)

Accelerated Approximate Optimization of Multi-Commodity Flows on Directed Graphs
by: Chen, Li, et al.
Published: (2025)

Improved Upper Bounds for the Directed Flow-Cut Gap
by: Bodwin, Greg, et al.
Published: (2026)

On the Distribution of Unweighted Minimum Knapsack Instances with Large SOS Rank
by: Kurpisz, Adam, et al.
Published: (2026)

Efficient approximation schemes for scheduling on a stochastic number of machines
by: Epstein, Leah, et al.
Published: (2024)

Algorithmic aspects of semistability of quiver representations
by: Iwamasa, Yuni, et al.
Published: (2024)

NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability
by: Kar, Prem Nigam, et al.
Published: (2024)

A Θ(m^9) ternary minimum-cost network flow LP model of the Assignment Problem polytope with applications to hard combinatorial optimization problems
by: Diaby, Moustapha
Published: (2016)

Online Disjoint Spanning Trees and Polymatroid Bases
by: Chandrasekaran, Karthekeyan, et al.
Published: (2025)

On Deleting Vertices to Reduce Density in Graphs and Supermodular Functions
by: Chandrasekaran, Karthekeyan, et al.
Published: (2025)

Monotone Submodular Multiway Partition
by: Bi, Richard, et al.
Published: (2024)

Quantum Approximate Optimization Algorithms for Maximum Cut on Low-Girth Graphs
by: Li, Tongyang, et al.
Published: (2024)

Expected Maximin Fairness in Max-Cut and other Combinatorial Optimization Problems
by: Salem, Jad, et al.
Published: (2024)

Phylogenetic Inference under the Balanced Minimum Evolution Criterion via Semidefinite Programming
by: Skums, P.
Published: (2026)

New Sequence-Independent Lifting Techniques for Cutting Planes and When They Induce Facets
by: Prasad, Siddharth, et al.
Published: (2024)

Dynamic Pricing for Reusable Resources: The Power of Two Prices
by: Balseiro, Santiago R., et al.
Published: (2023)

Fast and Flexible Flow Decompositions in General Graphs via Dominators
by: Sena, Francisco, et al.
Published: (2025)

Dynamic Batching of Online Arrivals to Leverage Economies of Scale
by: Bhimaraju, Akhil, et al.
Published: (2023)

Differentiable Extensions with Rounding Guarantees for Combinatorial Optimization over Permutations
by: Nerem, Robert R., et al.
Published: (2024)

A Primal-Dual Extension of the Goemans--Williamson Algorithm for the Weighted Fractional Cut-Covering Problem
by: Proença, Nathan Benedetto, et al.
Published: (2023)

Adaptive Matrix Sparsification and Applications to Empirical Risk Minimization
by: Liu, Yang P., et al.
Published: (2025)