You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 

140 lines
4.7 KiB

\documentclass{article}
\usepackage{bstr}
\fancyhead[L]{MA4701 - Optimización Combinatorial}
\fancyhead[R]{Primavera 2013}
\fancyfoot[C]{}
\title{Auxiliar 12}
\author{}
\date{}
\begin{document}
\maketitle
\thispagestyle{fancy}
\subsection*{P1}
Como $g_t(S) = f(S) - t|S|$, $f$ es submodular simétrica y $|\cdot|$ es
modular, entonces podemos minimizar $g_t$ en $=(|V|^3)$ (por un problema
controlable).
Sean
\begin{align*}
s^* &= \min_{\varnothing\subsetneq S\subsetneq V} \frac{f(S)}{|S|}\\
S^* &= \argmin_{\varnothing\subsetneq S\subsetneq V} \frac{f(S)}{|S|}
\end{align*}
Tenemos que
\[g_{s^*}(S) = f(S)-s^*|S| geq |S| geq 0 \ \forall \varnothing\subsetneq
S\subsetneq V\]
Además,
\[g_{s^*}(S^*) = f(S^*) - s^*|S^*| = 0\]
Por lo que $\min g_{s^*}(S) = 0$. Además, si $t < s^*$,
\[g_t(S) = f(S) - t(S) > f(S) - s^*|S| = g_{s^*}(S) \geq 0\]
Es decir, $\min g_t(S) > 0$. Por otra parte, si $t > s^*$
\[g_t(S) < 0 \Rightarrow \min g_t(S) < 0\]
Sea $t = \frac{p}{q}$ con $p\in\{1,\dots,K\}, q\in\{1,\dots,|V|-1\}$. Si
probamos todos los casos, tenemos un algoritmo de orden $O(K|V|^4)$. En cambio,
de lo que vimos antes podemos usar búsqueda binaria, lo que nos da un algoritmo
$O(\log(K|V|)|V|^3)$.
\subsection*{P2}
\subsubsection*{a)}
\begin{itemize}
\item[$\Rightarrow$] $\checkmark$
\item[$\Leftarrow$] Supongamos que hay una solución del problema original
que no es factible en el PL. Entonces existe un $(s_i,t_i)$-corte que no
tiene ninguna arista. Pero entonces $s_i,t_i$ no pueden estar conectados
$\contra$
\end{itemize}
\subsubsection*{b)}
Fijemos $i$.Tenemos que
\[\sum_{e\in\delta(S)}x_e\geq 1, \forall \text{$S$ $(s_i,t_i)$-corte} \iff
\min_{\text{$S$ $(s_i,t_i)$-corte}} \sum_{e\in\delta(S)}\geq 1\]
Luego, podemos verificar la desigualdad buscando flujo mínimo. Esto lo podemos
hacer calculando flujo máximo con EK.
\begin{algorithm}
\For{$i=1,\dots,k$}{
Defino la red $(G, x_e, s_i, t_i)$\;
$f\gets$ flujo máximo de la red\;
\If{$f<2$}{
Entrego la desigualdad\;
}
}
\end{algorithm}
\subsection*{P3}
\subsubsection*{a)}
Sea $B$ un corte con $|T\cap B|$ impar mínimo. Definimos
\begin{align*}
T_1 &= T\setminus(B\cup S)\\
T_2 &= (T\cap S)\setminus B\\
T_3 &= T\cap S\cap B\\
T_4 &= (Tcap B)\setminus S
\end{align*}
Por definición de $S$, tenemos que $T_2\cup T_3, T_1\cup T_4\neq\varnothing$ y
por definición de $B$, $T_3\cup T_4,t_1\cup T_2\neq\varnothing$. Luego,
\[(T_1\neq\varnothing\land T_3\neq\varnothing) \lor (T_2\neq\varnothing \land
T_4\neq\varnothing\]
Spg, $T_1,T_3\neq\varnothing$ (si pasa la otra, basta cambiar $B$ por
$V\setminus B$). Por submodularidad de la función de corte,
\[w(\delta(S)) + w(\delta(B)) \geq w(\delta(S\cap B)) + w(\delta(S\cup B))\]
Notemos que
\[|T\cap S\cap B| + |T\cap(S\cup B)| = |T_3| + |T_4| + |T_3| + |T_4|
= \underbrace{|T\cap S|}_{\text{par}} + \underbrace{|T\cap B|}_{\text{impar}}\]
Luego, $|T\cap S\cap B|$ o $|T\cap(S\cup B)|$ es impar.
\begin{itemize}
\item Si $|T\cap S\cap B|$ es impar,
\begin{align*}
w(\delta(S\cap B))&\geq w(\delta(B))\\
w(\delta(S\cup B))&\geq w(\delta(S))
\end{align*}
Luego, $w(\delta(S)) + w(\delta(B)) = w(\delta(S\cap B))+w(\delta(s\cup
B))$. Pero, entonces
\begin{align*}
w(\delta(S\cap B))&\geq w(\delta(B))\\
w(\delta(S\cup B))&\geq w(\delta(S))
\end{align*}
\item El caso en que $|T\cap(S\cup B)|$ es impar, llegamos a que
\begin{align*}
w(\delta(S\cup B))&\geq w(\delta(B))\\
w(\delta(S\cap B))&\geq w(\delta(S))
\end{align*}
Entonces $w(\delta S^c\cap B^c)) = w(\delta(B))$.
\end{itemize}
\subsubsection*{b)}
\begin{algorithm}
Busco el corte mínimo $S$ que deja al menos un vértice de $T$ a cada
lado\footnote{Esto se hace fijando $s\in T$ y haciendo un flujo máximo
para cada vértice en $T\setminus\{v\}$ y quedándose con el menor.}\;
\If{$|S\cap T|$ es impar}{
Ganamos\;
}
\Else{
$T_1\gets T\setminus S$\;
$T_2\gets T\cup S$\;
Busco recursivamente en $T_1$ y en $T_2$\;
}
\end{algorithm}
Sean $R(n,k)$ el tiempo máximo que se demora el algoritmo para grafos con $n$
vértices y $|T| = k$ y $f(n)$ el tiempo máximo para EK. Tenemos que
\begin{align*}
R(n,2) &= f(n)\\
R(n,k) &\leq \max_{k_1,k_2\geq{2}\ k_1+k_1 = k} \{(k-1)f(n) +
R(n,k_1)+R(n,k_2)\}
\end{align*}
Demostraremos por inducción que $R(n,k)\leq k^2f(n)$
\begin{align*}
R(n,k) &\leq \max_{k_1+k_2=k} \{(k-1)f(n) + k_1^2f(n) + k_2^2f(n)\}\\
&\leq f(n)\left[(k-1) + k^2 + \max(-2k_1(k-k_1))\right]\\
&\leq f(n)\left[(k-1) + k^2 -\frac{k^2}{2}\right]\\
&\leq f(n)\left[\frac{k^2}{2} + k-1\right]\leq f(n)k^2
\end{align*}
\subsection*{P4}
Verificar la primera y tercera desigualdad tiene orden $O(V|)$ y $O(|E|)$,
respectivamente. Ahora, para verificar la segunda igualdad, usamos el problema
anterior.
\end{document}