Buchumschlag

A Subquadratic Two-Party Communication Protocol for Minimum Cost Flow

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Gholizadeh, Hossein, Jiang, Yonggang
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Data Structures and Algorithms Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Parallel Minimum Cost Flow in Near-Linear Work and Square Root Depth for Dense Instances
von: Brand, Jan van den, et al.
Veröffentlicht: (2025)

Minimum Stable Cut and Treewidth
von: Lampis, Michael
Veröffentlicht: (2021)

Pseudodeterministic Algorithms for Minimum Cut Problems
von: Agarwala, Aryan, et al.
Veröffentlicht: (2025)

On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems
von: DeHaan, Ian, et al.
Veröffentlicht: (2025)

On the Inapproximability of Finding Minimum Monitoring Edge-Geodetic Sets
von: Bilò, Davide, et al.
Veröffentlicht: (2024)

Fast Leaf-to-Ancestor Minimum Query in the Oracle Model
von: Upirvitskiy, Aleksey, et al.
Veröffentlicht: (2026)

Self-referential instances of the dominating set problem are irreducible
von: Zhou, Guangyan
Veröffentlicht: (2026)

Improved Hardness and Approximations for Cardinality-Based Minimum $s$-$t$ Cuts Problems in Hypergraphs
von: Adriaens, Florian, et al.
Veröffentlicht: (2024)

The Art of Staying Ahead of Deadlines: Improved Algorithms for the Minimum Tardy Processing Time
von: Stoian, Mihail
Veröffentlicht: (2024)

On Permutation Selectors and their Applications in Ad-Hoc Radio Networks Protocols
von: Kuschner, Jordan, et al.
Veröffentlicht: (2024)

Sumplete is Hard, Even with Two Different Numbers
von: Ruangwises, Suthee
Veröffentlicht: (2023)

Better Boosting of Communication Oracles, or Not
von: Harms, Nathaniel, et al.
Veröffentlicht: (2024)

Structural Parameterizations for Two Bounded Degree Problems Revisited
von: Lampis, Michael, et al.
Veröffentlicht: (2023)

Finding One Local Optimum Is Easy -- but What About Two?
von: Kobayashi, Yasuaki, et al.
Veröffentlicht: (2025)

Finding Minimum Distance Preservers: A Parameterized Study
von: Simonov, Kirill, et al.
Veröffentlicht: (2026)

Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints
von: Kim, Eun Jung, et al.
Veröffentlicht: (2022)

On Stable Cutsets in General and Minimum Degree Constrained Graphs
von: Vroon, Mats, et al.
Veröffentlicht: (2025)

Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length Streams
von: Jiang, Cheng, et al.
Veröffentlicht: (2026)

On the Distribution of Unweighted Minimum Knapsack Instances with Large SOS Rank
von: Kurpisz, Adam, et al.
Veröffentlicht: (2026)

Near-Optimality for Single-Source Personalized PageRank
von: Jiang, Xinpeng, et al.
Veröffentlicht: (2025)

Certificates in P and Subquadratic-Time Computation of Radius, Diameter, and all Eccentricities in Graphs
von: Dragan, Feodor F., et al.
Veröffentlicht: (2018)

Finding a Minimum Spanning Tree with a Small Non-Terminal Set
von: Hanaka, Tesshu, et al.
Veröffentlicht: (2023)

NP-Completeness of Deterministic Communication Complexity via Relaxed Interlacing
von: Gaspers, Serge, et al.
Veröffentlicht: (2025)

On Approximating the Dynamic and Discrete Network Flow Problem
von: Manna, Bubai, et al.
Veröffentlicht: (2024)

A Dichotomy Theorem for Multi-Pass Streaming CSPs
von: Fei, Yumou, et al.
Veröffentlicht: (2025)

A Note on Approximability of Densest At-Least-k-Subgraph
von: Laekhanukit, Bundit, et al.
Veröffentlicht: (2026)

A Simple Proof that Ricochet Robots is PSPACE-Complete
von: Balanza-Martinez, Jose, et al.
Veröffentlicht: (2024)

A Faster Randomized Algorithm for Vertex Cover: An Automated Approach
von: Clinch, Katie, et al.
Veröffentlicht: (2025)

A Complexity Analysis of the c-Closed Vertex Deletion Problem
von: Lehner, Lisa, et al.
Veröffentlicht: (2025)

A Space-space Trade-off for Directed st-Connectivity
von: Edenhofer, Roman
Veröffentlicht: (2026)

A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
von: Buhrman, Harry, et al.
Veröffentlicht: (2025)

Connectivity-Preserving Important Separators: A Framework for Cut-Uncut Problems
von: Kenig, Batya
Veröffentlicht: (2025)

A fine-grained dichotomy for the center problem on Gromov hyperbolic graphs
von: Ducoffe, Guillaume
Veröffentlicht: (2026)

A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted Structures
von: Garg, Sumegha, et al.
Veröffentlicht: (2026)

A tight quasi-polynomial bound for Global Label Min-Cut
von: Jaffke, Lars, et al.
Veröffentlicht: (2022)

A New Information Complexity Measure for Multi-pass Streaming with Applications
von: Braverman, Mark, et al.
Veröffentlicht: (2024)

Clustering Permutations under the Ulam Metric: A Parameterized Complexity Study
von: Bai, Tian, et al.
Veröffentlicht: (2026)

A Tight Double-Exponentially Lower Bound for High-Multiplicity Bin Packing
von: Jansen, Klaus, et al.
Veröffentlicht: (2025)

A lossless a priori splitting rule for split-delivery routing problems
von: Jones, Bo, et al.
Veröffentlicht: (2025)

Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
von: S., Karthik C., et al.
Veröffentlicht: (2023)