Integer plane multiflow maximisation: one-quarter-approximation and gaps
From MaRDI portal
Publication:2089777
DOI10.1007/s10107-021-01700-8zbMath1504.90172OpenAlexW3110949939MaRDI QIDQ2089777
Naveen Garg, András Sebő, N. Kumar
Publication date: 24 October 2022
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-021-01700-8
approximation algorithmplanar graphsnetwork designmulticommodity flowintegrality gapmulticutmultiflowflow-multicut
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Primal-dual approximation algorithms for integral flow and multicut in trees
- Improved bounds for the max-flow min-multicut ratio for planar and \(K_{r,r}\)-free graphs
- Approximate min-max relations for odd cycles in planar graphs
- On the integrality ratio for tree augmentation
- Multicommodity flows in planar graphs
- Tight integral duality gap in the Chinese postman problem
- A proof of the four color theorem
- Edge-disjoint odd cycles in planar graphs.
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- A primal-dual approximation algorithm for generalized Steiner network problems
- A note on packing paths in planar graphs
- On the complexity of the disjoint paths problem
- Planar Multicommodity Fows, Maximum Matchings and Negative Cycles
- On Odd Cuts and Plane Multicommodity Flows
- Approximation algorithms for NP-complete problems on planar graphs
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
- Integer Plane Multiflow Maximisation: Flow-Cut Gap and One-Quarter-Approximation
- Excluded minors, network decomposition, and multicommodity flow
- Maximum Edge-Disjoint Paths in Planar Graphs with Congestion 2
- Lectures on matroids
- Dual Half-Integrality for Uncrossable Cut Cover and Its Application to Maximum Half-Integral Flow
- Combinatorial optimization. Theory and algorithms.
This page was built for publication: Integer plane multiflow maximisation: one-quarter-approximation and gaps
