TCS Wiki - User contributions [en]

Combinatorics (Fall 2010)/Flow and matching

2010-12-26T07:28:29Z

172.21.5.190: /* Integrality of polytopes */

== Flow and Cut==

=== Flows ===
An instance of the maximum flow problem consists of:
* a directed graph <math>G(V,E)</math>;
* two distinguished vertices <math>s</math> (the '''source''') and <math>t</math> (the '''sink'''), where the in-degree of <math>s</math> and the out-degree of <math>t</math> are both 0;
* the '''capacity function''' <math>c:E\rightarrow\mathbb{R}^+</math> which associates each directed edge <math>(u,v)\in E</math> a nonnegative real number <math>c_{uv}</math> called the '''capacity''' of the edge.

The quadruple <math>(G,c,s,t)</math> is called a '''flow network'''.

A function <math>f:E\rightarrow\mathbb{R}^+</math> is called a '''flow''' (to be specific an '''<math>s</math>-<math>t</math> flow''') in the network <math>G(V,E)</math> if it satisfies:
* '''Capacity constraint:''' <math>f_{uv}\le c_{uv}</math> for all <math>(u,v)\in E</math>.
* '''Conservation constraint:''' <math>\sum_{u:(u,v)\in E}f_{uv}=\sum_{w:(v,w)\in E}f_{vw}</math> for all <math>v\in V\setminus\{s,t\}</math>.

The '''value''' of the flow <math>f</math> is <math>\sum_{v:(s,v)\in E}f_{sv}</math>.

Given a flow network, the maximum flow problem asks to find the flow of the maximum value.

The maximum flow problem can be described as the following linear program.
:<math>
\begin{align}
\text{maximize} \quad& \sum_{v:(s,v)\in E}f_{sv}\\
\begin{align}
\text{subject to} \\
\\
\\
\\
\end{align}
\quad &
\begin{align} f_{uv}&\le c_{uv} &\quad& \forall (u,v)\in E\\
\sum_{u:(u,v)\in E}f_{uv}-\sum_{w:(v,w)\in E}f_{vw} &=0 &\quad& \forall v\in V\setminus\{s,t\}\\
f_{uv}&\ge 0 &\quad& \forall (u,v)\in E
\end{align}
\end{align}
</math>

=== Cuts ===
{{Theorem|Definition|
:Let <math>(G(V,E),c,s,t)</math> be a flow network. Let <math>S\subset V</math>. We call <math>(S,\bar{S})</math> an '''<math>s</math>-<math>t</math> cut''' if <math>s\in S</math> and <math>t\not\in S</math>.
:The '''value''' of the cut (also called the '''capacity''' of the cut) is defined as <math>\sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>.
}}

A fundamental fact in flow theory is that cuts always upper bound flows.

{{Theorem|Lemma|
:Let <math>(G(V,E),c,s,t)</math> be a flow network. Let <math>f</math> be an arbitrary flow in <math>G</math>, and let <math>(S,\bar{S})</math> be an arbitrary <math>s</math>-<math>t</math> cut. Then
::<math>\sum_{v:(s,v)}f_{sv}\le \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>,
:that is, the value of any flow is no greater than the value of any cut.
}}
{{Proof|By the definition of <math>s</math>-<math>t</math> cut, <math>s\in S</math> and <math>t\not\in S</math>.

Due to the conservation of flow,
:<math>\sum_{u\in S}\left(\sum_{v:(u,v)\in E}f_{uv}-\sum_{v:(v,u)\in E}f_{vu}\right)=\sum_{v:(s,v)\in E}f_{sv}+\sum_{u\in S\setminus\{s\}}\left(\sum_{v:(u,v)\in E}f_{uv}-\sum_{v:(v,u)\in E}f_{vu}\right)=\sum_{v:(s,v)\in E}f_{sv}\,.</math>
On the other hand, summing flow over edges,
:<math>\sum_{v\in S}\left(\sum_{u:(u,v)\in E}f_{uv}-\sum_{u:(v,u)\in E}f_{vu}\right)=\sum_{u\in S,v\in S\atop (u,v)\in E}\left(f_{uv}-f_{uv}\right)+\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu}=\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu}\,.</math>
Therefore,
:<math>\sum_{v:(s,v)\in E}f_{sv}=\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu}\le\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}\le \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}\,,</math>
}}

=== Augmenting paths ===
{{Theorem|Definition (Augmenting path)|
:Let <math>f</math> be a flow in <math>G</math>. An '''augmenting path to <math>u_k</math>''' is a sequence of distinct vertices <math>P=(u_0,u_1,\cdots, u_k)</math>, such that
:* <math>u_0=s\,</math>;
:and each pair of consecutive vertices <math>u_{i}u_{i+1}\,</math> in <math>P</math> corresponds to either a '''forward edge''' <math>(u_{i},u_{i+1})\in E</math> or a '''reverse edge''' <math>(u_{i+1},u_{i})\in E</math>, and
:* <math>f(u_i,u_{i+1})<c(u_i,u_{i+1})\,</math> when <math>u_{i}u_{i+1}\,</math> corresponds to a forward edge <math>(u_{i},u_{i+1})\in E</math>, and
:* <math>f(u_{i+1},u_i)>0\,</math> when <math>u_{i}u_{i+1}\,</math> corresponds to a reverse edge <math>(u_{i+1},u_{i})\in E</math>.
:If <math>u_k=t\,</math>, we simply call <math>P</math> an '''augmenting path'''.
}}

Let <math>f</math> be a flow in <math>G</math>. Suppose there is an augmenting path <math>P=u_0u_1\cdots u_k</math>, where <math>u_0=s</math> and <math>u_k=t</math>. Let <math>\epsilon>0</math> be a positive constant satisfying
*<math>\epsilon \le c(u_{i},u_{i+1})-f(u_i,u_{i+1})</math> for all forward edges <math>(u_{i},u_{i+1})\in E</math> in <math>P</math>;
*<math>\epsilon \le f(u_{i+1},u_i)</math> for all reverse edges <math>(u_{i+1},u_i)\in E</math> in <math>P</math>.
Due to the definition of augmenting path, we can always find such a positive <math>\epsilon</math>.

Increase <math>f(u_i,u_{i+1})</math> by <math>\epsilon</math> for all forward edges <math>(u_{i},u_{i+1})\in E</math> in <math>P</math> and decrease <math>f(u_{i+1},u_i)</math> by <math>\epsilon</math> for all reverse edges <math>(u_{i+1},u_i)\in E</math> in <math>P</math>. Denote the modified flow by <math>f'</math>. It can be verified that <math>f'</math> satisfies the capacity constraint and conservation constraint thus is still a valid flow. On the other hand, the value of the new flow <math>f'</math>
:<math>\sum_{v:(s,v)\in E}f_{sv}'=\epsilon+\sum_{v:(s,v)\in E}f_{sv}>\sum_{v:(s,v)\in E}f_{sv}</math>.
Therefore, the value of the flow can be "augmented" by adjusting the flow on the augmenting path. This immediately implies that if a flow is maximum, then there is no augmenting path. Surprisingly, the converse is also true, thus maximum flows are "characterized" by augmenting paths.

{{Theorem|Lemma|
:A flow <math>f</math> is maximum if and only if there are no augmenting paths.
}}
{{Proof|We have already proved the "only if" direction above. Now we prove the "if" direction.

Let <math>S=\{u\in V\mid \exists\text{an augmenting path to }u\}</math>. Clearly <math>s\in S</math>, and since there is no augmenting path <math>t\not\in S</math>. Therefore, <math>(S,\bar{S})</math> defines an <math>s</math>-<math>t</math> cut.

We claim that
:<math>\sum_{v:(s,v)}f_{sv}= \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>,
that is, the value of flow <math>f</math> approach the value of the cut <math>(S,\bar{S})</math> defined above. By the above lemma, this will imply that the current flow <math>f</math> is maximum.

To prove this claim, we first observe that
:<math>\sum_{v:(s,v)}f_{sv}= \sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu}</math>.
This identity is implied by the flow conservation constraint, and holds for any <math>s</math>-<math>t</math> cut <math>(S,\bar{S})</math>.

We then claim that
*<math>f_{uv}=c_{uv}</math> for all <math>u\in S,v\not\in S, (u,v)\in E</math>; and
*<math>f_{vu}=0</math> for all <math>u\in S,v\not\in S, (v,u)\in E</math>.
If otherwise, then the augmenting path to <math>u</math> apending <math>uv</math> becomes a new augmenting path to <math>v</math>, which contradicts that <math>S</math> includes all vertices to which there exist augmenting paths.

Therefore,
:<math>\sum_{v:(s,v)}f_{sv}= \sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu} = \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>.
As discussed above, this proves the theorem.
}}

=== The max-flow min-cut theorem ===
{{Theorem|Max-Flow Min-Cut Theorem|
:In a flow network, the maximum value of any <math>s</math>-<math>t</math> flow equals the minimum value of any <math>s</math>-<math>t</math> cut.
}}

{{Proof|
Let <math>f</math> be a flow with maximum value, so there is no augmenting path.

Again, let <math>S=\{u\in V\mid \exists\text{an augmenting path to }u\}</math>. As proved above, <math>(S,\bar{S})</math> forms an <math>s</math>-<math>t</math> cut, and
:<math>\sum_{v:(s,v)}f_{sv}= \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>,
that is, the value of flow <math>f</math> equals the value of cut <math>(S,\bar{S})</math>.

Since we know that all <math>s</math>-<math>t</math> flows are not greater than any <math>s</math>-<math>t</math> cut, the value of flow <math>f</math> equals the minimum value of any <math>s</math>-<math>t</math> cut.
}}

{{Theorem|Flow Integrality Theorem|
:Let <math>(G,c,s,t)</math> be a flow network with integral capacity <math>c</math>. There exists an integral flow which is maximum.
}}
{{Proof|
Let <math>f</math> be an integral flow of maximum value. If there is an augmenting path, since both <math>c</math> and <math>f</math> are integral, a new flow can be constructed of value 1+the value of <math>f</math>, contradicting that <math>f</math> is maximum over all integral flows. Therefore, there is no augmenting path, which means that <math>f</math> is maximum over all flows, integral or not.
}}

