# 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|.$