Average-Case Approximation Ratio of Scheduling Without Payments
Authors: Jie Zhang
AAAI 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we take the average-case analysis approach, and tackle one of the primary motivating problems in Algorithmic Mechanism Design the scheduling problem (Nisan and Ronen 1999). We show, however, when the costs of the machines to executing the task follow any independent and identical distribution, the average-case approximation ratio of the mechanism given in (Koutsoupias 2014) is upper bounded by a constant. This positive result asymptotically separates the average-case ratio from the worst-case ratio, and indicates that the optimal mechanism for the problem actually works well on average, although in the worst-case the expected cost of the mechanism is Θ(n) times that of the optimal cost. |
| Researcher Affiliation | Academia | Jie Zhang Electronics and Computer Science University of Southampton, United Kingdom jie.zhang@soton.ac.uk |
| Pseudocode | No | The paper describes 'Mechanism M' in natural language and mathematical formulas, but does not include structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any concrete access information (e.g., repository links, explicit statements of code release) for open-source code related to the described methodology. |
| Open Datasets | No | The paper is theoretical and analyzes performance based on mathematical distributions (e.g., Pareto, Exponential, Log-logistic), not empirical datasets. Therefore, no concrete access information for a publicly available dataset is provided. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical data. Therefore, no specific dataset split information for training, validation, or testing is provided. |
| Hardware Specification | No | The paper is theoretical and does not report on computational experiments. Therefore, no specific hardware details are provided. |
| Software Dependencies | No | The paper is theoretical and does not discuss software implementations or dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe any computational experiments or their setup details, such as hyperparameters or configurations. |