== Unimodularity ==

=== Integer Programming===

=== Integrality of polytopes ===
A point in an <math>n</math>-dimensional space is integral if all its coordinates are integers.

A polyhedron is said to be '''integral''' if all its vertices are integral.

There always exists an optimal solution which is a vertex in <math>P</math>. For integral <math>P</math>, all vertices are integral.

{{Theorem|Theorem (Hoffman 1974)|
: If a polyhedron <math>P</math> is integral then for all integer vectors <math>\boldsymbol{c}</math> there is an optimal solution to <math>\max\{\boldsymbol{c}^T\boldsymbol{x}\mid \boldsymbol{x}\in P\}</math> which is integral.
}}

=== Unimodularity and total unimodularity ===
{{Theorem|Definition (Unimodularity)|
:An <math>n\times n</math> integer matrix <math>A</math> is called '''unimodular''' if <math>\det(A)=\pm1</math>.
:An <math>m\times n</math> integer matrix <math>A</math> is called '''total unimodular''' if every square submatrix <math>B</math> of <math>A</math> has <math>\det(B)\in\{1,-1,0\}</math>, that is, every square, nonsingular submatrix of <math>A</math> is unimodular.
}}

{{Theorem|Theorem|
:Let <math>A</math> be an <math>m\times n</math> integer matrix.
:If <math>A</math> is totally unimodualr, then for any integer vector <math>\boldsymbol{b}\in\mathbb{Z}^n</math> the polyhedron <math>\{\boldsymbol{x}\in\mathbb{R}^n\mid A\boldsymbol{x}=\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}\}</math> is integral.
}}
{{Proof|
Let <math>B</math> be a basis of <math>A</math>, and let <math>\boldsymbol{b}'</math> be the corresponding coordinates in <math>\boldsymbol{b}</math>. A basic solution is formed by <math>B^{-1}\boldsymbol{b}'</math> and zeros. Since <math>A</math> is totally unimodular and <math>B</math> is a basis thus nonsingular, <math>\det(B)\in\{1,-1,0\}</math>. By [http://en.wikipedia.org/wiki/Cramer's_rule Cramer's rule], <math>B^{-1}</math> has integer entries, thus <math>B^{-1}\boldsymbol{b}'</math> is integral. Therefore, any basic solution of <math>A\boldsymbol{x}=\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}</math> is integral, which means the polyhedron <math>\{\boldsymbol{x}\in\mathbb{R}^n\mid A\boldsymbol{x}=\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}\}</math> is integral.
}}

{{Theorem|Theorem (Hoffman-Kruskal 1956)|
:Let <math>A</math> be an <math>m\times n</math> integer matrix.
:If <math>A</math> is totally unimodualr, then for any integer vector <math>\boldsymbol{b}\in\mathbb{Z}^n</math> the polyhedron <math>\{\boldsymbol{x}\in\mathbb{R}^n\mid A\boldsymbol{x}\ge\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}\}</math> is integral.
}}
{{Proof|
Let <math>A'=\begin{bmatrix}A & -I\end{bmatrix}</math>. We claim that <math>A'</math> is also totally unimodular. Any square submatrix <math>B</math> of <math>A</math> can be written in the following form after permutation:
:<math>B=\begin{bmatrix}
C & 0\\
D & I
\end{bmatrix}</math>
where <math>C</math> is a square submatrix of <math>A</math> and <math>I</math> is identity matrix. Therefore,
:<math>\det(B)=\det(C)\in\{1,-1,0\}</math>,
thus <math>A'</math> is totally unimodular.

Add slack variables to transform the constraints to the standard form <math>A'\boldsymbol{z}=\boldsymbol{b},\boldsymbol{z}\ge\boldsymbol{0}</math>. The polyhedron <math>\{\boldsymbol{x}\mid A\boldsymbol{x}\ge\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}\}</math> is integral if the polyhedron <math>\{\boldsymbol{z}\mid A'\boldsymbol{z}=\boldsymbol{b}, \boldsymbol{z}\ge \boldsymbol{0}\}</math> is integral, which is implied by the total unimodularity of <math>A'\,</math>.
}}

Combinatorics (Fall 2010)/Flow and matching

2010-12-26T07:10:55Z

172.21.5.190: /* Cuts */

== Flow and Cut==

=== Flows ===
An instance of the maximum flow problem consists of:
* a directed graph <math>G(V,E)</math>;
* two distinguished vertices <math>s</math> (the '''source''') and <math>t</math> (the '''sink'''), where the in-degree of <math>s</math> and the out-degree of <math>t</math> are both 0;
* the '''capacity function''' <math>c:E\rightarrow\mathbb{R}^+</math> which associates each directed edge <math>(u,v)\in E</math> a nonnegative real number <math>c_{uv}</math> called the '''capacity''' of the edge.

The quadruple <math>(G,c,s,t)</math> is called a '''flow network'''.

A function <math>f:E\rightarrow\mathbb{R}^+</math> is called a '''flow''' (to be specific an '''<math>s</math>-<math>t</math> flow''') in the network <math>G(V,E)</math> if it satisfies:
* '''Capacity constraint:''' <math>f_{uv}\le c_{uv}</math> for all <math>(u,v)\in E</math>.
* '''Conservation constraint:''' <math>\sum_{u:(u,v)\in E}f_{uv}=\sum_{w:(v,w)\in E}f_{vw}</math> for all <math>v\in V\setminus\{s,t\}</math>.

The '''value''' of the flow <math>f</math> is <math>\sum_{v:(s,v)\in E}f_{sv}</math>.

Given a flow network, the maximum flow problem asks to find the flow of the maximum value.

The maximum flow problem can be described as the following linear program.
:<math>
\begin{align}
\text{maximize} \quad& \sum_{v:(s,v)\in E}f_{sv}\\
\begin{align}
\text{subject to} \\
\\
\\
\\
\end{align}
\quad &
\begin{align} f_{uv}&\le c_{uv} &\quad& \forall (u,v)\in E\\
\sum_{u:(u,v)\in E}f_{uv}-\sum_{w:(v,w)\in E}f_{vw} &=0 &\quad& \forall v\in V\setminus\{s,t\}\\
f_{uv}&\ge 0 &\quad& \forall (u,v)\in E
\end{align}
\end{align}
</math>

=== Cuts ===
{{Theorem|Definition|
:Let <math>(G(V,E),c,s,t)</math> be a flow network. Let <math>S\subset V</math>. We call <math>(S,\bar{S})</math> an '''<math>s</math>-<math>t</math> cut''' if <math>s\in S</math> and <math>t\not\in S</math>.
:The '''value''' of the cut (also called the '''capacity''' of the cut) is defined as <math>\sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>.
}}

A fundamental fact in flow theory is that cuts always upper bound flows.

{{Theorem|Lemma|
:Let <math>(G(V,E),c,s,t)</math> be a flow network. Let <math>f</math> be an arbitrary flow in <math>G</math>, and let <math>(S,\bar{S})</math> be an arbitrary <math>s</math>-<math>t</math> cut. Then
::<math>\sum_{v:(s,v)}f_{sv}\le \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>,
:that is, the value of any flow is no greater than the value of any cut.
}}
{{Proof|By the definition of <math>s</math>-<math>t</math> cut, <math>s\in S</math> and <math>t\not\in S</math>.

Due to the conservation of flow,
:<math>\sum_{u\in S}\left(\sum_{v:(u,v)\in E}f_{uv}-\sum_{v:(v,u)\in E}f_{vu}\right)=\sum_{v:(s,v)\in E}f_{sv}+\sum_{u\in S\setminus\{s\}}\left(\sum_{v:(u,v)\in E}f_{uv}-\sum_{v:(v,u)\in E}f_{vu}\right)=\sum_{v:(s,v)\in E}f_{sv}\,.</math>
On the other hand, summing flow over edges,
:<math>\sum_{v\in S}\left(\sum_{u:(u,v)\in E}f_{uv}-\sum_{u:(v,u)\in E}f_{vu}\right)=\sum_{u\in S,v\in S\atop (u,v)\in E}\left(f_{uv}-f_{uv}\right)+\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu}=\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu}\,.</math>
Therefore,
:<math>\sum_{v:(s,v)\in E}f_{sv}=\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu}\le\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}\le \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}\,,</math>
}}

=== Augmenting paths ===
{{Theorem|Definition (Augmenting path)|
:Let <math>f</math> be a flow in <math>G</math>. An '''augmenting path to <math>u_k</math>''' is a sequence of distinct vertices <math>P=(u_0,u_1,\cdots, u_k)</math>, such that
:* <math>u_0=s\,</math>;
:and each pair of consecutive vertices <math>u_{i}u_{i+1}\,</math> in <math>P</math> corresponds to either a '''forward edge''' <math>(u_{i},u_{i+1})\in E</math> or a '''reverse edge''' <math>(u_{i+1},u_{i})\in E</math>, and
:* <math>f(u_i,u_{i+1})<c(u_i,u_{i+1})\,</math> when <math>u_{i}u_{i+1}\,</math> corresponds to a forward edge <math>(u_{i},u_{i+1})\in E</math>, and
:* <math>f(u_{i+1},u_i)>0\,</math> when <math>u_{i}u_{i+1}\,</math> corresponds to a reverse edge <math>(u_{i+1},u_{i})\in E</math>.
:If <math>u_k=t\,</math>, we simply call <math>P</math> an '''augmenting path'''.
}}

Let <math>f</math> be a flow in <math>G</math>. Suppose there is an augmenting path <math>P=u_0u_1\cdots u_k</math>, where <math>u_0=s</math> and <math>u_k=t</math>. Let <math>\epsilon>0</math> be a positive constant satisfying
*<math>\epsilon \le c(u_{i},u_{i+1})-f(u_i,u_{i+1})</math> for all forward edges <math>(u_{i},u_{i+1})\in E</math> in <math>P</math>;
*<math>\epsilon \le f(u_{i+1},u_i)</math> for all reverse edges <math>(u_{i+1},u_i)\in E</math> in <math>P</math>.
Due to the definition of augmenting path, we can always find such a positive <math>\epsilon</math>.

