Approximation Algorithms and Hardness of the k -Route Cut Problem

DOI10.1145/2644814zbMath1398.68665arXiv1112.3611OpenAlexW4302769223MaRDI QIDQ4962202

Yuan Zhou, Yury Makarychev, Julia Chuzhoy, Aravindan Vijayaraghavan

Publication date: 30 October 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithm\(k\)-route cut problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (5)

The Densest $k$-Subhypergraph Problem ⋮ Vertex downgrading to minimize connectivity ⋮ Unnamed Item ⋮ A note on degree vs gap of Min-Rep label cover and improved inapproximability for connectivity problems ⋮ The complexity of mixed-connectivity

This page was built for publication: Approximation Algorithms and Hardness of the k -Route Cut Problem