Solving \((k-1)\)-stable instances of \texttt{k-terminal cut} with isolating cuts

DOI10.1007/s10878-021-00769-3zbMath1490.90298OpenAlexW2977561619MaRDI QIDQ2125213

Mark Velednitsky

Publication date: 13 April 2022

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-021-00769-3

zbMATH Keywords

stabilityapproximation\(k\)-terminal cutisolating cuts

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Cites Work

• Unnamed Item
• Unnamed Item
• Robust solutions of linear programming problems contaminated with uncertain data
• Isolation branching: a branch and bound algorithm for the k-terminal cut problem
• An improved integrality gap for the Călinescu-Karloff-Rabani relaxation for multiway cut
• Rounding algorithms for a geometric embedding of minimum multiway cut
• Are Stable Instances Easy?
• Powers of tensors and fast matrix multiplication
• A Characterization of Stability in Linear Programming
• The Complexity of Multiterminal Cuts
• Algorithms for stable and perturbation-resilient problems
• Solving linear programs in the current matrix multiplication time
• Multiway cut, pairwise realizable distributions, and descending thresholds
• Bilu–Linial Stable Instances of Max Cut and Minimum Multiway Cut
• Simplex partitioning via exponential clocks and the multiway cut problem

This page was built for publication: Solving \((k-1)\)-stable instances of \texttt{k-terminal cut} with isolating cuts