Increase <math>f(u_i,u_{i+1})</math> by <math>\epsilon</math> for all forward edges <math>(u_{i},u_{i+1})\in E</math> in <math>P</math> and decrease <math>f(u_{i+1},u_i)</math> by <math>\epsilon</math> for all reverse edges <math>(u_{i+1},u_i)\in E</math> in <math>P</math>. Denote the modified flow by <math>f'</math>. It can be verified that <math>f'</math> satisfies the capacity constraint and conservation constraint thus is still a valid flow. On the other hand, the value of the new flow <math>f'</math>
:<math>\sum_{v:(s,v)\in E}f_{sv}'=\epsilon+\sum_{v:(s,v)\in E}f_{sv}>\sum_{v:(s,v)\in E}f_{sv}</math>.
Therefore, the value of the flow can be "augmented" by adjusting the flow on the augmenting path. This immediately implies that if a flow is maximum, then there is no augmenting path. Surprisingly, the converse is also true, thus maximum flows are "characterized" by augmenting paths.

{{Theorem|Lemma|
:A flow <math>f</math> is maximum if and only if there are no augmenting paths.
}}
{{Proof|We have already proved the "only if" direction above. Now we prove the "if" direction.

Let <math>S=\{u\in V\mid \exists\text{an augmenting path to }u\}</math>. Clearly <math>s\in S</math>, and since there is no augmenting path <math>t\not\in S</math>. Therefore, <math>(S,\bar{S})</math> defines an <math>s</math>-<math>t</math> cut.

We claim that
:<math>\sum_{v:(s,v)}f_{sv}= \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>,
that is, the value of flow <math>f</math> approach the value of the cut <math>(S,\bar{S})</math> defined above. By the above lemma, this will imply that the current flow <math>f</math> is maximum.

To prove this claim, we first observe that
:<math>\sum_{v:(s,v)}f_{sv}= \sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu}</math>.
This identity is implied by the flow conservation constraint, and holds for any <math>s</math>-<math>t</math> cut <math>(S,\bar{S})</math>.

We then claim that
*<math>f_{uv}=c_{uv}</math> for all <math>u\in S,v\not\in S, (u,v)\in E</math>; and
*<math>f_{vu}=0</math> for all <math>u\in S,v\not\in S, (v,u)\in E</math>.
If otherwise, then the augmenting path to <math>u</math> apending <math>uv</math> becomes a new augmenting path to <math>v</math>, which contradicts that <math>S</math> includes all vertices to which there exist augmenting paths.

Therefore,
:<math>\sum_{v:(s,v)}f_{sv}= \sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu} = \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>.
As discussed above, this proves the theorem.
}}

=== The max-flow min-cut theorem ===
{{Theorem|Max-Flow Min-Cut Theorem|
:In a flow network, the maximum value of any <math>s</math>-<math>t</math> flow equals the minimum value of any <math>s</math>-<math>t</math> cut.
}}

{{Proof|
Let <math>f</math> be a flow with maximum value, so there is no augmenting path.

Again, let <math>S=\{u\in V\mid \exists\text{an augmenting path to }u\}</math>. As proved above, <math>(S,\bar{S})</math> forms an <math>s</math>-<math>t</math> cut, and
:<math>\sum_{v:(s,v)}f_{sv}= \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>,
that is, the value of flow <math>f</math> equals the value of cut <math>(S,\bar{S})</math>.

Since we know that all <math>s</math>-<math>t</math> flows are not greater than any <math>s</math>-<math>t</math> cut, the value of flow <math>f</math> equals the minimum value of any <math>s</math>-<math>t</math> cut.
}}

{{Theorem|Flow Integrality Theorem|
:Let <math>(G,c,s,t)</math> be a flow network with integral capacity <math>c</math>. There exists an integral flow which is maximum.
}}
{{Proof|
Let <math>f</math> be an integral flow of maximum value. If there is an augmenting path, since both <math>c</math> and <math>f</math> are integral, a new flow can be constructed of value 1+the value of <math>f</math>, contradicting that <math>f</math> is maximum over all integral flows. Therefore, there is no augmenting path, which means that <math>f</math> is maximum over all flows, integral or not.
}}

== Unimodularity ==

=== Integer Programming===

=== Integrality of polytopes ===

=== Unimodularity and total unimodularity ===
{{Theorem|Definition (Unimodularity)|
:An <math>n\times n</math> integer matrix <math>A</math> is called '''unimodular''' if <math>\det(A)=\pm1</math>.
:An <math>m\times n</math> integer matrix <math>A</math> is called '''total unimodular''' if every square submatrix <math>B</math> of <math>A</math> has <math>\det(B)\in\{1,-1,0\}</math>, that is, every square, nonsingular submatrix of <math>A</math> is unimodular.
}}

{{Theorem|Theorem|
:Let <math>A</math> be an <math>m\times n</math> integer matrix.
:If <math>A</math> is totally unimodualr, then for any integer vector <math>\boldsymbol{b}\in\mathbb{Z}^n</math> the polyhedron <math>\{\boldsymbol{x}\in\mathbb{R}^n\mid A\boldsymbol{x}=\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}\}</math> is integral.
}}
{{Proof|
Let <math>B</math> be a basis of <math>A</math>, and let <math>\boldsymbol{b}'</math> be the corresponding coordinates in <math>\boldsymbol{b}</math>. A basic solution is formed by <math>B^{-1}\boldsymbol{b}'</math> and zeros. Since <math>A</math> is totally unimodular and <math>B</math> is a basis thus nonsingular, <math>\det(B)\in\{1,-1,0\}</math>. By [http://en.wikipedia.org/wiki/Cramer's_rule Cramer's rule], <math>B^{-1}</math> has integer entries, thus <math>B^{-1}\boldsymbol{b}'</math> is integral. Therefore, any basic solution of <math>A\boldsymbol{x}=\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}</math> is integral, which means the polyhedron <math>\{\boldsymbol{x}\in\mathbb{R}^n\mid A\boldsymbol{x}=\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}\}</math> is integral.
}}

{{Theorem|Theorem (Hoffman-Kruskal 1956)|
:Let <math>A</math> be an <math>m\times n</math> integer matrix.
:If <math>A</math> is totally unimodualr, then for any integer vector <math>\boldsymbol{b}\in\mathbb{Z}^n</math> the polyhedron <math>\{\boldsymbol{x}\in\mathbb{R}^n\mid A\boldsymbol{x}\ge\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}\}</math> is integral.
}}
{{Proof|
Let <math>A'=\begin{bmatrix}A & -I\end{bmatrix}</math>. We claim that <math>A'</math> is also totally unimodular. Any square submatrix <math>B</math> of <math>A</math> can be written in the following form after permutation:
:<math>B=\begin{bmatrix}
C & 0\\
D & I
\end{bmatrix}</math>
where <math>C</math> is a square submatrix of <math>A</math> and <math>I</math> is identity matrix. Therefore,
:<math>\det(B)=\det(C)\in\{1,-1,0\}</math>,
thus <math>A'</math> is totally unimodular.

Add slack variables to transform the constraints to the standard form <math>A'\boldsymbol{z}=\boldsymbol{b},\boldsymbol{z}\ge\boldsymbol{0}</math>. The polyhedron <math>\{\boldsymbol{x}\mid A\boldsymbol{x}\ge\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}\}</math> is integral if the polyhedron <math>\{\boldsymbol{z}\mid A'\boldsymbol{z}=\boldsymbol{b}, \boldsymbol{z}\ge \boldsymbol{0}\}</math> is integral, which is implied by the total unimodularity of <math>A'\,</math>.
}}

Combinatorics (Fall 2010)/Flow and matching

2010-12-26T07:09:55Z

172.21.5.190: /* Integer Programmings */

== Flow and Cut==

=== Flows ===
An instance of the maximum flow problem consists of:
* a directed graph <math>G(V,E)</math>;
* two distinguished vertices <math>s</math> (the '''source''') and <math>t</math> (the '''sink'''), where the in-degree of <math>s</math> and the out-degree of <math>t</math> are both 0;
* the '''capacity function''' <math>c:E\rightarrow\mathbb{R}^+</math> which associates each directed edge <math>(u,v)\in E</math> a nonnegative real number <math>c_{uv}</math> called the '''capacity''' of the edge.

The quadruple <math>(G,c,s,t)</math> is called a '''flow network'''.

A function <math>f:E\rightarrow\mathbb{R}^+</math> is called a '''flow''' (to be specific an '''<math>s</math>-<math>t</math> flow''') in the network <math>G(V,E)</math> if it satisfies:
* '''Capacity constraint:''' <math>f_{uv}\le c_{uv}</math> for all <math>(u,v)\in E</math>.
* '''Conservation constraint:''' <math>\sum_{u:(u,v)\in E}f_{uv}=\sum_{w:(v,w)\in E}f_{vw}</math> for all <math>v\in V\setminus\{s,t\}</math>.

The '''value''' of the flow <math>f</math> is <math>\sum_{v:(s,v)\in E}f_{sv}</math>.

Given a flow network, the maximum flow problem asks to find the flow of the maximum value.

The maximum flow problem can be described as the following linear program.
:<math>
\begin{align}
\text{maximize} \quad& \sum_{v:(s,v)\in E}f_{sv}\\
\begin{align}
\text{subject to} \\
\\
\\
\\
\end{align}
\quad &
\begin{align} f_{uv}&\le c_{uv} &\quad& \forall (u,v)\in E\\
\sum_{u:(u,v)\in E}f_{uv}-\sum_{w:(v,w)\in E}f_{vw} &=0 &\quad& \forall v\in V\setminus\{s,t\}\\
f_{uv}&\ge 0 &\quad& \forall (u,v)\in E
\end{align}
\end{align}
</math>

