programming exercise 2

\(\def\Real{\mathbb{R}}
\def\Comp{\mathbb{C}}
\def\Rat{\mathbb{Q}}
\def\Field{\mathbb{F}}
\def\Fun{\mathbf{Fun}}
\def\e{\mathbf{e}}
\def\f{\mathbf{f}}
\def\bv{\mathbf{v}}
\)

Set \(d=18\).

Consider the \(d\times d\) matrix
\[
C=\left(c_{ij}\right)_{i,j}
\]
where
\[
c_{ij}=a_{ij}+n_i-n_j.
\]
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