Voronoi game on graphs

DOI10.1016/j.tcs.2014.10.003zbMath1303.90057OpenAlexW2108472197MaRDI QIDQ476871

Sayan Bandyapadhyay, Aritra Banik, Hirak Sarkar, Sandip Das

Publication date: 2 December 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.10.003

zbMATH Keywords

approximation algorithmsNP-hardnesscompetitive facility locationlocation gamesVoronoi game on graphs

Mathematics Subject Classification ID

Games involving graphs (91A43) Discrete location and assignment (90B80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items

The discrete Voronoi game in \(\mathbb{R}^2\) ⋮ Rectilinear Voronoi games with a simple rectilinear obstacle in plane ⋮ Improved bounds for discrete Voronoi games ⋮ Balancing graph Voronoi diagrams with one more vertex ⋮ Competitive location problems: balanced facility location and the one-round Manhattan Voronoi game ⋮ The inverse Voronoi problem in graphs. I: Hardness ⋮ Competitive location problems: balanced facility location and the one-round Manhattan Voronoi game ⋮ The 1-dimensional discrete Voronoi game ⋮ Spatial competition on 2-dimensional markets and networks when consumers don't always go to the closest firm ⋮ \(\varepsilon\)-Constraint method for bi-objective competitive facility location problem with uncertain demand scenario

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The one-round Voronoi game replayed
• Existence theory for spatially competitive network facility location models
• Competitive spatial models
• On locating new facilities in a competitive environment
• The one-round Voronoi game
• A competitive facility location problem on a tree network with stochastic weights.
• Competitive facility location: the Voronoi game
• The Theory of Search: Optimum Distribution of Search Effort
• A General Algorithm for the Optimal Distribution of Effort
• The Voronoi game on graphs and its complexity
• Nash Equilibria in Voronoi Games on Graphs
• Voronoi Games on Cycle Graphs
• The Maximum Coverage Location Problem
• Market and Locational Equilibrium for Two Competitors
• Existence of equilibrium configurations of competitive firms on an infinite two-dimensional space
• Voronoi Game on Graphs
• Competitive Location Models: A Framework and Bibliography
• The Optimum Distribution of Effort