Approximating max \(k\)-uncut via LP-rounding plus greed, with applications to densest \(k\)-subgraph
From MaRDI portal
Publication:5918330
DOI10.1007/978-3-030-57602-8_15zbMath1482.68188OpenAlexW3048196243MaRDI QIDQ5918330
Publication date: 5 July 2021
Published in: Algorithmic Aspects in Information and Management (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-030-57602-8_15
Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Approximation algorithms (68W25) Density (toughness, etc.) (05C42)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Algorithmic aspects of homophyly of networks
- 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
- 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
- The Byzantine Generals Problem
- A Polynomial Algorithm for the k-cut Problem for Fixed k
- Finding k Cuts within Twice the Optimal
- Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
- Lower bounds for the happy coloring problems
This page was built for publication: Approximating max \(k\)-uncut via LP-rounding plus greed, with applications to densest \(k\)-subgraph