=== Cuts ===
{{Theorem|Definition|
:Let <math>(G(V,E),c,s,t)</math> be a flow network. Let <math>S\subset V</math>. We call <math>(S,\bar{S})</math> an '''<math>s</math>-<math>t</math> cut''' if <math>s\in S</math> and <math>t\not\in S</math>.
:The '''value''' of the cut (also called the '''capacity''' of the cut) is defined as <math>\sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>.
}}

A fundamental fact in the theory of flow is that cuts always upper bound flows.

{{Theorem|Lemma|
:Let <math>(G(V,E),c,s,t)</math> be a flow network. Let <math>f</math> be an arbitrary flow in <math>G</math>, and let <math>(S,\bar{S})</math> be an arbitrary <math>s</math>-<math>t</math> cut. Then
::<math>\sum_{v:(s,v)}f_{sv}\le \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>,
:that is, the value of any flow is no greater than the value of any cut.
}}
{{Proof|By the definition of <math>s</math>-<math>t</math> cut, <math>s\in S</math> and <math>t\not\in S</math>.

Due to the conservation of flow,
:<math>\sum_{u\in S}\left(\sum_{v:(u,v)\in E}f_{uv}-\sum_{v:(v,u)\in E}f_{vu}\right)=\sum_{v:(s,v)\in E}f_{sv}+\sum_{u\in S\setminus\{s\}}\left(\sum_{v:(u,v)\in E}f_{uv}-\sum_{v:(v,u)\in E}f_{vu}\right)=\sum_{v:(s,v)\in E}f_{sv}\,.</math>
On the other hand, summing flow over edges,
:<math>\sum_{v\in S}\left(\sum_{u:(u,v)\in E}f_{uv}-\sum_{u:(v,u)\in E}f_{vu}\right)=\sum_{u\in S,v\in S\atop (u,v)\in E}\left(f_{uv}-f_{uv}\right)+\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu}=\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu}\,.</math>
Therefore,
:<math>\sum_{v:(s,v)\in E}f_{sv}=\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu}\le\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}\le \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}\,,</math>
}}

=== Augmenting paths ===
{{Theorem|Definition (Augmenting path)|
:Let <math>f</math> be a flow in <math>G</math>. An '''augmenting path to <math>u_k</math>''' is a sequence of distinct vertices <math>P=(u_0,u_1,\cdots, u_k)</math>, such that
:* <math>u_0=s\,</math>;
:and each pair of consecutive vertices <math>u_{i}u_{i+1}\,</math> in <math>P</math> corresponds to either a '''forward edge''' <math>(u_{i},u_{i+1})\in E</math> or a '''reverse edge''' <math>(u_{i+1},u_{i})\in E</math>, and
:* <math>f(u_i,u_{i+1})<c(u_i,u_{i+1})\,</math> when <math>u_{i}u_{i+1}\,</math> corresponds to a forward edge <math>(u_{i},u_{i+1})\in E</math>, and
:* <math>f(u_{i+1},u_i)>0\,</math> when <math>u_{i}u_{i+1}\,</math> corresponds to a reverse edge <math>(u_{i+1},u_{i})\in E</math>.
:If <math>u_k=t\,</math>, we simply call <math>P</math> an '''augmenting path'''.
}}

Let <math>f</math> be a flow in <math>G</math>. Suppose there is an augmenting path <math>P=u_0u_1\cdots u_k</math>, where <math>u_0=s</math> and <math>u_k=t</math>. Let <math>\epsilon>0</math> be a positive constant satisfying
*<math>\epsilon \le c(u_{i},u_{i+1})-f(u_i,u_{i+1})</math> for all forward edges <math>(u_{i},u_{i+1})\in E</math> in <math>P</math>;
*<math>\epsilon \le f(u_{i+1},u_i)</math> for all reverse edges <math>(u_{i+1},u_i)\in E</math> in <math>P</math>.
Due to the definition of augmenting path, we can always find such a positive <math>\epsilon</math>.

Increase <math>f(u_i,u_{i+1})</math> by <math>\epsilon</math> for all forward edges <math>(u_{i},u_{i+1})\in E</math> in <math>P</math> and decrease <math>f(u_{i+1},u_i)</math> by <math>\epsilon</math> for all reverse edges <math>(u_{i+1},u_i)\in E</math> in <math>P</math>. Denote the modified flow by <math>f'</math>. It can be verified that <math>f'</math> satisfies the capacity constraint and conservation constraint thus is still a valid flow. On the other hand, the value of the new flow <math>f'</math>
:<math>\sum_{v:(s,v)\in E}f_{sv}'=\epsilon+\sum_{v:(s,v)\in E}f_{sv}>\sum_{v:(s,v)\in E}f_{sv}</math>.
Therefore, the value of the flow can be "augmented" by adjusting the flow on the augmenting path. This immediately implies that if a flow is maximum, then there is no augmenting path. Surprisingly, the converse is also true, thus maximum flows are "characterized" by augmenting paths.

{{Theorem|Lemma|
:A flow <math>f</math> is maximum if and only if there are no augmenting paths.
}}
{{Proof|We have already proved the "only if" direction above. Now we prove the "if" direction.

Let <math>S=\{u\in V\mid \exists\text{an augmenting path to }u\}</math>. Clearly <math>s\in S</math>, and since there is no augmenting path <math>t\not\in S</math>. Therefore, <math>(S,\bar{S})</math> defines an <math>s</math>-<math>t</math> cut.

We claim that
:<math>\sum_{v:(s,v)}f_{sv}= \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>,
that is, the value of flow <math>f</math> approach the value of the cut <math>(S,\bar{S})</math> defined above. By the above lemma, this will imply that the current flow <math>f</math> is maximum.

To prove this claim, we first observe that
:<math>\sum_{v:(s,v)}f_{sv}= \sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu}</math>.
This identity is implied by the flow conservation constraint, and holds for any <math>s</math>-<math>t</math> cut <math>(S,\bar{S})</math>.

We then claim that
*<math>f_{uv}=c_{uv}</math> for all <math>u\in S,v\not\in S, (u,v)\in E</math>; and
*<math>f_{vu}=0</math> for all <math>u\in S,v\not\in S, (v,u)\in E</math>.
If otherwise, then the augmenting path to <math>u</math> apending <math>uv</math> becomes a new augmenting path to <math>v</math>, which contradicts that <math>S</math> includes all vertices to which there exist augmenting paths.

Therefore,
:<math>\sum_{v:(s,v)}f_{sv}= \sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu} = \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>.
As discussed above, this proves the theorem.
}}

=== The max-flow min-cut theorem ===
{{Theorem|Max-Flow Min-Cut Theorem|
:In a flow network, the maximum value of any <math>s</math>-<math>t</math> flow equals the minimum value of any <math>s</math>-<math>t</math> cut.
}}

{{Proof|
Let <math>f</math> be a flow with maximum value, so there is no augmenting path.

Again, let <math>S=\{u\in V\mid \exists\text{an augmenting path to }u\}</math>. As proved above, <math>(S,\bar{S})</math> forms an <math>s</math>-<math>t</math> cut, and
:<math>\sum_{v:(s,v)}f_{sv}= \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>,
that is, the value of flow <math>f</math> equals the value of cut <math>(S,\bar{S})</math>.

Since we know that all <math>s</math>-<math>t</math> flows are not greater than any <math>s</math>-<math>t</math> cut, the value of flow <math>f</math> equals the minimum value of any <math>s</math>-<math>t</math> cut.
}}

{{Theorem|Flow Integrality Theorem|
:Let <math>(G,c,s,t)</math> be a flow network with integral capacity <math>c</math>. There exists an integral flow which is maximum.
}}
{{Proof|
Let <math>f</math> be an integral flow of maximum value. If there is an augmenting path, since both <math>c</math> and <math>f</math> are integral, a new flow can be constructed of value 1+the value of <math>f</math>, contradicting that <math>f</math> is maximum over all integral flows. Therefore, there is no augmenting path, which means that <math>f</math> is maximum over all flows, integral or not.
}}

== Unimodularity ==

=== Integer Programming===

=== Integrality of polytopes ===

=== Unimodularity and total unimodularity ===
{{Theorem|Definition (Unimodularity)|
:An <math>n\times n</math> integer matrix <math>A</math> is called '''unimodular''' if <math>\det(A)=\pm1</math>.
:An <math>m\times n</math> integer matrix <math>A</math> is called '''total unimodular''' if every square submatrix <math>B</math> of <math>A</math> has <math>\det(B)\in\{1,-1,0\}</math>, that is, every square, nonsingular submatrix of <math>A</math> is unimodular.
}}

{{Theorem|Theorem|
:Let <math>A</math> be an <math>m\times n</math> integer matrix.
:If <math>A</math> is totally unimodualr, then for any integer vector <math>\boldsymbol{b}\in\mathbb{Z}^n</math> the polyhedron <math>\{\boldsymbol{x}\in\mathbb{R}^n\mid A\boldsymbol{x}=\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}\}</math> is integral.
}}
{{Proof|
Let <math>B</math> be a basis of <math>A</math>, and let <math>\boldsymbol{b}'</math> be the corresponding coordinates in <math>\boldsymbol{b}</math>. A basic solution is formed by <math>B^{-1}\boldsymbol{b}'</math> and zeros. Since <math>A</math> is totally unimodular and <math>B</math> is a basis thus nonsingular, <math>\det(B)\in\{1,-1,0\}</math>. By [http://en.wikipedia.org/wiki/Cramer's_rule Cramer's rule], <math>B^{-1}</math> has integer entries, thus <math>B^{-1}\boldsymbol{b}'</math> is integral. Therefore, any basic solution of <math>A\boldsymbol{x}=\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}</math> is integral, which means the polyhedron <math>\{\boldsymbol{x}\in\mathbb{R}^n\mid A\boldsymbol{x}=\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}\}</math> is integral.
}}

{{Theorem|Theorem (Hoffman-Kruskal 1956)|
:Let <math>A</math> be an <math>m\times n</math> integer matrix.
:If <math>A</math> is totally unimodualr, then for any integer vector <math>\boldsymbol{b}\in\mathbb{Z}^n</math> the polyhedron <math>\{\boldsymbol{x}\in\mathbb{R}^n\mid A\boldsymbol{x}\ge\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}\}</math> is integral.
}}
{{Proof|
Let <math>A'=\begin{bmatrix}A & -I\end{bmatrix}</math>. We claim that <math>A'</math> is also totally unimodular. Any square submatrix <math>B</math> of <math>A</math> can be written in the following form after permutation:
:<math>B=\begin{bmatrix}
C & 0\\
D & I
\end{bmatrix}</math>
where <math>C</math> is a square submatrix of <math>A</math> and <math>I</math> is identity matrix. Therefore,
:<math>\det(B)=\det(C)\in\{1,-1,0\}</math>,
thus <math>A'</math> is totally unimodular.

Add slack variables to transform the constraints to the standard form <math>A'\boldsymbol{z}=\boldsymbol{b},\boldsymbol{z}\ge\boldsymbol{0}</math>. The polyhedron <math>\{\boldsymbol{x}\mid A\boldsymbol{x}\ge\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}\}</math> is integral if the polyhedron <math>\{\boldsymbol{z}\mid A'\boldsymbol{z}=\boldsymbol{b}, \boldsymbol{z}\ge \boldsymbol{0}\}</math> is integral, which is implied by the total unimodularity of <math>A'\,</math>.
}}

