Approximation algorithms for vertex happiness

DOI10.1007/S40305-019-00260-1zbMath1449.90308arXiv1606.03185OpenAlexW2963480423MaRDI QIDQ2326078

Peng Zhang, Randy Goebel, Yong Chen, Yao Xu

Publication date: 4 October 2019

Published in: Journal of the Operations Research Society of China (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1606.03185

zbMATH Keywords

approximation algorithmintegrality gappolynomial-time reductionsubmodular/supermodular set functionmulti-labelingvertex happiness

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A lower bound of \(8/(7+\frac{1}{k-1})\) on the integrality ratio of the Călinescu-Karloff-Rabani relaxation for multiway cut
• Algorithmic aspects of homophyly of networks
• Inapproximability results for combinatorial auctions with submodular utility functions
• Three short proofs in graph theory
• Improved approximation algorithms for the maximum happy vertices and edges problems
• Greedy splitting algorithms for approximating multiway partition problems
• Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems
• Combinatorial auctions with decreasing marginal utilities
• Rounding algorithms for a geometric embedding of minimum multiway cut
• Symmetry and Approximability of Submodular Maximization Problems
• Submodular Cost Allocation Problem and Applications
• Improved Approximation Algorithms for the Maximum Happy Vertices and Edges Problems
• An improved approximation algorithm for combinatorial auctions with submodular bidders
• Approximation Algorithms for Graph Homomorphism Problems
• The Complexity of Multiterminal Cuts
• Multiway cuts in node weighted graphs
• On Maximizing Welfare When Utility Functions Are Subadditive
• Multiway cut, pairwise realizable distributions, and descending thresholds
• Approximation Algorithms for Submodular Multiway Partition
• Simplex partitioning via exponential clocks and the multiway cut problem
• Local Distribution and the Symmetry Gap: Approximability of Multiway Partitioning Problems

This page was built for publication: Approximation algorithms for vertex happiness