EFX Feasible Scheduling for Time-dependent Resources
Authors: Jiazhu Fang, Qizhi Fang, Minming Li, Wenjing Liu
IJCAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We discuss the compatibility between envy-freeness up to any item (EFX) and various efficiency concepts. Additionally, we present polynomial-time algorithms for various settings. Our main contributions are summarized as follows. EFX + Max NSW + PO. We first consider binary valuation functions, where agents valuations for jobs are restricted to 1 or 0. We explore the characteristics of Max NSW schedules, focusing on fairness guarantees (approximate EFX) and efficiency guarantees (PO). Main Result 1: For any instance of FISP with binary valuations, there exists a Max NSW schedule that is 1/2-EFX and PO. Additionally, there exist instances where no Max NSW schedule can guarantee (1/2 + ε)-EFX for any ε > 0. |
| Researcher Affiliation | Academia | 1 School of Mathematical Sciences, Ocean University of China, Qingdao, Shandong, China. 2 Laboratory of Marine Mathematics, Ocean University of China, Qingdao, Shandong, China. 3 Department of Computer Science, City University of Hong Kong, Kowloon Tong, Hong Kong, China. EMAIL, EMAIL, EMAIL, EMAIL |
| Pseudocode | Yes | Algorithm 1 Greedy Algorithm Algorithm 2 Envy-Bundle Elimination Algorithm 3 Efficient Implementation |
| Open Source Code | No | No explicit statement or link for open-source code is provided in the paper. |
| Open Datasets | No | An instance I of the fair interval scheduling problem (FISP) is given by a tuple (J, A, u A), where J = {j1, . . . , jn} represents a set of n indivisible jobs and A = {a1, . . . , am} is a set of m agents (machines). There is no mention of specific public datasets or access information for any dataset. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical evaluation on datasets, thus no dataset splits are mentioned. |
| Hardware Specification | No | The paper describes theoretical algorithms and proofs, and does not report on experiments requiring specific hardware specifications. |
| Software Dependencies | No | The paper presents theoretical algorithms and does not specify software dependencies with version numbers for implementation. |
| Experiment Setup | No | The paper describes theoretical algorithms and proofs, and does not include details about an experimental setup, hyperparameters, or training configurations. |