An approximation algorithm for the generalized k-multicut problem

DOI10.1016/J.DAM.2012.01.016zbMATH Open1255.68312OpenAlexW2088728264MaRDI QIDQ423940FDOQ423940

Authors: Daming Zhu, Junfeng Luan, Peng Zhang 

Publication date: 30 May 2012

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2012.01.016

Recommendations

• Approximating Generalized Multicut on Trees
• Partial multicuts in trees
• Generalized \(k\)-multiway cut problems
• Approximation and Online Algorithms
• On the generalized multiway cut in trees problem

zbMATH Keywords

combinatorial optimizationapproximation algorithmLP-rounding\(k\)-forest\(k\)-multicut

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cites Work

• Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
• The Complexity of Multiterminal Cuts
• A General Approximation Technique for Constrained Forest Problems
• The dense \(k\)-subgraph problem
• A note on the prize collecting traveling salesman problem
• Rounding algorithms for a geometric embedding of minimum multiway cut
• Title not available (Why is that?)
• On the multiway cut polyhedron
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Approximating the k-multicut problem
• The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
• An improved approximation algorithm of MULTIWAY CUT.
• Multiway cut and integer flow problems in trees
• Dial a Ride from k-Forest
• Algorithm Theory - SWAT 2004
• Approximating Generalized Multicut on Trees
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Approximation and Online Algorithms
• On the complexity of the multicut problem in bounded tree-width graphs and digraphs

Cited In (12)

• \(k\)-cuts: a variation of Gomory mixed integer cuts from the LP tableau
• Approximating Generalized Multicut on Trees
• An approximation algorithm for the \(B\)-prize-collecting multicut problem in trees
• A new approximation algorithm for the selective single-sink buy-at-bulk problem in network design
• Generalized \(k\)-multiway cut problems
• A generalized \(\alpha\)-cut
• An approximation algorithm for the \(\boldsymbol{K}\)-prize-collecting multicut problem in trees with submodular penalties
• Combinatorial approximation algorithms for the submodular multicut problem in trees with submodular penalties
• Approximation and Online Algorithms
• An \(O^\ast(1.84^k)\) parameterized algorithm for the multiterminal cut problem
• Partial multicuts in trees
• On the generalized multiway cut in trees problem

This page was built for publication: An approximation algorithm for the generalized \(k\)-multicut problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q423940)