Algorithms for Divisor Methods of Apportionment

This repository contains implementations of algorithms for proportional apportionment with divisor methods. Inspect and use at your own risk.

• File SandwichSelect.java contains an implementation of the algorithm SandwichSelect we have presented in

  Wild, S. and Reitzig, R.
  A Practical and Worst-Case Efficient Algorithm for Divisor Methods of Apportionment
  submitted
  [preprint (v3,2016)]

  Some variants exist.

• In ChengEppsteinSelect.java we provide an implementation of the algorithm proposed in

  Cheng, Z. and Eppstein, D.
  Linear-time Algorithms for Proportional Apportionment
  In: International Symposium on Algorithms and Computation (ISAAC) 2014.
  Springer (2014)
  [preprint (v1,2014)]

• Furthermore, we implement the jump-and-step algorithm from

  Pukelsheim, F.
  Proportional Representation
  Springer, 2014

  in PukelsheimPQ.java with priority queues for determining the next party to modify, and in PukelsheimLS.java using linear scan.

• Finally, we give implementations of the naive iterative algorithms using priority queues resp. a linear scan for finding maxima in IterativeDMPQ.java and IterativeDMLS.java, respectively.

The core algorithms start in the respective implementations of method unitSize resp. apportion.

The remaining files provide interfaces, shared algorithmic parts and utility code. Some files are taken or adapted from Sedgewick/Wayne with our thanks; we re-release their files in agreement with their license statement (see Q + A here).

Compilation

Execute ant compile; you will need algs4.jar (in folder lib) from the book website of Sedgewick/Wayne.

Usage

Run ant test for testing correctness of the implementations. Besides rudimentary sanity checks, the test basically check Pukelsheim's Max-Min Inequality for all computed assignments, i.e. for all ways to resolve ties.

Command ant run executes a sample runtime experiment.

Run your own experiments by defining the parameters in a space-separated file (see e.g. arxiv2.experiment; those are the ones from the article) and passing it as parameter to run_experiments.rb. That is,

ruby run_experiments.rb arxiv.experiments 

runs the exact experiments used in our article.

In case you can not get this to work, here is a workaround.

1. Open a terminal resp. command line in th repository and execute ant compile.

2. Create the following folder structure within the code respository:

   my_experiment
   |- data
   |- plots
   |   |- times
   |   |- counters
   |   |- scatter
   |   |- averages
   |- tmp
   

3. Change directory to folder my_experiment.

4. For each non-comment line from arxiv.experiment (or your file), execute

   java -cp ../build de.unikl.csgak.appportionment.experiments.RunningTimeMain [line]
   

   If you use LDM(x,y) as divisor method, enclose this parameter in double-quotes.

5. Execute gnuplot tmp/*.gp.

Hint: For plotting purposes, you can use script separate_by_alg to split the .tab-files in data by algorithm. If you need one file per input size, you can split these file using separate_by_n.