Combinatorics (Fall 2010)/Flow and matching

2010-12-26T07:04:57Z

172.21.5.190: /* Unimodularity and total unimodularity */

== Flow and Cut==

=== Flows ===
An instance of the maximum flow problem consists of:
* a directed graph <math>G(V,E)</math>;
* two distinguished vertices <math>s</math> (the '''source''') and <math>t</math> (the '''sink'''), where the in-degree of <math>s</math> and the out-degree of <math>t</math> are both 0;
* the '''capacity function''' <math>c:E\rightarrow\mathbb{R}^+</math> which associates each directed edge <math>(u,v)\in E</math> a nonnegative real number <math>c_{uv}</math> called the '''capacity''' of the edge.

The quadruple <math>(G,c,s,t)</math> is called a '''flow network'''.

A function <math>f:E\rightarrow\mathbb{R}^+</math> is called a '''flow''' (to be specific an '''<math>s</math>-<math>t</math> flow''') in the network <math>G(V,E)</math> if it satisfies:
* '''Capacity constraint:''' <math>f_{uv}\le c_{uv}</math> for all <math>(u,v)\in E</math>.
* '''Conservation constraint:''' <math>\sum_{u:(u,v)\in E}f_{uv}=\sum_{w:(v,w)\in E}f_{vw}</math> for all <math>v\in V\setminus\{s,t\}</math>.

The '''value''' of the flow <math>f</math> is <math>\sum_{v:(s,v)\in E}f_{sv}</math>.

Given a flow network, the maximum flow problem asks to find the flow of the maximum value.

The maximum flow problem can be described as the following linear program.
:<math>
\begin{align}
\text{maximize} \quad& \sum_{v:(s,v)\in E}f_{sv}\\
\begin{align}
\text{subject to} \\
\\
\\
\\
\end{align}
\quad &
\begin{align} f_{uv}&\le c_{uv} &\quad& \forall (u,v)\in E\\
\sum_{u:(u,v)\in E}f_{uv}-\sum_{w:(v,w)\in E}f_{vw} &=0 &\quad& \forall v\in V\setminus\{s,t\}\\
f_{uv}&\ge 0 &\quad& \forall (u,v)\in E
\end{align}
\end{align}
</math>

=== Cuts ===
{{Theorem|Definition|
:Let <math>(G(V,E),c,s,t)</math> be a flow network. Let <math>S\subset V</math>. We call <math>(S,\bar{S})</math> an '''<math>s</math>-<math>t</math> cut''' if <math>s\in S</math> and <math>t\not\in S</math>.
:The '''value''' of the cut (also called the '''capacity''' of the cut) is defined as <math>\sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>.
}}

A fundamental fact in the theory of flow is that cuts always upper bound flows.

{{Theorem|Lemma|
:Let <math>(G(V,E),c,s,t)</math> be a flow network. Let <math>f</math> be an arbitrary flow in <math>G</math>, and let <math>(S,\bar{S})</math> be an arbitrary <math>s</math>-<math>t</math> cut. Then
::<math>\sum_{v:(s,v)}f_{sv}\le \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>,
:that is, the value of any flow is no greater than the value of any cut.
}}
{{Proof|By the definition of <math>s</math>-<math>t</math> cut, <math>s\in S</math> and <math>t\not\in S</math>.

Due to the conservation of flow,
:<math>\sum_{u\in S}\left(\sum_{v:(u,v)\in E}f_{uv}-\sum_{v:(v,u)\in E}f_{vu}\right)=\sum_{v:(s,v)\in E}f_{sv}+\sum_{u\in S\setminus\{s\}}\left(\sum_{v:(u,v)\in E}f_{uv}-\sum_{v:(v,u)\in E}f_{vu}\right)=\sum_{v:(s,v)\in E}f_{sv}\,.</math>
On the other hand, summing flow over edges,
:<math>\sum_{v\in S}\left(\sum_{u:(u,v)\in E}f_{uv}-\sum_{u:(v,u)\in E}f_{vu}\right)=\sum_{u\in S,v\in S\atop (u,v)\in E}\left(f_{uv}-f_{uv}\right)+\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu}=\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu}\,.</math>
Therefore,
:<math>\sum_{v:(s,v)\in E}f_{sv}=\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu}\le\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}\le \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}\,,</math>
}}

=== Augmenting paths ===
{{Theorem|Definition (Augmenting path)|
:Let <math>f</math> be a flow in <math>G</math>. An '''augmenting path to <math>u_k</math>''' is a sequence of distinct vertices <math>P=(u_0,u_1,\cdots, u_k)</math>, such that
:* <math>u_0=s\,</math>;
:and each pair of consecutive vertices <math>u_{i}u_{i+1}\,</math> in <math>P</math> corresponds to either a '''forward edge''' <math>(u_{i},u_{i+1})\in E</math> or a '''reverse edge''' <math>(u_{i+1},u_{i})\in E</math>, and
:* <math>f(u_i,u_{i+1})<c(u_i,u_{i+1})\,</math> when <math>u_{i}u_{i+1}\,</math> corresponds to a forward edge <math>(u_{i},u_{i+1})\in E</math>, and
:* <math>f(u_{i+1},u_i)>0\,</math> when <math>u_{i}u_{i+1}\,</math> corresponds to a reverse edge <math>(u_{i+1},u_{i})\in E</math>.
:If <math>u_k=t\,</math>, we simply call <math>P</math> an '''augmenting path'''.
}}

Let <math>f</math> be a flow in <math>G</math>. Suppose there is an augmenting path <math>P=u_0u_1\cdots u_k</math>, where <math>u_0=s</math> and <math>u_k=t</math>. Let <math>\epsilon>0</math> be a positive constant satisfying
*<math>\epsilon \le c(u_{i},u_{i+1})-f(u_i,u_{i+1})</math> for all forward edges <math>(u_{i},u_{i+1})\in E</math> in <math>P</math>;
*<math>\epsilon \le f(u_{i+1},u_i)</math> for all reverse edges <math>(u_{i+1},u_i)\in E</math> in <math>P</math>.
Due to the definition of augmenting path, we can always find such a positive <math>\epsilon</math>.

Increase <math>f(u_i,u_{i+1})</math> by <math>\epsilon</math> for all forward edges <math>(u_{i},u_{i+1})\in E</math> in <math>P</math> and decrease <math>f(u_{i+1},u_i)</math> by <math>\epsilon</math> for all reverse edges <math>(u_{i+1},u_i)\in E</math> in <math>P</math>. Denote the modified flow by <math>f'</math>. It can be verified that <math>f'</math> satisfies the capacity constraint and conservation constraint thus is still a valid flow. On the other hand, the value of the new flow <math>f'</math>
:<math>\sum_{v:(s,v)\in E}f_{sv}'=\epsilon+\sum_{v:(s,v)\in E}f_{sv}>\sum_{v:(s,v)\in E}f_{sv}</math>.
Therefore, the value of the flow can be "augmented" by adjusting the flow on the augmenting path. This immediately implies that if a flow is maximum, then there is no augmenting path. Surprisingly, the converse is also true, thus maximum flows are "characterized" by augmenting paths.

{{Theorem|Lemma|
:A flow <math>f</math> is maximum if and only if there are no augmenting paths.
}}
{{Proof|We have already proved the "only if" direction above. Now we prove the "if" direction.

Let <math>S=\{u\in V\mid \exists\text{an augmenting path to }u\}</math>. Clearly <math>s\in S</math>, and since there is no augmenting path <math>t\not\in S</math>. Therefore, <math>(S,\bar{S})</math> defines an <math>s</math>-<math>t</math> cut.

We claim that
:<math>\sum_{v:(s,v)}f_{sv}= \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>,
that is, the value of flow <math>f</math> approach the value of the cut <math>(S,\bar{S})</math> defined above. By the above lemma, this will imply that the current flow <math>f</math> is maximum.

To prove this claim, we first observe that
:<math>\sum_{v:(s,v)}f_{sv}= \sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu}</math>.
This identity is implied by the flow conservation constraint, and holds for any <math>s</math>-<math>t</math> cut <math>(S,\bar{S})</math>.

We then claim that
*<math>f_{uv}=c_{uv}</math> for all <math>u\in S,v\not\in S, (u,v)\in E</math>; and
*<math>f_{vu}=0</math> for all <math>u\in S,v\not\in S, (v,u)\in E</math>.
If otherwise, then the augmenting path to <math>u</math> apending <math>uv</math> becomes a new augmenting path to <math>v</math>, which contradicts that <math>S</math> includes all vertices to which there exist augmenting paths.

Therefore,
:<math>\sum_{v:(s,v)}f_{sv}= \sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu} = \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>.
As discussed above, this proves the theorem.
}}

