Integer Plane Multiflow Maximisation: Flow-Cut Gap and One-Quarter-Approximation

DOI10.1007/978-3-030-45771-6_12zbMath1503.90147arXiv2002.10927OpenAlexW3017192358MaRDI QIDQ5041741

Naveen Garg, N. Kumar, András Sebő

Publication date: 14 October 2022

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2002.10927

zbMATH Keywords

approximation algorithmplanar graphsnetwork designmulticommodity flowintegrality gapmulticutmultiflowflow-cut

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Related Items (6)

Approximating maximum integral multiflows on bounded genus graphs ⋮ Dual Half-Integrality for Uncrossable Cut Cover and Its Application to Maximum Half-Integral Flow ⋮ Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators ⋮ Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators ⋮ An Approximation Algorithm for Fully Planar Edge-Disjoint Paths ⋮ Integer plane multiflow maximisation: one-quarter-approximation and gaps

Cites Work

• 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
• Matching theory
• 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
• 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
• Excluded minors, network decomposition, and multicommodity flow
• Maximum Edge-Disjoint Paths in Planar Graphs with Congestion 2
• Lectures on matroids
• Combinatorial optimization. Theory and algorithms.

This page was built for publication: Integer Plane Multiflow Maximisation: Flow-Cut Gap and One-Quarter-Approximation