Dual-Based Approximation Algorithms for Cut-Based Network Connectivity Problems

Benjamin Grimmer

We consider a variety of NP-Complete network connectivity problems. We introduce a novel dual-based approach to approximating network design problems with cut-based linear programm…