# Minimum maximal solutions of LPs

Linear programming is, of course, nowadays very well understood. We have a lot of work that characterises the structure of feasible solutions, and the structure of optimal solutions. We have the strong duality, poly-time algorithms, etc.

But what is known about minimum maximal solutions of LPs? Or, equivalently, maximum minimal solutions?

(This is not really a research question, but maybe we can have something less technical for the holidays. I'm just being curious, and after some googling I got the feeling that I must be missing the right keywords. It feels like an obvious problem to study, but I only found some sporadic papers that mention the problem.)

To keep things simple, let's focus on packing and covering LPs. In a packing LP we are given a non-negative matrix $A$. A vector $x$ is feasible if $x \ge 0$ and $Ax \le 1$. We say that $x$ is maximal if it is feasible and we can't greedily increase any component. That is, if $y \ge 0$ and $y \ne 0$, then $x + y$ is not feasible. And finally, $x$ is a minimum maximal solution, if it minimises the objective function $\sum_i x_i$ among all maximal solutions.

(You can define a maximum minimal solution of a covering LP in an analogous manner.)

What does the space of minimum maximal solutions look like? How can we find such solutions? How difficult it is to find such solutions? How can we approximate such solutions? Who studies such things, and what is the right term for it?

These questions were originally motivated by edge dominating sets and minimum maximal matchings. It is well known (and fairly easy to see) that a minimum maximal matching is a minimum edge dominating set; conversely, given a minimum edge dominating set, it is easy to construct a minimum maximal matching.

So they are, in essence, the same problem. Both problems are NP-hard and APX-hard. There is a trivial 2-approximation algorithm: any maximal matching.

However, their "natural" LP relaxations look very different. If you take the edge dominating set problem and form a natural LP relaxation, you get a covering LP. However, if you take the problem of finding a minimum maximal matching and try to come up with an LP relaxation, then what do you get? Well, of course fractional matchings are feasible solutions of a packing LP; then maximal fractional matchings are maximal solutions of such LPs, and minimum maximal fractional matchings are therefore minimum maximal solutions of such LPs. :)

• Your definition of maximal as "we can't greedily increase any component" sounds a lot like Nash Equilibrium. Is there a hidden connection to game theory here? – Derrick Stolee Dec 19 '10 at 17:15
• Isn't it the case that for every maximal solution $x'$ in packing LP example, $Ax'=1$?. Then essentially we are looking for a minimum (in $L_{\infty}$-norm) solution of system of linear equations. – Imran Rauf Jan 4 '11 at 17:47
• @Imran: No, I do not think this is correct. A maximal solution (and a maximum solution) always exists, even if we don't have a solution to $Ax = 1$. – Jukka Suomela Jan 4 '11 at 22:48
• Are you familiar with bottleneck linear programs, in which the minimax aspect is all in the objective function? – Mike Spivey Sep 15 '11 at 22:44

You may find it useful to look into blocking and anti-blocking pairs of polyhedra. Say you have a packing problem. Then your feasible region $P$ is a corner polyhedron in the nonnegative orthant, and its anti-blocker $A(P)$ (also a corner polyhedron) is basically the set of inequalities defining $P$.
For example, if you take the stable set polytope $STAB(G)$ for some graph $G$ (i.e. the convex hull of incidence vectors of stable sets), its anti-blocker is the fractional clique polytope of $G$, i.e. $QSTAB(\bar G)$ (i.e. the set of nonnegative weightings such that no stable set has total weight $> 1$).
If you look at "The ellipsoid method and its consequences in combinatorial optimization" by Grötschel, Lovász, and Schrijver, you'll find that optimization over $P$ is in a sense computationally equivalent to optimization over $A(P)$. This is one way to prove that computing the fractional chromatic number is NP-hard, since the dual region to the LP is the anti-blocker of the stable set polytope!