An improved approximation algorithm of MULTIWAY CUT.

DOI10.1006/jcss.1999.1687zbMath0986.90043OpenAlexW3009415557MaRDI QIDQ1577011

Gruia Călinescu, Yuval Rabani, Howard J. Karloff

Publication date: 21 November 2000

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.1999.1687

zbMATH Keywords

linear programming relaxationundirected graphMULTIWAY CUT of minimum cost

Mathematics Subject Classification ID

Linear programming (90C05) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items

On the (near) optimality of extended formulations for multi-way cut in social networks, Approximation and hardness results for the max \(k\)-uncut problem, Approximation algorithms for requirement cut on graphs, An improved parameterized algorithm for the minimum node multiway cut problem, Improved Approximation Algorithms for the Maximum Happy Vertices and Edges Problems, \(\ell_p\)-norm multiway cut, Global and fixed-terminal cuts in digraphs, Simplex Partitioning via Exponential Clocks and the Multiway-Cut Problem, Clique Cover and Graph Separation, Vertex downgrading to minimize connectivity, Algorithms for Multiterminal Cuts, Strategic cooperation in cost sharing games, Approximation and Hardness Results for the Max k-Uncut Problem, Approximation algorithms for \(k\)-hurdle problems, An approximation algorithm for the generalized \(k\)-multicut problem, The evolution of rectangular bin packing problem -- a review of research topics, applications, and cited papers, Strategic multiway cut and multicut games, Models and methods for solving the problem of network vulnerability, Geometric multicut: shortest fences for separating groups of objects in the plane, Generating partitions of a graph into a fixed number of minimum weight cuts, On the advantage of overlapping clusters for minimizing conductance, Cut problems in graphs with a budget constraint, Algorithmic aspects of homophyly of networks, How to Cut a Graph into Many Pieces, Submodular Cost Allocation Problem and Applications, Approximating Requirement Cut via a Configuration LP, Improved approximation algorithms for the maximum happy vertices and edges problems, Discrete and continuous models for partitioning problems, Optimal 3-terminal cuts and linear programming, Greedy splitting algorithms for approximating multiway partition problems, Unnamed Item, Simple and improved parameterized algorithms for multiterminal cuts, Unnamed Item, Approximation Algorithms for k-Hurdle Problems, A simple algorithm for the multiway cut problem, Improving the integrality gap for multiway cut, Beating the 2-approximation factor for global bicut, Simplex Transformations and the Multiway Cut Problem, On a bidirected relaxation for the MULTIWAY CUT problem, Clustering with qualitative information

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Geometric algorithms and combinatorial optimization.
• On weighted multiway cuts in trees
• Extended formulations for the \(A\)-cut problem
• An $O ( | V |^2 )$ Algorithm for the Planar 3-Cut Problem
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• On the multiway cut polyhedron
• Multiprocessor Scheduling with the Aid of Network Flow Algorithms
• The Complexity of Multiterminal Cuts
• A new approach to the minimum cut problem
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• Nonlinear formulations and improved randomized approximation algorithms for multicut problems