I'm trying to solve a variant of Voronoi Game.

Given a Graph $G=(V, E)$, with uniform distance $d(E)=1$, a subset of the vertices $\hat{V} \subseteq V$ are vertices of interests. $k$ players take turns to place their facilities $V^*_i$ on graph $G$. We define a subgraph $G_i = \{ V_i, E : \forall V_i, d(V_i, V^*_i) \leq d(V_i, V^*_j) \}$, that is in plain words, every vertex in the subgraph is closer to the player $i$'s facility than other facilities.

Each player will take turns to place their facilities. Each player will place at most 1 facility. The goal for player $i$ is to maximize the verticies of interest in his subgraph, or $|\hat{V}| \in G_i$.

My research points me to several papers, such as Nash equilibria in Voronoi games on graphs, but most of them simply states that the problem is NP-hard. Also, I am not even sure if I need Nash equilibrium, since I am just trying to find the optimal placement for each player.

As this is a practical problem, and the space is small, think $k=5$, $|V|=25$, I'm wondering if there are any greedy, approximation, randomized algorithms that are efficient for this task?

I would also appreciate any hints, or places to further my search.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.