Approximation and Hardness Results for the Max k-Uncut Problem
From MaRDI portal
Publication:2958303
DOI10.1007/978-3-319-48749-6_4zbMath1407.68556OpenAlexW2541328924MaRDI QIDQ2958303
Peng Zhang, Xinghe Zhang, Chen-Chen Wu, Da-Chuan Xu
Publication date: 1 February 2017
Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-48749-6_4
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
Cites Work
- Unnamed Item
- 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}\)
- Approximation of dense-\(n/2\)-subgraph and the complement of min-bisection
- 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
- Improved Approximation Algorithms for the Maximum Happy Vertices and Edges Problems
- 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
