Approximation and hardness results for the max \(k\)-uncut problem

DOI10.1016/j.tcs.2017.09.003zbMath1407.68555OpenAlexW2754777885MaRDI QIDQ1630990

Peng Zhang, Da-Chuan Xu, Chen-Chen Wu

Publication date: 5 December 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2017.09.003

zbMATH Keywords

computational complexityapproximation algorithmhomophilydensest \(k\)-subgraphmax \(k\)-uncut

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (4)

New algorithms for a simple measure of network partitioning ⋮ New algorithms for a simple measure of network partitioning ⋮ Approximating max \(k\)-uncut via LP-rounding plus greed, with applications to densest \(k\)-subgraph ⋮ Approximating max \(k\)-uncut via LP-rounding plus greed, with applications to densest \(k\)-subgraph

Cites Work

• Algorithmic aspects of homophyly of networks
• Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
• An improved approximation algorithm of MULTIWAY CUT.
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Improved approximation algorithms for the maximum happy vertices and edges problems
• Approximation of dense-\(n/2\)-subgraph and the complement of min-bisection
• Linear Time Algorithms for Happy Vertex Coloring Problems for Trees
• Detecting high log-densities
• Graph expansion and the unique games conjecture
• A Complex Semidefinite Programming Rounding Approximation Algorithm for the Balanced Max-3-Uncut Problem
• Approximation and Hardness Results for the Max k-Uncut Problem
• An approximation algorithm for maxk-uncut with capacity constraints
• O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
• Approximation Algorithms for Graph Homomorphism Problems
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• Finding k Cuts within Twice the Optimal
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• Simplex partitioning via exponential clocks and the multiway cut problem
• The dense \(k\)-subgraph problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Approximation and hardness results for the max \(k\)-uncut problem