When Rigging a Tournament, Let Greediness Blind You
Authors: Sushmita Gupta, Sanjukta Roy, Saket Saurabh, Meirav Zehavi
IJCAI 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We present a fresh, purely combinatorial greedy solution. We rely on new insights into TFP itself, which also results in the better running time bound of 2O(k log k)n O(1). While our analysis is intricate, the algorithm itself is surprisingly simple. ... First, our algorithm is purely combinatorial (unlike the algebraic algorithm of [Ramanujan and Szeider, 2017]). ... Third, our algorithm is substantially faster than that of [Ramanujan and Szeider, 2017]. Specifically, our running time bound is 2O(k log k)n O(1) rather than 2O(k 2 log k)n O(1). |
| Researcher Affiliation | Academia | Sushmita Gupta1, Sanjukta Roy2, Saket Saurabh1.2 and Meirav Zehavi3 1 University of Bergen, Bergen, Norway 2 The Institute of Mathematical Sciences, HBNI, Chennai, India 3 Ben-Gurion University, Beersheba, Israel sushmita.gupta@gmail.com, sanjukta@imsc.res.in, saket@imsc.res.in, meiravze@bgu.ac.il |
| Pseudocode | Yes | Path Greedy: 1. Let v be the highest unresolved fas-vertex in T and w be its fas-parent. ... Subtree Greedy: 1. Let v be the highest unresolved fas-vertex. ... Subtree Completion: 1. Initialize φi to be φi 1, and U to be Wvi. |
| Open Source Code | No | The paper does not provide any links to open-source code or explicitly state that the code for their methodology is publicly available. |
| Open Datasets | No | This is a theoretical paper presenting an algorithm and its complexity analysis. It does not involve experimental data, training datasets, or any form of empirical evaluation. |
| Dataset Splits | No | This is a theoretical paper presenting an algorithm and its complexity analysis. It does not involve experimental data, validation sets, or any form of empirical evaluation. |
| Hardware Specification | No | This is a theoretical paper focusing on algorithm design and complexity. It does not mention any hardware specifications for running experiments as no empirical experiments are conducted or reported. |
| Software Dependencies | No | This is a theoretical paper focused on algorithm design and complexity analysis. It does not mention any specific software dependencies with version numbers for reproducing experiments, as no empirical experiments are reported. |
| Experiment Setup | No | This is a theoretical paper focused on algorithm design and complexity analysis. It does not include an experimental setup section or details on hyperparameters or training configurations, as no empirical experiments are reported. |