<p>You may find it useful to look into <em>blocking</em> and <em>anti-blocking</em> 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$.</p>

<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$).</p>

<p>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!</p>

<p>Sadly I have had a hard time finding a transparent explanation of this stuff, but I'm by no means an expert on polyhedra.  Hopefully you'll find it relevant to the problem at hand.</p>

CC BY-SA 2.5
2011-01-11T17:21:22.123Z
2011-01-11T17:21:22.123Z
Andrew D. King
<p>Maximality and minimality: They are kinds of Pareto optimality.<br>
Complexity: I think finding a minimum maximal solution is NP-hard.  I would reduce the independence domination problem (aka the minimum maximal independent set problem) in bipartite graphs.  This problem (more precisely its decision version) is known to be NP-complete (D. G. Corneil and Y. Perl, Clustering and domination in perfect graphs.  Discrete Applied Mathematics 9 (1984) 27-39).  Since a bipartite graph is perfect, its independent set polytope is determined by the clique inequalities, and the number of cliques in a bipartite graph is polynomial.  Therefore, we can explicitly write down a system of linear inequalities Ax &lt;= 1, x >= 0 for the independent set polytope.  The extreme solutions correspond to the independent sets, and the extreme maximal solutions correspond to the maximal independent sets.</p>

CC BY-SA 2.5
2010-12-28T16:14:43.590Z
2010-12-28T16:14:43.590Z
Yoshio Okamoto
<p>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.</p>

<p>But what is known about <strong>minimum maximal solutions</strong> of LPs? Or, equivalently, maximum minimal solutions?</p>

<p>(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.)</p>

<hr>

<p>To keep things simple, let's focus on <a href="http://en.wikipedia.org/wiki/Linear_programming#Covering-packing_dualities">packing and covering LPs</a>. In a <strong>packing LP</strong> we are given a <strong>non-negative</strong> matrix $A$. A vector $x$ is <strong>feasible</strong> if $x \ge 0$ and $Ax \le 1$. We say that $x$ is <strong>maximal</strong> 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 <strong>minimum maximal</strong> solution, if it minimises the objective function $\sum_i x_i$ among all maximal solutions.</p>

<p>(You can define a <em>maximum minimal</em> solution of a <em>covering LP</em> in an analogous manner.)</p>

<p>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?</p>

<hr>

<p>These questions were originally motivated by <a href="http://en.wikipedia.org/wiki/Edge_dominating_set">edge dominating sets</a> and <a href="http://en.wikipedia.org/wiki/Matching_%28graph_theory%29#Maximal_matchings">minimum maximal matchings</a>. 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.</p>

<p>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.</p>

<p>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. :)</p>

CC BY-SA 2.5
2010-12-19T17:15:56.537Z
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
CC BY-SA 2.5
2011-01-04T17:47:38.753Z
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
CC BY-SA 2.5
2011-01-04T22:48:32.770Z
@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
CC BY-SA 3.0
2011-09-15T22:44:51.397Z
Are you familiar with *bottleneck linear programs*, in which the minimax aspect is all in the objective function?
Mike Spivey
<cc.complexity-theory><ds.algorithms><reference-request><linear-programming><optimization>
Minimum maximal solutions of LPs
Jukka Suomela
# Minimum maximal solutions of LPs

(Asked by: username_0 on 2010-12-19)

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](http://en.wikipedia.org/wiki/Linear_programming#Covering-packing_dualities). 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](http://en.wikipedia.org/wiki/Edge_dominating_set) and [minimum maximal matchings](http://en.wikipedia.org/wiki/Matching_%28graph_theory%29#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. :)

**Tags:** cc.complexity-theory, ds.algorithms, reference-request, linear-programming, optimization

> **Comments:**
> **username_1**: 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?  
> **username_2**: 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.  
> **username_0**: @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$.  
> **username_3**: Are you familiar with *bottleneck linear programs*, in which the minimax aspect is all in the objective function?  

---

## 2 answers

### Answer by username_5 on 2010-12-28. Score: 11 | Accepted answer

Maximality and minimality: They are kinds of Pareto optimality.  
Complexity: I think finding a minimum maximal solution is NP-hard. I would reduce the independence domination problem (aka the minimum maximal independent set problem) in bipartite graphs. This problem (more precisely its decision version) is known to be NP-complete (D. G. Corneil and Y. Perl, Clustering and domination in perfect graphs. Discrete Applied Mathematics 9 (1984) 27-39). Since a bipartite graph is perfect, its independent set polytope is determined by the clique inequalities, and the number of cliques in a bipartite graph is polynomial. Therefore, we can explicitly write down a system of linear inequalities Ax <= 1, x >= 0 for the independent set polytope. The extreme solutions correspond to the independent sets, and the extreme maximal solutions correspond to the maximal independent sets.


---

### Answer by username_4 on 2011-01-11. Score: 2

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!

Sadly I have had a hard time finding a transparent explanation of this stuff, but I'm by no means an expert on polyhedra. Hopefully you'll find it relevant to the problem at hand.


---

