Improved approximation algorithms for the maximum happy vertices and edges problems

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

zbMATH Keywords

approximation algorithm; randomized rounding; maximum happy edges; maximum happy vertices; network homophyly

Mathematics Subject Classification ID

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