Algorithms for Max-Min Share Fair Allocation of Indivisible Chores
Authors: Haris Aziz, Gerhard Rauchecker, Guido Schryen, Toby Walsh
AAAI 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In this section, we report the results of our computational study where we tested the performance of our SCHED heuristic (Algorithm 3). We show that SCHED returns near-optimal solutions and greatly outperforms the simpler greedy round-robin protocol (Algorithm 1). |
| Researcher Affiliation | Academia | Haris Aziz Data61 and UNSW Sydney, NSW 2052, Australia haris.aziz@data61.csiro.au; Gerhard Rauchecker University of Regensburg 93053 Regensburg, Germany gerhard.rauchecker@ur.de; Guido Schryen University of Regensburg 93053 Regensburg, Germany guido.schryen@ur.de; Toby Walsh UNSW, Data61 and TU Berlin Sydney, NSW 2052, Australia toby.walsh@data61.csiro.au |
| Pseudocode | Yes | Algorithm 1 Greedy round-robin protocol; Algorithm 2 PTAS for optimal Mm S; Algorithm 3 SCHED heuristic for optimal Mm S |
| Open Source Code | No | The paper does not provide any statement or link indicating that the source code for the described methodology is publicly available. |
| Open Datasets | No | Utilities were drawn from a uniform distribution ui(j) U(0, 100) (and negated for obtaining chores instances) as it is common in the literature for fair division of goods (Amanatidis et al. 2015; Bouveret and Lemaˆıtre 2016; Kurokawa, Procaccia, and Wang 2016). This describes data generation, not the use of a publicly accessible dataset with concrete access info. |
| Dataset Splits | No | The paper does not explicitly provide information about training, validation, or test dataset splits. It describes generating instances for computational experiments but not how they are partitioned for model evaluation. |
| Hardware Specification | Yes | We coded all algorithms in C++ on a Linux Cent OS 7 based 12-core processor with a clock speed of 3.07 GHz and 24 Gi B memory. |
| Software Dependencies | Yes | Integer linear programs were solved via the Gurobi 6 C++ API. |
| Experiment Setup | Yes | The time limit in step 4 of SCHED was set to Tmax = 300s. |