Facility Location Problem with Capacity Constraints: Algorithmic and Mechanism Design Perspectives
Authors: Haris Aziz, Hau Chan, Barton Lee, Bo Li, Toby Walsh1806-1813
AAAI 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | From the algorithmic perspective, we prove that the corresponding optimization problem, where the goal is to locate facilities to minimize either the total cost to all agents or the maximum cost of any agent is NP-hard. However, we show that the problem is fixed-parameter tractable, and the optimal solution can be computed in polynomial time whenever the number of facilities is bounded, or when all facilities have identical capacities. We then consider the problem from a mechanism design perspective where the agents are strategic and need not reveal their true locations. We show that several natural mechanisms studied in the uncapacitated setting either lose strategyproofness or a bound on the solution quality for the total or maximum cost objective. We then propose new mechanisms that are strategyproof and achieve approximation guarantees that almost match the lower bounds.Our main contributions are as follows. Firstly, for FLP-CC, we provide algorithmic results identifying the complexity of the corresponding optimization problem (NP-hard) but also provide tractability results, via dynamic programs (DPs), for various restricted settings. Secondly, we explore the mechanism design challenges introduced by this new setting. |
| Researcher Affiliation | Collaboration | Haris Aziz,1 Hau Chan,2 Barton E. Lee,1 Bo Li,3 Toby Walsh4 1UNSW Sydney and Data61 CSIRO 2Department of Computer Science and Engineering, University of Nebraska-Lincoln 3Department of Computer Science, University of Oxford 4TU Berlin, UNSW Sydney and Data61 CSIRO |
| Pseudocode | Yes | Algorithm 1 OPT T (j, j , k, S) and Algorithm 2 OPT M(i, i , j, S ) |
| Open Source Code | No | The paper does not provide an explicit statement or link for open-source code for the methodology described. |
| Open Datasets | No | The paper focuses on theoretical analysis and does not involve training models on datasets. |
| Dataset Splits | No | The paper is theoretical and does not describe any dataset splits for validation. |
| Hardware Specification | No | The paper is theoretical and does not describe the hardware specifications used for experiments. |
| Software Dependencies | No | The paper focuses on theoretical contributions and does not mention specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not provide details on experimental setup, hyperparameters, or system-level training settings. |