programming exercise 2


Set \(d=18\).

Consider the \(d\times d\) matrix
The base matrix of coefficients \(a_{ij}, 1\leq i,j\leq d\) is given here; the modifier \(n_j\) is the \(j\)-th digit of your UID squared.

In the following assignment, use simplex method.

3 credits students

Find the least cost bipartite matching where the cost are given by the coefficients \(c_{ij}\), – that is find the permutation \(\sigma=(\sigma_1,\ldots,\sigma_d)\) such that
\sum_{i=1}^d c_{i \sigma(i)}\to\min.

Hint:Use the Birkhoff-von Neumann theorem that the permutation matrices
P_\sigma=\left(p_{ij}\right), p_{ij}=\delta_{\sigma(i)j}
are the vertices of the polyhedron of doubly stochastic matrices
\left\{(p_{ij})_{1\leq i,j\leq d}:\sum_i p_{ij}=1, 1\leq j\leq d; \sum_j p_{ij}=1, 1\leq i\leq d; p_{ij}\geq 0, 1\leq i,j\leq d\right\}

4 credits students

Find the scalar ranking \(r_i, 0\leq i\leq d\) best approximating the tournament \(c_{ij}\) in \(l_\infty\) norm, i.e. minimize
\max_{i,j} \left|c_{ij}-(r_i-r_j)\right|.

Submit your results (code, answers) by midnight of April 25.

20 Responses to programming exercise 2