World's most popular travel blog for travel bloggers.

How to read 'max min' and 'min max'?

, , No Comments
Problem Detail: 

Here is an exercise I came across while studying MaxFlow / MinCut and I'm rather stumped:

Designate $G = (V, E)$ as an undirected graph that has at least two vertices. Every edge $(e)$ on this graph has capacity $c_e$. Pick two arbitrary vertices from $G$ and label them $s$ and $t$ respectively.

Now, we'll let $P*$ be the set of $s-t$ paths in the graph, and let $C*$ be the set of $s-t$ cuts -- meaning, $C*$ refers to the subset of edges in $G$ that constitute all possible $s-t$ cuts.

Demonstrate that the following equality is true:

$\max_{P\in P*} \min_{e \in P}c_e = \min_{C \in C*}\max_{e \in C}c_e$

My issue: I'm having trouble parsing the above equation. The LHS appears to be describing the longest(?) of all possible s-t paths, and the edge with the minimum capacity along that path. The RHS appears to be describing the minimum number of edges(?) possible in a subset of edges constituting an s-t cut, and the edge with the max. capacity within that subset? I'm frankly not even sure whether the above equation is meant to involve a multiplication.

Still, I figure there must be a way to parse and understand the equation correctly such that the equality would always hold, and that it can be demonstrated as such. I'd appreciate any help in this matter.

Asked By : user3280193
Answered By : Raphael

I'm frankly not even sure whether the above equation is meant to involve a multiplication.

No, not at all. We have nesting here:

$\max_{X \in \mathcal{X}}\ ( \min_{x \in X} x)$

is the largest minimum of all $X$. Similarly -- but the other way around -- for $\min \max$. This is very similar to nested quantifiers $\forall$ and $\exists$.

Let, for instance, $\mathcal{X} = \{ \{1,2\}, \{3,4\} \}$. Then, the following equalities hold:

  1. $\min_{X \in \mathcal{X}} \min_{x \in X} x = 1$.
  2. $\min_{X \in \mathcal{X}} \max_{x \in X} x = 2$.
  3. $\max_{X \in \mathcal{X}} \min_{x \in X} x = 3$.
  4. $\max_{X \in \mathcal{X}} \max_{x \in X} x = 4$.

Play around with the example by adding more sets to $\mathcal{X}$, more values to the individual sets, and quantify over $f(x)$ instead of just $x$ for different $f$, in order to get a feeling for this.

If you are inclined to algorithmic thinking, do a quick implementation; you'll see how these operators nest more clearly with types, and examples are faster to compute. For instance, the second example would be

Xs.map { X => X.max }.min 
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/55197

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback