A lower bound of \(8/(7+\frac{1}{k-1})\) on the integrality ratio of the Călinescu-Karloff-Rabani relaxation for multiway cut
type: Item
instance of: scholarly article
title: A lower bound of \(8/(7+\frac{1}{k-1})\) on the integrality ratio of the Călinescu-Karloff-Rabani relaxation for multiway cut
zbMATH Open document ID: 1339.68204
DOI: 10.1016/S0020-0190(00)00065-X
author: Ari Freund
author: Howard Karloff
published in: Information Processing Letters
publication date: 2016-06-16T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 90C35
zbMATH DE Number: 6594110
zbMATH Keywords: graph algorithms
zbMATH Keywords: multiway cuts
zbMATH Keywords: lower bounds
zbMATH Keywords: approximation ratio
MaRDI profile type: Publication
cites work: Q4234075
cites work: Nonlinear formulations and improved randomized approximation algorithms for multicut problems
cites work: Q4542519
cites work: On the multiway cut polyhedron
cites work: Q4035360
cites work: Q4263706
cites work: The Complexity of Multiterminal Cuts
cites work: On minimum 3-cuts and approximating k-cuts using Cut Trees
cites work: Rounding algorithms for a geometric embedding of minimum multiway cut
full work available at URL: s0020-0190(00)00065-x
OpenAlex ID: W1985219023
description: scientific article; zbMATH DE number 6594110