Improved approximation algorithms for the maximum happy vertices and edges problems
From MaRDI portal
Publication:1750352
DOI10.1007/s00453-017-0302-8zbMath1387.68301MaRDI QIDQ1750352
Yao Xu, Peng Zhang, Tao Jiang, Eiji Miyano, Guo-Hui Lin, Ang Sheng Li
Publication date: 18 May 2018
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-017-0302-8
approximation algorithm; randomized rounding; maximum happy edges; maximum happy vertices; network homophyly
90C35: Programming involving graphs or networks
90C59: Approximation methods and heuristics in mathematical programming
90C27: Combinatorial optimization
68W25: Approximation algorithms
Related Items
Parameterized algorithms for the happy set problem, 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, Lower bounds for the happy coloring problems, New algorithms for a simple measure of network partitioning, Approximation and hardness results for the max \(k\)-uncut problem, Graph classes and approximability of the happy set problem, Tackling the maximum happy vertices problem in large networks, A simple and effective algorithm for the maximum happy vertices problem, Approximation algorithms for vertex happiness, Complexity and approximability of the happy set problem, New algorithms for a simple measure of network partitioning
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Algorithmic aspects of homophyly of networks
- An improved approximation algorithm of MULTIWAY CUT.
- Rounding algorithms for a geometric embedding of minimum multiway cut
- The Design of Approximation Algorithms
- Improved Approximation Algorithms for the Maximum Happy Vertices and Edges Problems
- Approximation algorithms for classification problems with pairwise relationships
- Approximation Algorithms for Graph Homomorphism Problems
- The Complexity of Multiterminal Cuts
- Linear Programming in O([n3/ln nL) Operations]
- Multiway cut, pairwise realizable distributions, and descending thresholds
- Simplex partitioning via exponential clocks and the multiway cut problem