Strategy Proof Mechanisms for Facility Location at Limited Locations
Facility location problems often permit facilities to be located at any position. But what if this is not the case in practice? What if facilities can only be located at particular locations like a highway exit or close to a bus stop? We consider here the impact of such constraints on the location of facilities on the performance of strategy proof mechanisms for locating facilities.We study four different performance objectives: the total distance agents must travel to their closest facility, the maximum distance any agent must travel to their closest facility, and the utilitarian and egalitarian welfare.We show that constraining facilities to a limited set of locations makes all four objectives harder to approximate in general.
Code (0)
등록된 구현이 없습니다.
Tasks
PositionMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Strategy Proof Mechanisms for Facility Location with Capacity Limits
An important feature of many real world facility location problems are capacity limits on the facilities. We show here how capacity constraints make it harder to design strategy proof mechanisms for facility location, bu…
Mechanism Design With Predictions for Obnoxious Facility Location
We study mechanism design with predictions for the obnoxious facility location problem. We present deterministic strategyproof mechanisms that display tradeoffs between robustness and consistency on segments, squares, ci…
Proportional Fairness in Obnoxious Facility Location
We consider the obnoxious facility location problem (in which agents prefer the facility location to be far from them) and propose a hierarchy of distance-based proportional fairness concepts for the problem. These fairn…
FairnessStrategy Proof Mechanisms for Facility Location in Euclidean and Manhattan Space
We study the impact on mechanisms for facility location of moving from one dimension to two (or more) dimensions and Euclidean or Manhattan distances. We consider three fundamental axiomatic properties: anonymity which i…
FairnessFacility Location Problem with Capacity Constraints: Algorithmic and Mechanism Design Perspectives
We consider the facility location problem in the one-dimensional setting where each facility can serve a limited number of agents from the algorithmic and mechanism design perspectives. From the algorithmic perspective, …