This program contains two algorithms that solve the Lobbying problem:
1) the simple greedy algorithm as described in "On Approximating Optimal Weighted Lobbying, and Frequency of Correctness Versus Average-Case Polynomial Time, 2007";
2) our greedy heuristic as introduced in "A Multivariate Complexity Analysis of Lobbying in Multiple Referenda, 2012".
For the problem description please refer to our paper "A Multivariate Complexity Analysis of Lobbying in Multiple Referenda".
********************************************************************
* The source code is written in C++.
* To build from source, run the following within the source
* directory:
* autogen.sh
* ./configure
* make
********************************************************************
********************************************************************
* SYNOPSIS
* ols [-s] filename
*
*
* FUNCTION
* Read a binary matrix from a file and compute the number of rows
* to modify to have more ones than zeros in each column. Here,
* modifying a row means making this row an all-ones row.
*
* Two algorithms are used: 1) a simple greedy heuristic as
* described in "On Approximating Optimal Weighted Lobbying, and
* Frequency of Correctness Versus Average-Case Polynomial Time,
* 2007" and 2) our greedy heuristic as described in "A
* Multivariate Complexity Analysis of Lobbying in Multiple
* Referenda, 2012".
*
*
* PARAMETERS
* -s --use the simple greedy heuristic
* -g --also output the rows to be bribed
* filename --the name of a file containing the input matrix.
*
* An example of the format of the input file:
* # k=3,m=5,n=6
* 0 0 0 0 1
* 0 0 1 1 0
* 0 1 0 1 0
* 1 0 1 0 0
* 1 1 0 1 0
* 1 1 1 0 1
* The first line starts with a '#'.
* It specifies three values:
* the minimum number k of rows to modify,
* the number m of columns, and the number n of rows in the given
* matrix. The next n lines indicate the entries of the given
* binary matrix, each line representing a row. In a line, two
* consecutive entries are separated by a space ' '.
*
*
* EXAMPLE
* ./ols test.matrix
*
* OUTPUT
* 2 1 1 1 1 2
* 3 3 0.000032 0.000342
*
* The first line indicates the maximum gap value followed by the
* gap values of each column;
* The second line indicates the minimum number of rows to be
* bribed as as shown in the input file named under k, the number
* of rows to be bribved found by the heuristic, the actual solve
* time (in microseconds), and the time duration (also in
* microseconds) including reading the input matrix etc.
* The file named 'test.matrix' has 5 columns and 6 rows, the
* minimum number rows to be bribed is 3. The maximum gap value
* is 2. The gap values are 1 1 1 1 2. The solve time duration is
* 0.00032 us. The total time duration is 0.000342 us.
********************************************************************