Past exam of the computer science course of the University of Oxford / 2018 / Algorithms / 3

Use the standard maximum form of a linear programAn arbitrary linear program can be converted by the following operations.

These substitutions preserve the attainable objective values, up to the stated sign and constant corrections, and map feasible points in both directions. An alternative standard-form convention uses $Az=b,z\ge 0$: add a nonnegative slack variable to each upper-bound row, or subtract a nonnegative surplus variable from a lower-bound row. The inequality convention above is used in the remaining solutions.

Let $Z$ be the set of isolated vertices of the finite simple graph $G=(V,E)$. Introduce a nonnegative integer $x_v$ for every vertex. Use the integer programEvery nonisolated vertex belongs to an edge, whose inequality and the other endpoint's nonnegativity already imply $x_v\le 1$. The explicit bounds on $Z$ therefore make all variables binary. For an integer feasible point, $S=\{v:x_v=1\}$ is an independent set, and its cardinality is the objective. Conversely the indicator vector of any independent set is feasible. Thus the optimal value is the maximum independent set size. Including the isolated-vertex bounds is essential for an arbitrary graph; without them the formulation would be unbounded whenever an isolated vertex is present.

Remove the integer requirements from the previous formulation to obtain its linear programming relaxation. Give each edge constraint a nonnegative dual variable $y_e$, and each bound for $v\in Z$ a nonnegative dual variable $z_v$. Since all right-hand sides are one, the dual linear program isAn integer feasible point selects a multiset of edges touching every nonisolated vertex, together with at least one singleton for each isolated vertex. Repeated edges or singleton choices can be discarded without losing coverage, so an optimum has a genuine edge cover of the nonisolated part and one singleton per isolated vertex. If $G$ has no isolated vertices, this is exactly an edge cover, with the objective counting selected edges including any unnecessary multiplicities. The isolated-singleton extension is necessary because a graph with an isolated vertex admits no ordinary edge cover.

This interpretation concerns integer feasible dual solutions. The linear programming relaxation can have fractional optima, so its value need not equal the integer independent set optimum. For example, the triangle has relaxed independent-set value $3/2$, whereas its maximum independent set has size $1$ and its minimum edge cover has size $2$.

Regard the two kinds of agents as the two sides of a complete bipartite graph, with edge weight $c_{ij}$. Pairing everyone is a perfect matching, and its maximum total weight is $P$. Consider the capacitated linear programIt is feasible and bounded. Every optimum has all row and column sums equal to one: otherwise the equal total deficits of the two sides give a row $i$ and column $j$ both below one. Increasing $x_{ij}$ by the smaller of their positive deficits remains feasible and increases the objective because $c_{ij}>0$, a contradiction.

Thus an optimum is a doubly stochastic matrix. By the Birkhoff-von Neumann theorem it is a convex combination of permutation matrices, so at least one corresponding perfect matching has weight at least its objective. Conversely every such perfect matching gives a feasible matrix. Hence $P_{\mathrm{LP}}=P$. One way to justify the decomposition is to apply Hall's marriage theorem to the positive-entry support, subtract the smallest entry on a supported perfect matching, and repeat after rescaling the nonzero remainder; each subtraction removes a positive entry, so the process terminates.

The dual linear program assigns nonnegative dual variables $p_i,q_j$ to the row and column capacity constraints:These are exactly the permitted payments and all the pairwise acceptance conditions, so its optimal value is $Q$. It is feasible, for example by taking $p_i={\max }_j{c}_{ij}$ and $q_j=0$. Strong duality now gives $P=P_{\mathrm{LP}}=Q$. In particular, the nonnegative payment restriction has been retained throughout; using capacity inequalities rather than equality constraints avoids introducing unrestricted prices.

For a direct weak duality check, sum $p_i+q_{\pi (i)}\ge c_{i,\pi (i)}$ over any pairing $\pi$. Its revenue never exceeds the company's total offered payment. The linear programming duality and integrality argument prove that this lower bound on payments is attained.

Combine all inequalities, including nonnegativity, into $Cx\le d$; explicitly, the rows $-e_j^{T}x\le 0$ encode $x_j\ge 0$. Let $x_{\ast }$ be a vertex of a linear polyhedron, equivalently an extreme point of the feasible linear polyhedron, and let $I$ index the active constraints there.

Suppose the active row normals have rank smaller than $n$. By the rank-nullity theorem there is a nonzero vector $h$ with $C_{i}h=0$ for every $i\in I$. Every inactive row has positive slack variable value $s_i=d_i-C_i{x}_{\ast }>0$. Since there are only finitely many rows, choose $\epsilon >0$ so small thatThen both $x_{\ast }+\epsilon h$ and $x_{\ast }-\epsilon h$ are feasible points: the active constraints remain equalities and no inactive inequality is violated. They are distinct, and $x_{\ast }$ is their midpoint, contradicting the extreme point property.

Therefore the active row normals have rank $n$, and at least $n$ linearly independent constraints are satisfied with equality. In particular at least $n$ constraints are tight, as claimed. Nonnegativity bounds must be counted: for example, at the origin these can supply all $n$ active rows. Degeneracy can make more than $n$ constraints tight, so the result does not assert exactly $n$.