|
| | | | |
| | | |
| Stat |
Members: 3667
Articles: 2'599'751
Articles rated: 2609
07 February 2025 |
|
| | | | |
|
Article overview
| |
|
|
Settling the Distortion of Distributed Facility Location | | Aris Filos-Ratsikas
; Panagiotis Kanellopoulos
; Alexandros A. Voudouris
; Rongsen Zhang
; | | Date: |
4 Jan 2023 | | Abstract: | We study the distributed facility location problem, where a set of agents
with positions on the line of real numbers are partitioned into disjoint
districts, and the goal is to choose a point to satisfy certain criteria, such
as optimize an objective function or avoid strategic behavior. A mechanism in
our distributed setting works in two steps: For each district it chooses a
point that is representative of the positions reported by the agents in the
district, and then decides one of these representative points as the final
output. We consider two classes of mechanisms: Unrestricted mechanisms which
assume that the agents directly provide their true positions as input, and
strategyproof mechanisms which deal with strategic agents and aim to
incentivize them to truthfully report their positions. For both classes, we
show tight bounds on the best possible approximation in terms of several
minimization social objectives, including the well-known social cost (total
distance of agents from chosen point) and max cost (maximum distance among all
agents from chosen point), as well as other fairness-inspired objectives that
are tailor-made for the distributed setting. | | Source: | arXiv, 2301.01604 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
|
| |
|
|
|
REGISTER