A note on anti-coordination and social interactions

Details A note on anti-coordination and social interactions A note on anti-coordination and social interactions

2012-01-02

arxiv.org/abs/1201.0410v2

Computer Science

Computer Science and Game Theory

7 pages

Scientific paper

10.1007/s10878-012-9486-7

This note confirms a conjecture of [Bramoull\'{e}, Anti-coordination and social interactions, Games and Economic Behavior, 58, 2007: 30-49]. The problem, which we name the maximum independent cut problem, is a restricted version of the MAX-CUT problem, requiring one side of the cut to be an independent set. We show that the maximum independent cut problem does not admit any polynomial time algorithm with approximation ratio better than $n^{1-\epsilon}$, where $n$ is the number of nodes, and $\epsilon$ arbitrarily small, unless P=NP. For the rather special case where each node has a degree of at most four, the problem is still MAXSNP-hard.

Affiliated with

Also associated with

No associations

Rating

A note on anti-coordination and social interactions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A note on anti-coordination and social interactions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A note on anti-coordination and social interactions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-55223