Satisfying Neighbor Preferences on a Circle

摘要

We study the problem of satisfying seating preferences on a circle. We assume we are given a collection of n agents to be arranged on a circle. Each agent is colored either blue or red, and there are exactly b blue agents and r red agents. The ω-neighborhood of an agent A is the sequence of 2w + 1 agents at distance