MAC Advice for facility location mechanism design
Authors: Zohar Barak, Anupam Gupta, Inbal Talgam-Cohen
NeurIPS 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We design both deterministic and randomized strategyproof anonymous mechanisms for facility location problems, with MAC predictions of the n agent locations. ... As our main technical result, for 2-facility location on a line we design a randomized mechanism that guarantees an expected approximation ratio of 3.6 + O(δ) (see Algorithm 4 and Theorem 9). ... For single-facility location in Rd, we design a mechanism that guarantees an approximation ratio of min{1 + 4δ 1 2δ, d} (see Algorithm 1 and Theorem 5). |
| Researcher Affiliation | Collaboration | Zohar Barak School of Computer Science Tel Aviv University zoharbarak@mail.tau.ac.il Anupam Gupta New York University and Google Research anupam.g@nyu.edu Inbal Talgam-Cohen School of Computer Science Tel Aviv University inbaltalgam@gmail.com |
| Pseudocode | Yes | Algorithm 1: Best-Choice-Single-Facility-Loc(X, X , δ)... Algorithm 2: SECOND-PROPORTIONAL-MECHANISM (X, h S)... Algorithm 3: BIG-CLUSTER-CENTER(X)... Algorithm 4: Robust-Half-Mechanism(X, X )... Algorithm 5: Bounded-Best-Choice-Single-Facility-Loc... Algorithm 6: MIN-BOUNDING-BOX... Algorithm 7: Balanced-k-Facility-Loc(X, X , b, δ) |
| Open Source Code | No | The paper states 'NA' for 'Open access to data and code' in the NeurIPS Paper Checklist. No explicit statement or link about code release is found in the paper text. |
| Open Datasets | No | The paper is theoretical and does not conduct empirical studies with datasets. Thus, there is no mention of dataset availability, or standard datasets and citations, for training or evaluation. |
| Dataset Splits | No | The paper is theoretical and does not conduct empirical studies with datasets. Thus, there is no mention of dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not describe any experimental hardware. The NeurIPS Paper Checklist confirms this by stating 'NA' for 'Experiments Compute Resources'. |
| Software Dependencies | No | The paper is theoretical and does not mention any specific software dependencies with version numbers for experimental reproducibility. The NeurIPS Paper Checklist confirms this by stating 'NA' for 'Experiments Compute Resources'. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithm design and proofs. It does not include an experimental setup section with hyperparameters or training details. The NeurIPS Paper Checklist confirms this by stating 'NA' for 'Experimental Setting/Details'. |