Approximation and Hardness Results for the Max k-Uncut Problem (Q2958303): Difference between revisions

@@ Property / author @@
-Chen-Chen Wu
@@ Property / author: Chen-Chen Wu / rank @@
-Normal rank
@@ Property / author @@
-Da-Chuan Xu
@@ Property / author: Da-Chuan Xu / rank @@
-Normal rank
@@ Property / author @@
+Chen-Chen Wu
@@ Property / author: Chen-Chen Wu / rank @@
+Normal rank
@@ Property / author @@
+Da-Chuan Xu
@@ Property / author: Da-Chuan Xu / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1007/978-3-319-48749-6_4
+Normal rank
@@ Property / OpenAlex ID @@
+W2541328924
@@ Property / OpenAlex ID: W2541328924 / rank @@
+Normal rank
@@ Property / cites work @@
+O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
+Normal rank
@@ Property / cites work @@
+Free Bits, PCPs, and Nonapproximability---Towards Tight Results
+Normal rank
@@ Property / cites work @@
+Detecting high log-densities
@@ Property / cites work: Detecting high log-densities / rank @@
+Normal rank
@@ Property / cites work @@
+Simplex partitioning via exponential clocks and the multiway cut problem
+Normal rank
@@ Property / cites work @@
+An improved approximation algorithm of MULTIWAY CUT.
+Normal rank
@@ Property / cites work @@
+An approximation algorithm for max<i>k</i>-uncut with capacity constraints
+Normal rank
@@ Property / cites work @@
+Q4931752
@@ Property / cites work: Q4931752 / rank @@
+Normal rank
@@ Property / cites work @@
+The dense \(k\)-subgraph problem
@@ Property / cites work: The dense \(k\)-subgraph problem / rank @@
+Normal rank
@@ Property / cites work @@
+Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
+Normal rank
@@ Property / cites work @@
+Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
+Normal rank
@@ Property / cites work @@
+A Polynomial Algorithm for the k-cut Problem for Fixed k
+Normal rank
@@ Property / cites work @@
+Clique is hard to approximate within \(n^{1-\epsilon}\)
+Normal rank
@@ Property / cites work @@
+Approximation Algorithms for Graph Homomorphism Problems
+Normal rank
@@ Property / cites work @@
+Graph expansion and the unique games conjecture
@@ Property / cites work: Graph expansion and the unique games conjecture / rank @@
+Normal rank
@@ Property / cites work @@
+Finding <i>k</i> Cuts within Twice the Optimal
@@ Property / cites work: Finding <i>k</i> Cuts within Twice the Optimal / rank @@
+Normal rank
@@ Property / cites work @@
+A Complex Semidefinite Programming Rounding Approximation Algorithm for the Balanced Max-3-Uncut Problem
+Normal rank
@@ Property / cites work @@
+Approximation of dense-\(n/2\)-subgraph and the complement of min-bisection
+Normal rank
@@ Property / cites work @@
+Improved Approximation Algorithms for the Maximum Happy Vertices and Edges Problems
+Normal rank
@@ Property / cites work @@
+Algorithmic aspects of homophyly of networks
@@ Property / cites work: Algorithmic aspects of homophyly of networks / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:2958303