Improved approximation algorithms for the maximum happy vertices and edges problems

DOI10.1007/s00453-017-0302-8zbMath1387.68301OpenAlexW1164874588MaRDI 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 algorithmrandomized roundingmaximum happy edgesmaximum happy verticesnetwork homophyly

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items

A simple and effective algorithm for the maximum happy vertices problem, Approximation and hardness results for the max \(k\)-uncut problem, Complexity and approximability of the happy set problem, New algorithms for a simple measure of network partitioning, Parameterized algorithms for the happy set problem, Graph classes and approximability of the happy set problem, Tackling the maximum happy vertices problem in large networks, New algorithms for a simple measure of network partitioning, 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, Approximation algorithms for vertex happiness

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