Facility Reallocation on the Line
Authors: Bart de Keijzer, Dominik Wojtczak
IJCAI 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We consider a multi-stage facility reallocation problems on the real line, where a facility is being moved between stages based on the locations reported by n agents. The aim of the reallocation mechanism is to minimize the social cost, i.e., the sum over the total distance between the facility and all agents at all stages, plus the cost incurred for moving the facility. We study this problem both in the offline setting and online setting. In the offline case the mechanism has full knowledge of the agent locations in all future stages, and in the online setting the mechanism does not know these future locations and must decide the location of the facility on a stage-per-stage basis. We derive the optimal mechanism in both cases. For the online setting we show that its competitive ratio is (n + 2)/(n + 1). As neither of these mechanisms turns out to be strategyproof, we propose another strategyproof mechanism which has a competitive ratio of (n + 3)/(n + 1) for odd n and (n + 4)/n for even n, which we conjecture to be the best possible. We also consider a generalization with multiple facilities and weighted agents, for which we show that the optimum can be computed in polynomial time for a fixed number of facilities. |
| Researcher Affiliation | Academia | Bart de Keijzer, Dominik Wojtczak, University of Liverpool B.De-Keijzer@liverpool.ac.uk, D.Wojtczak@liverpool.ac.uk |
| Pseudocode | No | The paper describes algorithms and mechanisms in prose and through mathematical derivations (e.g., "An optimal facility reallocation mechanism for k = 1 always places the facility at Stage t [T] in the median interval M t(yt 1)"), but it does not include any structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any statements about releasing source code or links to a code repository. |
| Open Datasets | No | The paper is theoretical and does not use or refer to any publicly available datasets for training or evaluation. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not describe any hardware used for computations or experiments. |
| Software Dependencies | No | The paper is theoretical and does not mention any specific software dependencies or versions. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithm design and proofs, rather than empirical experiments. Therefore, no experimental setup details like hyperparameters or training configurations are provided. |