Approximating max \(k\)-uncut via LP-rounding plus greed, with applications to densest \(k\)-subgraph
From MaRDI portal
Publication:5919045
DOI10.1016/j.tcs.2020.10.018zbMath1464.68302OpenAlexW3093638304MaRDI QIDQ5919045
Publication date: 15 December 2020
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2020.10.018
Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Approximation algorithms (68W25) Density (toughness, etc.) (05C42)
Related Items (2)
New algorithms for a simple measure of network partitioning ⋮ New algorithms for a simple measure of network partitioning
Cites Work
- Unnamed Item
- Unnamed Item
- Algorithmic aspects of homophyly of networks
- Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
- Approximation and hardness results for the max \(k\)-uncut problem
- Finding happiness: an analysis of the maximum happy vertices problem
- On the parameterized complexity of happy vertex coloring
- Improved approximation algorithms for the maximum happy vertices and edges problems
- Approximation of dense-\(n/2\)-subgraph and the complement of min-bisection
- An improved rounding method and semidefinite programming relaxation for graph partition
- Finding connected \(k\)-subgraphs with high density
- Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis
- Detecting high log-densities
- Graph expansion and the unique games conjecture
- Approximation algorithms for classification problems with pairwise relationships
- 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
- Greedily Finding a Dense Subgraph
- Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
- Approximating max \(k\)-uncut via LP-rounding plus greed, with applications to densest \(k\)-subgraph
- Lower bounds for the happy coloring problems
- The dense \(k\)-subgraph problem
This page was built for publication: Approximating max \(k\)-uncut via LP-rounding plus greed, with applications to densest \(k\)-subgraph
