Rainbow Cycle Number and EFX Allocations: (Almost) Closing the Gap
Authors: Shayan Chashm Jahan, Masoud Seddighin, Seyed-Mohammad Seyed-Javadi, Mohammad Sharifi
IJCAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In this paper, we introduce another problem in extremal combinatorics. For a parameter ℓ, we define the rainbow path degree and denote it by H(ℓ). We show that any lower bound on H(ℓ) yields an upper bound on R(d). Next, we prove that H(ℓ) Ω(ℓ2/ log ℓ) which yields an almost tight upper bound of R(d) Ω(d log d). This in turn proves the existence of (1 ϵ)-EFX allocation with Oϵ( n log n) number of discarded goods. In addition, for the special case of the Rainbow Cycle problem that the edges in each part form a permutation, we improve the upper bound to R(d) 2d 4. We leverage H(ℓ) to achieve this bound. Our conjecture is that the exact value of H(ℓ) is ℓ2 2 1. We provide some experiments that support this conjecture. |
| Researcher Affiliation | Academia | 1Sharif University of Technology, Iran 2Tehran Institute for Advanced Studies, Khatam University, Iran shayan.chashmjahan@gmail.com, m.seddighin@teias.insitute, mohammad.sj2@gmail.com, mohamadsharify36@gmail.com |
| Pseudocode | No | The paper does not contain any pseudocode or clearly labeled algorithm blocks. |
| Open Source Code | No | The paper does not provide any statement or link regarding the availability of open-source code. |
| Open Datasets | No | The paper describes theoretical work and computational experiments (exhaustive search for H(ℓ) values) rather than experiments involving datasets, and thus does not mention publicly available datasets or provide access information for them. |
| Dataset Splits | No | The paper describes theoretical work and computational experiments, not machine learning experiments, and therefore does not specify training/validation/test splits. |
| Hardware Specification | No | The paper mentions that "Our algorithm inputs ℓ, x and performs an exhaustive search", implying computation, but does not provide any specific details about the hardware used (e.g., CPU, GPU models, memory). |
| Software Dependencies | No | The paper does not specify any software dependencies with version numbers (e.g., programming languages, libraries, or solvers). |
| Experiment Setup | No | The paper describes the general approach of its experiments ("exhaustive search to find a counterexample"), but does not provide specific details on the experimental setup such as hyperparameters or system-level training settings. |