Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
EFX Feasible Scheduling for Time-dependent Resources
Authors: Jiazhu Fang, Qizhi Fang, Minming Li, Wenjing Liu
IJCAI 2025 | Venue PDF | 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. |