A Multivariate Complexity Analysis of Lobbying in Multiple Referenda
Authors: R. Bredereck, J. Chen, S. Hartung, S. Kratsch, R. Niedermeier, O. Suchy, G. J. Woeginger
JAIR 2014 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We contribute to the theoretical as well as to the empirical side. See the preliminaries in Section 2 for definitions of parameterized complexity classes and the like. Our complexity results are summarized in Table 1... Finally, in Section 6, we experimentally compare our greedy heuristic, with the heuristic in the work of Erd elyi et al. (2007), and an implementation of our ILP formulation providing solutions guaranteed to be optimal. Our empirical results with random data and real-world data indicate that Lobbying can be solved efficiently. |
| Researcher Affiliation | Academia | Robert Bredereck EMAIL Jiehua Chen EMAIL Sepp Hartung EMAIL Stefan Kratsch EMAIL Rolf Niedermeier EMAIL TU Berlin, Germany Ondˇrej Such y EMAIL Czech Technical University in Prague, Czech Republic Gerhard J. Woeginger EMAIL TU Eindhoven, The Netherlands |
| Pseudocode | Yes | Algorithm 1 Max Gap Zeros (A {0, 1}n m) compute the gap values of all columns while a column with positive gap value exists do compute the gain vector of each row vector modify an arbitrary row vector with highest gain update the gap values for all columns return modified rows |
| Open Source Code | Yes | The source code including the data generator is freely available.5 5. http://akt.tu-berlin.de/menue/software/ |
| Open Datasets | Yes | To obtain a data set representing realistic binary preferences of politicians we use the welldocumented voting records of the German parliament, the Bundestag . Votes on issues in the Bundestag can be anonymous or recorded votes...We generated our instances from the recorded votes in 2012 and 2013 which are freely available from www.bundestag.de |
| Dataset Splits | No | The paper describes random instance generation models with parameters for density, and how real-world data from the German parliament was processed and grouped for experiments. It mentions 'test series' with 'randomly selected issues' of 'small gap values' or 'high gap values', but it does not specify explicit train/test/validation splits needed to reproduce machine learning or predictive experiments. It describes how experimental *instances* were created or selected for different tests, but not how these instances were partitioned into training, validation, or test sets. |
| Hardware Specification | Yes | All our experiments were performed on an Intel Xeon E5-1620 3.6GHz machine with 64GB of memory running the Debian GNU/Linux 6.0 operating system. |
| Software Dependencies | Yes | We used Gurobi 5.0.1 as our (integer) linear program solver to handle the ILP formulation of Lobbying given in the proof of Theorem 9...Both greedy heuristics are implemented in C++. The ILP implementation uses Gurobi4 5.0.1 through its Java API. |
| Experiment Setup | Yes | Our row-oriented model randomly chooses a density for each row and then sets each row entry at random such that it equals 1 with a probability equal to the chosen density value. In a similar way, our column-oriented approach randomly chooses a density for each column and then generates the entries in this column at random using this density value as the probability for generating a 1. Section 6.1 contains a more detailed description of our random models. In Section 6.3 we present our experimental findings...For each number m of columns from {5, 10, . . . , 30} we extracted 100 instances for each of the first two experiments. For each m from {5, 10, . . . , 60} we generated 100 instances for the last experiment. |