Approximation and hardness results for label cut and related problems

DOI10.1007/s10878-009-9222-0zbMath1211.90201OpenAlexW2016115187MaRDI QIDQ630189

Lin-Qing Tang, Wen-Bo Zhao, Jin-Yi Cai, Peng Zhang

Publication date: 17 March 2011

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.113.6742

zbMATH Keywords

combinatorial optimizationapproximation algorithmsapproximation hardnesslabel cut

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (13)

Sequence Hypergraphs ⋮ Secluded connectivity problems ⋮ On the hardness of labeled correlation clustering problem: a parameterized complexity view ⋮ Sequence Hypergraphs: Paths, Flows, and Cuts ⋮ Simpler and better approximation algorithms for the unweighted minimum label \(s\)-\(t\) cut problem ⋮ Minimum label \(s\)-\(t\) cut has large integrality gaps ⋮ Hypergraph \(k\)-cut in randomized polynomial time ⋮ Graph cuts with interacting edge weights: examples, approximations, and algorithms ⋮ Algorithms and complexity results for labeled correlation clustering problem ⋮ Algorithms and complexity for a class of combinatorial optimization problems with labelling ⋮ Maximum cuts in edge-colored graphs ⋮ Refined parameterizations for computing colored cuts in edge-colored graphs ⋮ Approximate tradeoffs on weighted labeled matroids

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• PCP characterizations of NP: toward a polynomially-small error-probability
• Primal-dual approximation algorithms for integral flow and multicut in trees
• On the hardness of approximating label-cover
• The labeled perfect matching in bipartite graphs
• The hardness of approximate optima in lattices, codes, and systems of linear equations
• The minimum labeling spanning trees
• On the minimum label spanning tree problem
• The budgeted maximum coverage problem
• Local search for the minimum label spanning tree problem with bounded color classes.
• Worst-case behavior of the MVCA heuristic for the minimum labeling spanning tree problem
• Least and most colored bases
• Approximation algorithms and hardness results for labeled connectivity problems
• On the hardness of approximating Multicut and Sparsest-Cut
• Rounding algorithms for a geometric embedding of minimum multiway cut
• Improved approximation for directed cut problems
• On Labeled Traveling Salesman Problems
• Spanning trees with many or few colors in edge-colored graphs
• On the hardness of approximating minimization problems
• Finding k Cuts within Twice the Optimal
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• Formal Methods for Components and Objects

This page was built for publication: Approximation and hardness results for label cut and related problems