An approximation algorithm for the generalized k-multicut problem

DOI10.1016/J.DAM.2012.01.016MaRDI QIDQ423940zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(13)

• \(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
• Partial multicuts in trees
• An O^(1.84ᵏ) parameterized algorithm for the multiterminal cut problem
• An approximation algorithm for the \(k\)-prize-collecting multicut on a tree problem
• 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)