24 citations · 40 across the 9 of their papers we have counts for
Showing 2020Show all
2 papers · 1 filter
cs.DS2020
Dual Half-integrality for Uncrossable Cut Cover and its Application to Maximum Half-Integral Flow
Naveen Garg, Nikhil Kumar
Given an edge weighted graph and a forest , the is to pick a minimum weighted set of edges, , such that every connected c…
cs.DS2020
Integer Plane Multiflow Maximisation : Flow-Cut Gap and One-Quarter-Approximation
Naveen Garg, Nikhil Kumar, András Sebő
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 un…