Improved Hardness for Cut, Interdiction, and Firefighter Problems

DOI10.4230/LIPIcs.ICALP.2017.92zbMath1442.68067arXiv1607.05133OpenAlexW2963724423MaRDI QIDQ5111424

Euiwoong Lee

Publication date: 27 May 2020

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

zbMATH Keywords

unique games conjecturemulticutfirefighterlength-bounded cutshortest path interdiction

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (8)

Asymptotic quasi-polynomial time approximation scheme for resource minimization for fire containment ⋮ On Polynomial-Time Combinatorial Algorithms for Maximum $L$-Bounded Flow ⋮ A tight \(\sqrt{2} \)-approximation for linear 3-cut ⋮ Unnamed Item ⋮ Minimum Violation Vertex Maps and Their Applications to Cut Problems ⋮ On Algorithms Employing Treewidth for $L$-bounded Cut Problems ⋮ Beating the 2-approximation factor for global bicut ⋮ The Quest for Strong Inapproximability Results with Perfect Completeness

This page was built for publication: Improved Hardness for Cut, Interdiction, and Firefighter Problems