Integer plane multiflow maximisation: flow-cut gap and one-quarter-approximation

DOI10.1007/978-3-030-45771-6_12MaRDI QIDQ5041741zbMATH OpenOpenAlexFDO

Authors 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 algorithmflow-cutintegrality gapmulticommodity flowmulticutmultiflownetwork designplanar graphs

Mathematics Subject Classification ID

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

Abstract: In this paper, we bound the integrality gap and the approximation ratio for maximum plane multiflow problems and deduce bounds on the flow-cut-gap. Planarity means here that the union of the supply and demand graph is planar. We first prove that there exists a multiflow of value at least half of the capacity of a minimum multicut. We then show how to convert any multiflow into a half-integer one of value at least half of the original multiflow. Finally, we round any half-integer multiflow into an integer multiflow, losing again at most half of the value, in polynomial time, achieving a $1/4$-approximation algorithm for maximum integer multiflows in the plane, and an integer-flow-cut gap of $8$.

Recommendations

• Integer plane multiflow maximisation: one-quarter-approximation and gaps
• Integer plane multiflows with a mixed number of demands
• Flow-cut gaps for integer and fractional multiflows
• Flow-cut gaps for integer and fractional multiflows
• Approximate max-integral-flow/min-multicut theorems

Cites work

• A note on packing paths in planar graphs
• A primal-dual approximation algorithm for generalized Steiner network problems
• A proof of the four color theorem
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• Approximate min-max relations for odd cycles in planar graphs
• Approximation algorithms for NP-complete problems on planar graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Combinatorial optimization. Theory and algorithms.
• Correlation clustering and two-edge-connected augmentation for planar graphs
• Edge-disjoint odd cycles in planar graphs.
• Excluded minors, network decomposition, and multicommodity flow
• scientific article; zbMATH DE number 3121293 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3580570 (Why is no real title available?)
• scientific article; zbMATH DE number 1256776 (Why is no real title available?)
• Improved bounds for the max-flow min-multicut ratio for planar and \(K_{r,r}\)-free graphs
• Lectures on matroids
• Matching theory
• Maximum Edge-Disjoint Paths in Planar Graphs with Congestion 2
• Multicommodity flows in planar graphs
• On Odd Cuts and Plane Multicommodity Flows
• On the complexity of the disjoint paths problem
• On the integrality ratio for tree augmentation
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Tight integral duality gap in the Chinese postman problem

Cited in

(10)

• Integer plane multiflows with a mixed number of demands
• Flow-cut gaps for integer and fractional multiflows
• Integer plane multiflow maximisation: one-quarter-approximation and gaps
• An Approximation Algorithm for Fully Planar Edge-Disjoint Paths
• Flow-cut gaps for integer and fractional multiflows
• 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
• Approximating maximum integral multiflows on bounded genus graphs
• Approximating maximum integral multiflows on bounded genus graphs

This page was built for publication: Integer plane multiflow maximisation: flow-cut gap and one-quarter-approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5041741)