A note on anti-coordination and social interactions

DOI10.1007/s10878-012-9486-7zbMath1282.90148arXiv1201.0410OpenAlexW3124969533MaRDI QIDQ386417

Zhigang Cao, Xiao-guang Yang

Publication date: 9 December 2013

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

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

zbMATH Keywords

APX-hardanti-coordination gamefrustration functionmaximum independent cut problem

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items

The fashion game: network extension of matching pennies ⋮ Schedules for marketing products with negative externalities

Cites Work

• Unnamed Item
• Anti-coordination and social interactions
• On maximal independent sets of vertices in claw-free graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Optimization, approximation, and complexity classes
• Claw-free graphs---a survey
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Potential games
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Dynamics in Network Interaction Games
• On Syntactic versus Computational Views of Approximability
• Combinatorial optimization. Theory and algorithms.