Approximation and hardness results for the max \(k\)-uncut problem
type: Item
instance of: scholarly article
title: Approximation and hardness results for the max \(k\)-uncut problem
zbMATH Open document ID: 1407.68555
author: Peng Zhang
author: Chenchen Wu
author: Dachuan Xu
published in: Theoretical Computer Science
publication date: 2018-12-05T00:00:00Z
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 05C82
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68W20
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 6989361
zbMATH Keywords: max \(k\)-uncut
zbMATH Keywords: densest \(k\)-subgraph
zbMATH Keywords: homophily
zbMATH Keywords: approximation algorithm
zbMATH Keywords: computational complexity
MaRDI profile type: Publication
full work available at URL: j.tcs.2017.09.003
OpenAlex ID: W2754777885
cites work: O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
cites work: Linear Time Algorithms for Happy Vertex Coloring Problems for Trees
cites work: Free Bits, PCPs, and Nonapproximability---Towards Tight Results
cites work: Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
cites work: Simplex partitioning via exponential clocks and the multiway cut problem
cites work: An improved approximation algorithm of MULTIWAY CUT.
cites work: An approximation algorithm for maxk-uncut with capacity constraints
cites work: Q4931752
cites work: The dense \(k\)-subgraph problem
cites work: Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
cites work: Q4198056
cites work: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
cites work: A Polynomial Algorithm for the k-cut Problem for Fixed k
cites work: Clique is hard to approximate within \(n^{1-\epsilon}\)
cites work: Approximation Algorithms for Graph Homomorphism Problems
cites work: Graph expansion and the unique games conjecture
cites work: Finding k Cuts within Twice the Optimal
cites work: Q4258215
cites work: Q5311854
cites work: A Complex Semidefinite Programming Rounding Approximation Algorithm for the Balanced Max-3-Uncut Problem
cites work: Approximation of dense-\(n/2\)-subgraph and the complement of min-bisection
cites work: Algorithmic aspects of homophyly of networks
cites work: Approximation and Hardness Results for the Max k-Uncut Problem
cites work: Improved approximation algorithms for the maximum happy vertices and edges problems
DOI: 10.1016/J.TCS.2017.09.003
description: scientific article; zbMATH DE number 6989361