Contiguous Cake Cutting: Hardness Results and Approximation Algorithms
Authors: Paul W. Goldberg, Alexandros Hollender, Warut Suksompong1990-1997
AAAI 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the fair allocation of a cake... While it is known that no finite envy-free algorithm exists in this setting, we exhibit efficient algorithms that produce allocations with low envy among the agents. We then establish NP-hardness results for various decision problems... In addition, we consider a discretized setting... and show a number of hardness results strengthening those from prior work. |
| Researcher Affiliation | Academia | Paul W. Goldberg, Alexandros Hollender, Warut Suksompong Department of Computer Science University of Oxford |
| Pseudocode | Yes | Algorithm 1 1/3-Envy-Free Algorithm for Arbitrary Valuations; Algorithm 2 1/4-Envy-Free Algorithm for Uniform Single-Interval Valuations |
| Open Source Code | No | The paper does not provide any explicit statements or links about open-sourcing the code for the described methodology. |
| Open Datasets | No | This is a theoretical paper focused on algorithm design and hardness proofs; it does not involve empirical training on datasets. Therefore, there is no information about public datasets for training. |
| Dataset Splits | No | This is a theoretical paper presenting algorithms and hardness proofs, not empirical experiments. Therefore, there is no information about dataset splits for training, validation, or testing. |
| Hardware Specification | No | This is a theoretical paper presenting algorithms and hardness proofs, not empirical experiments. Therefore, there is no mention of hardware specifications. |
| Software Dependencies | No | This is a theoretical paper presenting algorithms and hardness proofs, not empirical experiments. Therefore, there are no software dependencies for reproducibility in the context of running experiments. |
| Experiment Setup | No | This is a theoretical paper presenting algorithms and hardness proofs, not empirical experiments. Therefore, there is no experimental setup, hyperparameters, or training configurations to detail. |