Improved approximation algorithms for the maximum happy vertices and edges problems

DOI10.1007/S00453-017-0302-8MaRDI QIDQ1750352zbMATH OpenOpenAlexFDO

Authors Peng Zhang, Yao Xu, Tao Jiang, Eiji Miyano, Angsheng Li, Guohui Lin

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)

Recommendations

• Improved approximation algorithms for the maximum happy vertices and edges problems
• Approximation algorithms for vertex happiness
• Algorithmic aspects of homophyly of networks

Cites work

• scientific article; zbMATH DE number 3860199 (Why is no real title available?)
• scientific article; zbMATH DE number 1330032 (Why is no real title available?)
• Algorithmic aspects of homophyly of networks
• An improved approximation algorithm of MULTIWAY CUT.
• Approximation Algorithms for Graph Homomorphism Problems
• Approximation algorithms for classification problems with pairwise relationships, metric labeling and Markov random fields
• Improved approximation algorithms for the maximum happy vertices and edges problems
• Linear Programming in O([n3/ln n]L) Operations
• Multiway cut, pairwise realizable distributions, and descending thresholds
• Networks, crowds and markets. Reasoning about a highly connected world.
• Simplex partitioning via exponential clocks and the multiway cut problem
• The Complexity of Multiterminal Cuts
• The design of approximation algorithms

Cited in

(16)

• A simple and effective algorithm for the maximum happy vertices problem
• Approximation and hardness results for the max \(k\)-uncut problem
• Tackling the maximum happy vertices problem in large networks
• The maximum happy induced subgraph problem: bounds and algorithms
• Parameterized algorithms for the happy set problem
• Complexity and approximability of the happy set problem
• Kernelization for maximum happy vertices problem
• New algorithms for a simple measure of network partitioning
• Graph classes and approximability of the happy set problem
• Algorithmic aspects of homophyly of networks
• Maximizing happiness in graphs of bounded clique-width
• 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
• Approximation algorithms for vertex happiness
• Improved approximation algorithms for the maximum happy vertices and edges problems

This page was built for publication: Improved approximation algorithms for the maximum happy vertices and edges problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1750352)