Dual Half-Integrality for Uncrossable Cut Cover and Its Application to Maximum Half-Integral Flow

DOI10.4230/LIPIcs.ESA.2020.55OpenAlexW3081626558MaRDI QIDQ5874526

Naveen Garg, N. Kumar

Publication date: 7 February 2023

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

zbMATH Keywords

combinatorial optimizationnetwork designmulticommodity flow

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items (1)

Integer plane multiflow maximisation: one-quarter-approximation and gaps

Cites Work

• Primal-dual approximation algorithms for integral flow and multicut in trees
• A factor 2 approximation algorithm for the generalized Steiner network problem
• A primal-dual approximation algorithm for generalized Steiner network problems
• A General Approximation Technique for Constrained Forest Problems
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
• 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

This page was built for publication: Dual Half-Integrality for Uncrossable Cut Cover and Its Application to Maximum Half-Integral Flow