=== The max-flow min-cut theorem ===
{{Theorem|Max-Flow Min-Cut Theorem|
:In a flow network, the maximum value of any <math>s</math>-<math>t</math> flow equals the minimum value of any <math>s</math>-<math>t</math> cut.
}}

{{Proof|
Let <math>f</math> be a flow with maximum value, so there is no augmenting path.

Again, let <math>S=\{u\in V\mid \exists\text{an augmenting path to }u\}</math>. As proved above, <math>(S,\bar{S})</math> forms an <math>s</math>-<math>t</math> cut, and
:<math>\sum_{v:(s,v)}f_{sv}= \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>,
that is, the value of flow <math>f</math> equals the value of cut <math>(S,\bar{S})</math>.

Since we know that all <math>s</math>-<math>t</math> flows are not greater than any <math>s</math>-<math>t</math> cut, the value of flow <math>f</math> equals the minimum value of any <math>s</math>-<math>t</math> cut.
}}

{{Theorem|Flow Integrality Theorem|
:Let <math>(G,c,s,t)</math> be a flow network with integral capacity <math>c</math>. There exists an integral flow which is maximum.
}}
{{Proof|
Let <math>f</math> be an integral flow of maximum value. If there is an augmenting path, since both <math>c</math> and <math>f</math> are integral, a new flow can be constructed of value 1+the value of <math>f</math>, contradicting that <math>f</math> is maximum over all integral flows. Therefore, there is no augmenting path, which means that <math>f</math> is maximum over all flows, integral or not.
}}

== Unimodularity ==

=== Integer Programmings===

=== Integrality of polytopes ===

=== Unimodularity and total unimodularity ===
{{Theorem|Definition (Unimodularity)|
:An <math>n\times n</math> integer matrix <math>A</math> is called '''unimodular''' if <math>\det(A)=\pm1</math>.
:An <math>m\times n</math> integer matrix <math>A</math> is called '''total unimodular''' if every square submatrix <math>B</math> of <math>A</math> has <math>\det(B)\in\{1,-1,0\}</math>, that is, every square, nonsingular submatrix of <math>A</math> is unimodular.
}}

{{Theorem|Theorem|
:Let <math>A</math> be an <math>m\times n</math> integer matrix.
:If <math>A</math> is totally unimodualr, then for any integer vector <math>\boldsymbol{b}\in\mathbb{Z}^n</math> the polyhedron <math>\{\boldsymbol{x}\in\mathbb{R}^n\mid A\boldsymbol{x}=\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}\}</math> is integral.
}}
{{Proof|
Let <math>B</math> be a basis of <math>A</math>, and let <math>\boldsymbol{b}'</math> be the corresponding coordinates in <math>\boldsymbol{b}</math>. A basic solution is formed by <math>B^{-1}\boldsymbol{b}'</math> and zeros. Since <math>A</math> is totally unimodular and <math>B</math> is a basis thus nonsingular, <math>\det(B)\in\{1,-1,0\}</math>. By [http://en.wikipedia.org/wiki/Cramer's_rule Cramer's rule], <math>B^{-1}</math> has integer entries, thus <math>B^{-1}\boldsymbol{b}'</math> is integral. Therefore, any basic solution of <math>A\boldsymbol{x}=\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}</math> is integral, which means the polyhedron <math>\{\boldsymbol{x}\in\mathbb{R}^n\mid A\boldsymbol{x}=\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}\}</math> is integral.
}}

{{Theorem|Theorem (Hoffman-Kruskal 1956)|
:Let <math>A</math> be an <math>m\times n</math> integer matrix.
:If <math>A</math> is totally unimodualr, then for any integer vector <math>\boldsymbol{b}\in\mathbb{Z}^n</math> the polyhedron <math>\{\boldsymbol{x}\in\mathbb{R}^n\mid A\boldsymbol{x}\ge\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}\}</math> is integral.
}}
{{Proof|
Let <math>A'=\begin{bmatrix}A & -I\end{bmatrix}</math>. We claim that <math>A'</math> is also totally unimodular. Any square submatrix <math>B</math> of <math>A</math> can be written in the following form after permutation:
:<math>B=\begin{bmatrix}
C & 0\\
D & I
\end{bmatrix}</math>
where <math>C</math> is a square submatrix of <math>A</math> and <math>I</math> is identity matrix. Therefore,
:<math>\det(B)=\det(C)\in\{1,-1,0\}</math>,
thus <math>A'</math> is totally unimodular.

Add slack variables to transform the constraints to the standard form <math>A'\boldsymbol{z}=\boldsymbol{b},\boldsymbol{z}\ge\boldsymbol{0}</math>. The polyhedron <math>\{\boldsymbol{x}\mid A\boldsymbol{x}\ge\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}\}</math> is integral if the polyhedron <math>\{\boldsymbol{z}\mid A'\boldsymbol{z}=\boldsymbol{b}, \boldsymbol{z}\ge \boldsymbol{0}\}</math> is integral, which is implied by the total unimodularity of <math>A'\,</math>.
}}

Randomized Algorithms (Spring 2010)/More on Chernoff bounds

2010-02-25T14:56:37Z

172.21.5.128: /* A two-phase randomized routing algorithm */

== Permutation Routing ==
The problem raises from parallel computing. Consider that we have <math>N</math> processors, connected by a communication network. The processors communicate with each other by sending and receiving '''packets''' through the network. We consider the following packet routing problem:
* Every processor is sending a packet to a unique destination. Therefore for <math>[N]</math> the set of processors, the destinations are given by a '''permutation''' <math>\pi</math> of <math>[N]</math>, such that for every processor <math>i\in[N]</math>, the processor <math>i</math> is sending a packet to processor <math>\pi(i)</math>.
* The communication is '''synchronized''', such that for each '''round''', every link (an edge of the graph) can forward at most one packet.

With a complete graph as the network. For any permutation <math>\pi</math> of <math>[N]</math>, all packets can be routed to their destinations in parallel with one round of communication. However, such an ideal connectivity is usually not available in reality, either because they are too expensive, or because they are physically impossible. We are interested in the case the graph is '''sparse''', such that the number of edges is significantly smaller than the complete graph, yet the distance between any pair of vertices is small, so that the packets can be efficiently routed between pairs of vertices.

