Approximation and hardness results for label cut and related problems
type: Item
instance of: scholarly article
title: Approximation and hardness results for label cut and related problems
zbMATH Open document ID: 1211.90201
author: Peng Zhang
author: Jin-Yi Cai
author: Lin-Qing Tang
author: Wen-Bo Zhao
published in: Journal of Combinatorial Optimization
publication date: 2011-03-17T00:00:00Z
full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 5866920
zbMATH Keywords: label cut
zbMATH Keywords: approximation algorithms
zbMATH Keywords: approximation hardness
zbMATH Keywords: combinatorial optimization
MaRDI profile type: Publication
OpenAlex ID: W2016115187
cites work: Improved approximation for directed cut problems
cites work: The hardness of approximate optima in lattices, codes, and systems of linear equations
cites work: Spanning trees with many or few colors in edge-colored graphs
cites work: Q4659605
cites work: Local search for the minimum label spanning tree problem with bounded color classes.
cites work: Q4952637
cites work: The minimum labeling spanning trees
cites work: On the hardness of approximating Multicut and Sparsest-Cut
cites work: Q3549612
cites work: On Labeled Traveling Salesman Problems
cites work: On the hardness of approximating label-cover
cites work: PCP characterizations of NP: toward a polynomially-small error-probability
cites work: Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
cites work: Primal-dual approximation algorithms for integral flow and multicut in trees
cites work: Approximation algorithms and hardness results for labeled connectivity problems
cites work: Rounding algorithms for a geometric embedding of minimum multiway cut
cites work: The budgeted maximum coverage problem
cites work: On the minimum label spanning tree problem
cites work: On the hardness of approximating minimization problems
cites work: Least and most colored bases
cites work: The labeled perfect matching in bipartite graphs
cites work: Finding k Cuts within Twice the Optimal
cites work: Formal Methods for Components and Objects
cites work: Worst-case behavior of the MVCA heuristic for the minimum labeling spanning tree problem
DOI: 10.1007/S10878-009-9222-0
description: scientific article; zbMATH DE number 5866920