A lower bound of \(8/(7+\frac{1}{k-1})\) on the integrality ratio of the Călinescu-Karloff-Rabani relaxation for multiway cut (Q294793): Difference between revisions

Latest revision as of 11:00, 30 July 2024

scientific article

Language	Label	Description	Also known as
English	A lower bound of \(8/(7+\frac{1}{k-1})\) on the integrality ratio of the Călinescu-Karloff-Rabani relaxation for multiway cut	scientific article

Statements

instance of

scholarly article

0 references

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 (English)

0 references

0 references

0 references

Information Processing Letters

0 references

publication date

16 June 2016

0 references

zbMATH Keywords

graph algorithms

0 references

multiway cuts

0 references

lower bounds

0 references

approximation ratio

0 references

0 references

0 references

Nonlinear formulations and improved randomized approximation algorithms for multicut problems

0 references

Q4542519

0 references

On the multiway cut polyhedron

0 references

Q4035360

0 references

Q4263706

0 references

The Complexity of Multiterminal Cuts

0 references

On minimum 3-cuts and approximating k-cuts using Cut Trees

0 references

Rounding algorithms for a geometric embedding of minimum multiway cut

0 references

full work available at URL

https://doi.org/10.1016/s0020-0190(00)00065-x

0 references

Identifiers

zbMATH Open document ID

1339.68204

0 references

DOI

10.1016/S0020-0190(00)00065-X

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:294793

@@ Property / author @@
-Howard J. Karloff
@@ Property / author: Howard J. Karloff / rank @@
-Normal rank
@@ Property / author @@
+Howard J. Karloff
@@ Property / author: Howard J. Karloff / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+R10
@@ Property / Mathematics Subject Classification ID: 68R10 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+C85
@@ Property / Mathematics Subject Classification ID: 05C85 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+Q17
@@ Property / Mathematics Subject Classification ID: 68Q17 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+W25
@@ Property / Mathematics Subject Classification ID: 68W25 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+C35
@@ Property / Mathematics Subject Classification ID: 90C35 / rank @@
+Normal rank
@@ Property / zbMATH DE Number @@
+6594110
@@ Property / zbMATH DE Number: 6594110 / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+graph algorithms
@@ Property / zbMATH Keywords: graph algorithms / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+multiway cuts
@@ Property / zbMATH Keywords: multiway cuts / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+lower bounds
@@ Property / zbMATH Keywords: lower bounds / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+approximation ratio
@@ Property / zbMATH Keywords: approximation ratio / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+Publication
@@ Property / MaRDI profile type: Publication / rank @@
+Normal rank
@@ Property / cites work @@
+Q4234075
@@ Property / cites work: Q4234075 / rank @@
+Normal rank
@@ Property / cites work @@
+Nonlinear formulations and improved randomized approximation algorithms for multicut problems
+Normal rank
@@ Property / cites work @@
+Q4542519
@@ Property / cites work: Q4542519 / rank @@
+Normal rank
@@ Property / cites work @@
+On the multiway cut polyhedron
@@ Property / cites work: On the multiway cut polyhedron / rank @@
+Normal rank
@@ Property / cites work @@
+Q4035360
@@ Property / cites work: Q4035360 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4263706
@@ Property / cites work: Q4263706 / rank @@
+Normal rank
@@ Property / cites work @@
+The Complexity of Multiterminal Cuts
@@ Property / cites work: The Complexity of Multiterminal Cuts / rank @@
+Normal rank
@@ Property / cites work @@
+On minimum 3-cuts and approximating k-cuts using Cut Trees
+Normal rank
@@ Property / cites work @@
+Rounding algorithms for a geometric embedding of minimum multiway cut
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/s0020-0190(00)00065-x
+Normal rank
@@ Property / OpenAlex ID @@
+W1985219023
@@ Property / OpenAlex ID: W1985219023 / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:294793