=== Routing on a hypercube ===
A [http://en.wikipedia.org/wiki/Hypercube hypercube] (sometimes called a Boolean cube, a Hamming cube, or just cube) is defined over <math>N</math> nodes, for <math>N</math> a power of 2. We assume that <math>N=2^d</math>. A hypercube of <math>d</math> dimensions, or a <math>d</math>-cube, is an undirected graph with the vertex set <math>\{0,1\}^d</math>, such that for any <math>u,v\in\{0,1\}^d</math>, <math>u</math> and <math>v</math> are adjacent if and only if <math>h(u,v)=1</math>, where <math>h(u,v)</math> is the [http://en.wikipedia.org/wiki/Hamming_distance Hamming distance] between <math>u</math> and <math>v</math>.

A <math>d</math>-cube is a <math>d</math>-degree regular graph over <math>N=2^d</math> vertices. For any pair <math>(u,v)</math> of vertices, the distance between <math>u</math> and <math>v</math> is at most <math>d</math>. (How do we know this? Since it takes at most <math>d</math> steps to fix any binary string of length <math>d</math> bit-by-bit to any other.) This directly gives us the following very natural routing algorithm.

{|border="1"
|'''Bit-Fixing Routing Algorithm:'''
|-
|For each packet:
#Let <math>u, v\in\{0,1\}^d</math> be the origin and destination of the packet respectively.
#For <math>i=1</math> to <math>d</math>, do:
::if <math>u_i\neq v_i</math> then traverse the edge <math>(v_1,\ldots,v_{i-1},u_i,\ldots,u_d)\rightarrow (v_1,\ldots,v_{i-1},v_i,u_{i+1}\ldots,u_d)</math>.
|}

;Oblivious routing algorithms
:This algorithm is blessed with a desirable property: it depends only on the origin, the destination, and the current node. We call the algorithms with this property '''oblivious''' routing algorithms. Compared to the routing algorithms which are adaptive to the path that the packet traversed, oblivious routing is more simple thus can be implemented by smaller routing table (or simple devices called '''switches''').

;Queuing policies
:When routing <math>N</math> packets in parallel, it is possible that more than one packets want to use the same edge at the same time. We assume that a queue is associated to each edge, such that the packets to be delivered through an edge are put into the queue associated with the edge. With some '''queuing policy''' (e.g. FIFO, or furthest to do), the queued packets are delivered through the edge by at most one packet per each round.

For the bit-fixing routing algorithm defined above, regardless of the queuing policy, there always exists a bad permutation <math>\pi</math> which specifies the destinations, such that it takes <math>\Omega(\sqrt{N})</math> steps by the bit-fixing algorithm to route all <math>N</math> packets to their destinations. (You can prove this by yourself.)

This is pretty bad, because we expect that the routing time is comparable to the diameter of the network, which is only <math>d=\log N</math> for hypercube.

The lower bound actually applies generally for any deterministic oblivious routing algorithms:

{|border="1"
|'''Theorem [Kaklamanis, Krizanc, Tsantilas, 1991]'''
:In any <math>N</math>-node communication network with maximum degree <math>d</math>, any deterministic oblivious algorithm for routing an arbitrary permutation requires <math>\Omega(\sqrt{N}/d)</math> parallel communication steps in the worst case.
|}

The proof of the lower bound is rather technical and complicated. However, the intuition is quite clear: for any oblivious rule for routing, there always exists a permutation which causes a very high '''congestion''', such that many packets have to be delivered through the same edge, thus no matter what queuing policy is used, the maximum delay must be very high.

=== A two-phase randomized routing algorithm ===
It is somehow surprising that routing the packet first to some completely irrelevant "relay" actually improves the overall performance.

{|border="1"
|'''Two-Phase Routing Algorithm:'''
|-
|For each packet:
'''Phase I:''' Route the packet to a random destination using the bit-fixing algorithm.

'''Phase II:''' Route the packet from the random location to its final destination using the bit-fixing algorithm.
|}

== Johnson-Lindenstrauss Theorem ==

Randomized Algorithms (Spring 2010)/More on Chernoff bounds

2010-02-25T14:50:34Z

172.21.5.128: /* A two-phase randomized routing algorithm */

== Permutation Routing ==
The problem raises from parallel computing. Consider that we have <math>N</math> processors, connected by a communication network. The processors communicate with each other by sending and receiving '''packets''' through the network. We consider the following packet routing problem:
* Every processor is sending a packet to a unique destination. Therefore for <math>[N]</math> the set of processors, the destinations are given by a '''permutation''' <math>\pi</math> of <math>[N]</math>, such that for every processor <math>i\in[N]</math>, the processor <math>i</math> is sending a packet to processor <math>\pi(i)</math>.
* The communication is '''synchronized''', such that for each '''round''', every link (an edge of the graph) can forward at most one packet.

With a complete graph as the network. For any permutation <math>\pi</math> of <math>[N]</math>, all packets can be routed to their destinations in parallel with one round of communication. However, such an ideal connectivity is usually not available in reality, either because they are too expensive, or because they are physically impossible. We are interested in the case the graph is '''sparse''', such that the number of edges is significantly smaller than the complete graph, yet the distance between any pair of vertices is small, so that the packets can be efficiently routed between pairs of vertices.

=== Routing on a hypercube ===
A [http://en.wikipedia.org/wiki/Hypercube hypercube] (sometimes called a Boolean cube, a Hamming cube, or just cube) is defined over <math>N</math> nodes, for <math>N</math> a power of 2. We assume that <math>N=2^d</math>. A hypercube of <math>d</math> dimensions, or a <math>d</math>-cube, is an undirected graph with the vertex set <math>\{0,1\}^d</math>, such that for any <math>u,v\in\{0,1\}^d</math>, <math>u</math> and <math>v</math> are adjacent if and only if <math>h(u,v)=1</math>, where <math>h(u,v)</math> is the [http://en.wikipedia.org/wiki/Hamming_distance Hamming distance] between <math>u</math> and <math>v</math>.

A <math>d</math>-cube is a <math>d</math>-degree regular graph over <math>N=2^d</math> vertices. For any pair <math>(u,v)</math> of vertices, the distance between <math>u</math> and <math>v</math> is at most <math>d</math>. (How do we know this? Since it takes at most <math>d</math> steps to fix any binary string of length <math>d</math> bit-by-bit to any other.) This directly gives us the following very natural routing algorithm.

{|border="1"
|'''Bit-Fixing Routing Algorithm:'''
|-
|For each packet:
#Let <math>u, v\in\{0,1\}^d</math> be the origin and destination of the packet respectively.
#For <math>i=1</math> to <math>d</math>, do:
::if <math>u_i\neq v_i</math> then traverse the edge <math>(v_1,\ldots,v_{i-1},u_i,\ldots,u_d)\rightarrow (v_1,\ldots,v_{i-1},v_i,u_{i+1}\ldots,u_d)</math>.
|}

;Oblivious routing algorithms
:This algorithm is blessed with a desirable property: it depends only on the origin, the destination, and the current node. We call the algorithms with this property '''oblivious''' routing algorithms. Compared to the routing algorithms which are adaptive to the path that the packet traversed, oblivious routing is more simple thus can be implemented by smaller routing table (or simple devices called '''switches''').

;Queuing policies
:When routing <math>N</math> packets in parallel, it is possible that more than one packets want to use the same edge at the same time. We assume that a queue is associated to each edge, such that the packets to be delivered through an edge are put into the queue associated with the edge. With some '''queuing policy''' (e.g. FIFO, or furthest to do), the queued packets are delivered through the edge by at most one packet per each round.

For the bit-fixing routing algorithm defined above, regardless of the queuing policy, there always exists a bad permutation <math>\pi</math> which specifies the destinations, such that it takes <math>\Omega(\sqrt{N})</math> steps by the bit-fixing algorithm to route all <math>N</math> packets to their destinations. (You can prove this by yourself.)

This is pretty bad, because we expect that the routing time is comparable to the diameter of the network, which is only <math>d=\log N</math> for hypercube.

The lower bound actually applies generally for any deterministic oblivious routing algorithms:

{|border="1"
|'''Theorem [Kaklamanis, Krizanc, Tsantilas, 1991]'''
:In any <math>N</math>-node communication network with maximum degree <math>d</math>, any deterministic oblivious algorithm for routing an arbitrary permutation requires <math>\Omega(\sqrt{N}/d)</math> parallel communication steps in the worst case.
|}

The proof of the lower bound is rather technical and complicated. However, the intuition is quite clear: for any oblivious rule for routing, there always exists a permutation which causes a very high '''congestion''', such that many packets have to be delivered through the same edge, thus no matter what queuing policy is used, the maximum delay must be very high.

=== A two-phase randomized routing algorithm ===

{|border="1"
|'''Two-Phase Routing Algorithm:'''
|-
|For each packet:
'''Phase I:''' Route the packet to a random destination using the bit-fixing algorithm.

'''Phase II:''' Route the packet from the random location to its final destination using the bit-fixing algorithm.
|}

== Johnson-Lindenstrauss Theorem ==

Randomized Algorithms (Spring 2010)/More on Chernoff bounds

2010-02-25T14:48:06Z

172.21.5.128: /* A two-phase randomized routing algorithm */

== Permutation Routing ==
The problem raises from parallel computing. Consider that we have <math>N</math> processors, connected by a communication network. The processors communicate with each other by sending and receiving '''packets''' through the network. We consider the following packet routing problem:
* Every processor is sending a packet to a unique destination. Therefore for <math>[N]</math> the set of processors, the destinations are given by a '''permutation''' <math>\pi</math> of <math>[N]</math>, such that for every processor <math>i\in[N]</math>, the processor <math>i</math> is sending a packet to processor <math>\pi(i)</math>.
* The communication is '''synchronized''', such that for each '''round''', every link (an edge of the graph) can forward at most one packet.

With a complete graph as the network. For any permutation <math>\pi</math> of <math>[N]</math>, all packets can be routed to their destinations in parallel with one round of communication. However, such an ideal connectivity is usually not available in reality, either because they are too expensive, or because they are physically impossible. We are interested in the case the graph is '''sparse''', such that the number of edges is significantly smaller than the complete graph, yet the distance between any pair of vertices is small, so that the packets can be efficiently routed between pairs of vertices.

=== Routing on a hypercube ===
A [http://en.wikipedia.org/wiki/Hypercube hypercube] (sometimes called a Boolean cube, a Hamming cube, or just cube) is defined over <math>N</math> nodes, for <math>N</math> a power of 2. We assume that <math>N=2^d</math>. A hypercube of <math>d</math> dimensions, or a <math>d</math>-cube, is an undirected graph with the vertex set <math>\{0,1\}^d</math>, such that for any <math>u,v\in\{0,1\}^d</math>, <math>u</math> and <math>v</math> are adjacent if and only if <math>h(u,v)=1</math>, where <math>h(u,v)</math> is the [http://en.wikipedia.org/wiki/Hamming_distance Hamming distance] between <math>u</math> and <math>v</math>.

A <math>d</math>-cube is a <math>d</math>-degree regular graph over <math>N=2^d</math> vertices. For any pair <math>(u,v)</math> of vertices, the distance between <math>u</math> and <math>v</math> is at most <math>d</math>. (How do we know this? Since it takes at most <math>d</math> steps to fix any binary string of length <math>d</math> bit-by-bit to any other.) This directly gives us the following very natural routing algorithm.

{|border="1"
|'''Bit-Fixing Routing Algorithm:'''
|-
|For each packet:
#Let <math>u, v\in\{0,1\}^d</math> be the origin and destination of the packet respectively.
#For <math>i=1</math> to <math>d</math>, do:
::if <math>u_i\neq v_i</math> then traverse the edge <math>(v_1,\ldots,v_{i-1},u_i,\ldots,u_d)\rightarrow (v_1,\ldots,v_{i-1},v_i,u_{i+1}\ldots,u_d)</math>.
|}

;Oblivious routing algorithms
:This algorithm is blessed with a desirable property: it depends only on the origin, the destination, and the current node. We call the algorithms with this property '''oblivious''' routing algorithms. Compared to the routing algorithms which are adaptive to the path that the packet traversed, oblivious routing is more simple thus can be implemented by smaller routing table (or simple devices called '''switches''').

;Queuing policies
:When routing <math>N</math> packets in parallel, it is possible that more than one packets want to use the same edge at the same time. We assume that a queue is associated to each edge, such that the packets to be delivered through an edge are put into the queue associated with the edge. With some '''queuing policy''' (e.g. FIFO, or furthest to do), the queued packets are delivered through the edge by at most one packet per each round.

For the bit-fixing routing algorithm defined above, regardless of the queuing policy, there always exists a bad permutation <math>\pi</math> which specifies the destinations, such that it takes <math>\Omega(\sqrt{N})</math> steps by the bit-fixing algorithm to route all <math>N</math> packets to their destinations. (You can prove this by yourself.)

This is pretty bad, because we expect that the routing time is comparable to the diameter of the network, which is only <math>d=\log N</math> for hypercube.

The lower bound actually applies generally for any deterministic oblivious routing algorithms:

{|border="1"
|'''Theorem [Kaklamanis, Krizanc, Tsantilas, 1991]'''
:In any <math>N</math>-node communication network with maximum degree <math>d</math>, any deterministic oblivious algorithm for routing an arbitrary permutation requires <math>\Omega(\sqrt{N}/d)</math> parallel communication steps in the worst case.
|}

The proof of the lower bound is rather technical and complicated. However, the intuition is quite clear: for any oblivious rule for routing, there always exists a permutation which causes a very high '''congestion''', such that many packets have to be delivered through the same edge, thus no matter what queuing policy is used, the maximum delay must be very high.

=== A two-phase randomized routing algorithm ===

{|border="1"
|'''Two-Phase Routing Algorithm:'''
|-
|'''Phase I:''' Route the packet to a random destination using the bit-fixing algorithm.
'''Phase II:''' Route the packet from the random location to its final destination using the bit-fixing algorithm.
|}

== Johnson-Lindenstrauss Theorem ==

Randomized Algorithms (Spring 2010)/More on Chernoff bounds

2010-02-25T14:47:26Z

172.21.5.128: /* A two-phase randomized routing algorithm */

== Permutation Routing ==
The problem raises from parallel computing. Consider that we have <math>N</math> processors, connected by a communication network. The processors communicate with each other by sending and receiving '''packets''' through the network. We consider the following packet routing problem:
* Every processor is sending a packet to a unique destination. Therefore for <math>[N]</math> the set of processors, the destinations are given by a '''permutation''' <math>\pi</math> of <math>[N]</math>, such that for every processor <math>i\in[N]</math>, the processor <math>i</math> is sending a packet to processor <math>\pi(i)</math>.
* The communication is '''synchronized''', such that for each '''round''', every link (an edge of the graph) can forward at most one packet.

With a complete graph as the network. For any permutation <math>\pi</math> of <math>[N]</math>, all packets can be routed to their destinations in parallel with one round of communication. However, such an ideal connectivity is usually not available in reality, either because they are too expensive, or because they are physically impossible. We are interested in the case the graph is '''sparse''', such that the number of edges is significantly smaller than the complete graph, yet the distance between any pair of vertices is small, so that the packets can be efficiently routed between pairs of vertices.

=== Routing on a hypercube ===
A [http://en.wikipedia.org/wiki/Hypercube hypercube] (sometimes called a Boolean cube, a Hamming cube, or just cube) is defined over <math>N</math> nodes, for <math>N</math> a power of 2. We assume that <math>N=2^d</math>. A hypercube of <math>d</math> dimensions, or a <math>d</math>-cube, is an undirected graph with the vertex set <math>\{0,1\}^d</math>, such that for any <math>u,v\in\{0,1\}^d</math>, <math>u</math> and <math>v</math> are adjacent if and only if <math>h(u,v)=1</math>, where <math>h(u,v)</math> is the [http://en.wikipedia.org/wiki/Hamming_distance Hamming distance] between <math>u</math> and <math>v</math>.

A <math>d</math>-cube is a <math>d</math>-degree regular graph over <math>N=2^d</math> vertices. For any pair <math>(u,v)</math> of vertices, the distance between <math>u</math> and <math>v</math> is at most <math>d</math>. (How do we know this? Since it takes at most <math>d</math> steps to fix any binary string of length <math>d</math> bit-by-bit to any other.) This directly gives us the following very natural routing algorithm.

{|border="1"
|'''Bit-Fixing Routing Algorithm:'''
|-
|For each packet:
#Let <math>u, v\in\{0,1\}^d</math> be the origin and destination of the packet respectively.
#For <math>i=1</math> to <math>d</math>, do:
::if <math>u_i\neq v_i</math> then traverse the edge <math>(v_1,\ldots,v_{i-1},u_i,\ldots,u_d)\rightarrow (v_1,\ldots,v_{i-1},v_i,u_{i+1}\ldots,u_d)</math>.
|}

;Oblivious routing algorithms
:This algorithm is blessed with a desirable property: it depends only on the origin, the destination, and the current node. We call the algorithms with this property '''oblivious''' routing algorithms. Compared to the routing algorithms which are adaptive to the path that the packet traversed, oblivious routing is more simple thus can be implemented by smaller routing table (or simple devices called '''switches''').

;Queuing policies
:When routing <math>N</math> packets in parallel, it is possible that more than one packets want to use the same edge at the same time. We assume that a queue is associated to each edge, such that the packets to be delivered through an edge are put into the queue associated with the edge. With some '''queuing policy''' (e.g. FIFO, or furthest to do), the queued packets are delivered through the edge by at most one packet per each round.

For the bit-fixing routing algorithm defined above, regardless of the queuing policy, there always exists a bad permutation <math>\pi</math> which specifies the destinations, such that it takes <math>\Omega(\sqrt{N})</math> steps by the bit-fixing algorithm to route all <math>N</math> packets to their destinations. (You can prove this by yourself.)

This is pretty bad, because we expect that the routing time is comparable to the diameter of the network, which is only <math>d=\log N</math> for hypercube.

The lower bound actually applies generally for any deterministic oblivious routing algorithms:

{|border="1"
|'''Theorem [Kaklamanis, Krizanc, Tsantilas, 1991]'''
:In any <math>N</math>-node communication network with maximum degree <math>d</math>, any deterministic oblivious algorithm for routing an arbitrary permutation requires <math>\Omega(\sqrt{N}/d)</math> parallel communication steps in the worst case.
|}

The proof of the lower bound is rather technical and complicated. However, the intuition is quite clear: for any oblivious rule for routing, there always exists a permutation which causes a very high '''congestion''', such that many packets have to be delivered through the same edge, thus no matter what queuing policy is used, the maximum delay must be very high.

=== A two-phase randomized routing algorithm ===

{|border="1"
|'''Two-Phase Routing Algorithm:'''
|-
|'''Phase I:''' Route the packet to a uniformly random destination using the bit-fixing algorithm.
'''Phase II:''' Route the packet from the random location to its final destination using the bit-fixing algorithm.
|}

== Johnson-Lindenstrauss Theorem ==

Randomized Algorithms (Spring 2010)/More on Chernoff bounds

2010-02-25T14:40:12Z

172.21.5.128: /* Routing on a hypercube */

Randomized Algorithms (Spring 2010)/More on Chernoff bounds

2010-02-25T14:38:57Z

172.21.5.128: /* Routing on a hypercube */

Randomized Algorithms (Spring 2010)/More on Chernoff bounds

2010-02-25T14:32:38Z

172.21.5.128: /* Permutation Routing */

== Permutation Routing ==
The problem raises from parallel computing. Consider that we have <math>N</math> processors, connected by a communication network. The processors communicate with each other by sending and receiving '''packets''' through the network. We consider the following packet routing problem:
* Every processor is sending a packet to a unique destination. Therefore for <math>[N]</math> the set of processors, the destinations are given by a '''permutation''' <math>\pi</math> of <math>[N]</math>, such that for every processor <math>i\in[N]</math>, the processor <math>i</math> is sending a packet to processor <math>\pi(i)</math>.
* The communication is '''synchronized''', such that for each '''round''', every link (an edge of the graph) can forward at most one packet.

With a complete graph as the network. For any permutation <math>\pi</math> of <math>[N]</math>, all packets can be routed to their destinations in parallel with one round of communication. However, such an ideal connectivity is usually not available in reality, either because they are too expensive, or because they are physically impossible. We are interested in the case the graph is '''sparse''', such that the number of edges is significantly smaller than the complete graph, yet the distance between any pair of vertices is small, so that the packets can be efficiently routed between pairs of vertices.

=== Routing on a hypercube ===
A [http://en.wikipedia.org/wiki/Hypercube hypercube] (sometimes called a Boolean cube, a Hamming cube, or just cube) is defined over <math>N</math> nodes, for <math>N</math> a power of 2. We assume that <math>N=2^d</math>. A hypercube of <math>d</math> dimensions, or a <math>d</math>-cube, is an undirected graph with the vertex set <math>\{0,1\}^d</math>, such that for any <math>u,v\in\{0,1\}^d</math>, <math>u</math> and <math>v</math> are adjacent if and only if <math>h(u,v)=1</math>, where <math>h(u,v)</math> is the [http://en.wikipedia.org/wiki/Hamming_distance Hamming distance] between <math>u</math> and <math>v</math>.

A <math>d</math>-cube is a <math>d</math>-degree regular graph over <math>N=2^d</math> vertices. For any pair <math>(u,v)</math> of vertices, the distance between <math>u</math> and <math>v</math> is at most <math>d</math>. (How do we know this? Since it takes at most <math>d</math> steps to fix any binary string of length <math>d</math> bit-by-bit to any other.) This directly gives us the following very natural routing algorithm.

{|border="1"
|'''Bit-Fixing Routing Algorithm:'''
|-
|For each packet:
#Let <math>u, v\in\{0,1\}^d</math> be the origin and destination of the packet respectively.
#For <math>i=1</math> to <math>d</math>, do:
::if <math>u_i\neq v_i</math> then traverse the edge <math>(v_1,\ldots,v_{i-1},u_i,\ldots,u_d)\rightarrow (v_1,\ldots,v_{i-1},v_i,u_{i+1}\ldots,u_d)</math>.
|}

;Oblivious routing algorithms
:This algorithm is blessed with a desirable property: it depends only on the origin, the destination, and the current node. We call the algorithms with this property '''oblivious''' routing algorithms. Compared to the routing algorithms which are adaptive to the path that the packet traversed, oblivious routing is more simple thus can be implemented by smaller routing table (or simple devices called '''switches''').

;Queuing policies
:When routing <math>N</math> packets in parallel, it is possible that more than one packets want to use the same edge at the same time. We assume that a queue is associated to each edge, such that the packets to be delivered through an edge are put into the queue associated with the edge. With some '''queuing policy''' (e.g. FIFO, or furthest to do), the queued packets are delivered through the edge by at most one packet per each round.

For the bit-fixing routing algorithm defined above, regardless of the queuing policy, there always exists a bad permutation <math>\pi</math> which specifies the destinations, such that it takes <math>\Omega(\sqrt{N})</math> steps by the bit-fixing algorithm to route all <math>N</math> packets to their destinations. (You can prove this by yourself.)

The lower bound actually applies generally for any deterministic oblivious routing algorithms:

{|border="1"
|'''Theorem [Kaklamanis, Krizanc, Tsantilas, 1991]'''
:In any <math>N</math>-node communication network with maximum degree <math>d</math>, any deterministic oblivious algorithm for routing an arbitrary permutation requires <math>\Omega(\sqrt{N}/d)</math> parallel communication steps in the worst case.
|}

This is pretty bad, because we expect that the routing time is comparable to the diameter of the network, which is only <math>d=\log N</math> for hypercube.

== Johnson-Lindenstrauss Theorem ==