229 lines
7.7 KiB
TeX
229 lines
7.7 KiB
TeX
\documentclass{beamer}
|
|
\DeclareMathOperator*{\opt}{OPT}
|
|
|
|
\title[Edge Conn Interdiction]{Faster FPTAS for Edge Connectivity Interdiction}
|
|
\date{\today}
|
|
\author{丛宇}
|
|
% \AtBeginSection[]{
|
|
% \frame{\frametitle{Outline}\tableofcontents[currentsection,
|
|
% subsectionstyle=show/show/shaded]}
|
|
% }
|
|
|
|
\usetheme{Simple}
|
|
\usepackage{algo}
|
|
|
|
\begin{document}
|
|
\begin{frame}[plain]
|
|
% Print the title page as the first slide
|
|
\titlepage
|
|
\end{frame}
|
|
|
|
\begin{frame}[plain]{Plan}
|
|
\tableofcontents
|
|
\end{frame}
|
|
|
|
\section{Connectivity Interdiction}
|
|
|
|
\begin{frame}{Edge Connectivity \& Cut}
|
|
\begin{definition}
|
|
Let $G=(V,E)$ be a undirected connected graph. The minimum cut of $G$ is the minimum set of edges whose removal breaks the connectivity of $G$.
|
|
\end{definition}
|
|
|
|
The edge connectivity of $G$ = $|\text{mincut of $G$}|-1$.
|
|
\newline
|
|
|
|
Edge connectivity is an important measure of network reliability. The greater the edge connectivity, the more difficult it is to break the network's connectivity.
|
|
\newline
|
|
|
|
Now suppose that we want to attack the network. To what extent can we decrease the size of the min-cut by removing a limited set of edges?
|
|
\end{frame}
|
|
|
|
|
|
\begin{frame}{Interdiction}
|
|
\begin{problem}[edge connectivity interdiction]
|
|
The input is a graph $G=(V,E)$ with edge weights $w:E\to \Z_+$ and edge removal cost $c:E\to \Z_+$ and a budget $b\in \Z_+$. The goal is to find a interdiction set $F\subset E$ with $c(F)\leq b$ that minimizes the mincut in $G-F$.
|
|
\end{problem}
|
|
|
|
How to solve this problem if\dots
|
|
\begin{itemize}
|
|
\item the optimal $F$ is given?
|
|
\item the optimal $C$ is given?
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
|
|
\begin{frame}{Example}
|
|
\begin{figure}
|
|
\includegraphics[width=0.8\textwidth]{images/knapsack.png}
|
|
\end{figure}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Prevous Works}
|
|
Zenklusen \citep{zenklusen_connectivity_2014} first studied this problem and showed the following results:
|
|
\begin{itemize}
|
|
\item A PTAS\footnote{polynomial time approximation scheme. The running time is polynomial in the input size if $\epsilon$ is fixed.} for edge connectivity interdiction;
|
|
\item A $\tilde{O}(m^2 n^4)$ algorithm for the unit cost case\footnote{$\tilde{O}$ hides polylog factors}.
|
|
\end{itemize}
|
|
|
|
Later \citep{vygen_fptas_2024} discovered an FPTAS\footnote{Fully PTAS. The running time is polynomial in both the input size and $1/\epsilon$} with time complexity $\tilde{O}(m^2 n^4/\epsilon)$.
|
|
\end{frame}
|
|
|
|
|
|
\section{FPTAS}
|
|
|
|
\begin{frame}{Intermediate Problem}
|
|
\begin{problem}[Normalized Mincut]
|
|
The input is a graph $G=(V,E)$ with edge weights $w:E\to \Z_+$ and edge removal cost $c:E\to \Z_+$ and a budget $b\in \Z_+$. Find an edge set $F\subset E$ with $c(F)\leq b$ and a cut $C$ such that $\frac{w(C-F)}{b+1-c(F)}$ is minimized.
|
|
\end{problem}
|
|
|
|
Let $\tau$ be the optimum of Normalized Mincut. Consider a truncated weight $w_\tau(e)= \min \{w(e),c(e)\tau\}$.
|
|
|
|
\begin{theorem}\label{thm:2approx}
|
|
The optimal cut $C^*$ for Connectivity Interdiction is a 2-approximation of global mincut with weights $w_\tau$.
|
|
\end{theorem}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Algorithm}
|
|
\begin{algo}
|
|
\underline{\textsc{FPTAS for Connectivity Interdiction}}$(G,w,c,b)$\\
|
|
1. estimate Normalized Mincut $\tau$\\
|
|
2. \quad enumerate all 2-approximate mincut with weight $w_\tau$\\
|
|
3. \quad \quad for each cut $C$ solve a knapsack to compute $F$\\
|
|
4. return $(C,F)$ with smallest objective value.
|
|
\end{algo}
|
|
|
|
1 takes $O(\log_{1+\epsilon}(poly(n)))$ time;\newline
|
|
2 takes $O(n^4)$;\newline
|
|
3 takes $O(m^2/\epsilon)$.
|
|
\newline
|
|
|
|
complexity: $\tilde{O}(m^2n^4/\epsilon)$.
|
|
\end{frame}
|
|
|
|
|
|
\section{LP Perspective}
|
|
|
|
\begin{frame}{LP Method}
|
|
\citep{vygen_fptas_2024} gives a strong framework but the intuition behind is vague.
|
|
\begin{equation}\label{IP}
|
|
\begin{aligned}
|
|
\min& & \sum_{e} x_e w(e) & & & &\\
|
|
s.t.& & \sum_{e\in T} x_e+y_e&\geq 1 & &\forall T & &\text{($x+y$ is a cut)}\\
|
|
& & \sum_{e} y_e c(e) &\leq b & & & &\text{(budget for $F$)}\\
|
|
% & & x_e&\geq y_e & &\forall e\quad(F\subset C)\\
|
|
& & y_e,x_e&\in\{0,1\} & &\forall e & &
|
|
\end{aligned}
|
|
\end{equation}
|
|
\end{frame}
|
|
|
|
|
|
\begin{frame}{Normalized Mincut from LP}
|
|
One standard trick for dealing LPs with knapsack constraints is to consider its Lagrangian dual.
|
|
\begin{equation*}
|
|
\max_{\mu\geq 0} L(\mu)= \max_{\mu\geq 0} \min \left\{ w(C\setminus F)-\mu(b-c(F)) | \forall \text{cut $C$}\;\forall F\subset C
|
|
% \land c(F)\leq b
|
|
\right\}
|
|
\end{equation*}
|
|
|
|
\begin{lemma}
|
|
$L(\mu)$ is piecewise linear and concave.
|
|
\end{lemma}
|
|
|
|
For fixed $\mu$, how to solve $\min\limits_{C,F} \left\{ w(C\setminus F)-\mu(b-c(F))
|
|
\right\}$?
|
|
|
|
For small enough $\mu\geq 0$, $w(C\setminus F)$ term is dominanting.
|
|
Thus the optimal solution must be $C=F=\text{mincut with capacity $c$}$.
|
|
\end{frame}
|
|
|
|
|
|
\begin{frame}{Plot $L(\mu)$}
|
|
\begin{figure}
|
|
\includegraphics[width=0.8\linewidth]{images/L.png}
|
|
\end{figure}
|
|
\end{frame}
|
|
|
|
|
|
\begin{frame}{Breakpoints on $L(\mu)$}
|
|
We have see that the first line segment is $L(\mu)=(\lambda_c-b)\mu$ where $\lambda_c$ is the value of mincut with capacity $c$.
|
|
|
|
What is the first breakpoint on $L(\mu)$?
|
|
\newline
|
|
|
|
We have $-\mu(b-\lambda_c)\leq w(C\setminus F)-\mu(b-c(F))$ for any cut $C$ and $F\subsetneq C$. Thus the first breakpoint is $\mu=\min \frac{w(C\setminus F)}{\lambda_c-c(F)}$, which is the value of normalized mincut.
|
|
\newline
|
|
|
|
What about other breakpoints?
|
|
\begin{lemma}
|
|
$\mu^*\in [\min\limits_{C,F} \frac{w(C\setminus F)}{\lambda_c - c(F)},\min\limits_{C,F} \frac{w(C\setminus F)}{b - c(F)}]$
|
|
\end{lemma}
|
|
\begin{lemma}
|
|
$\mu_i=\min \frac{w(C\setminus F)-w(C_{i-1}\setminus F_{i-1})}{c(F_{i-1})-c(F)}$, where the minimum is taken over all cut $C$ and $F\subset C$ such that both the numerator and denominator are positive.
|
|
\end{lemma}
|
|
\end{frame}
|
|
|
|
|
|
\begin{frame}{Weight Truncation from LP}
|
|
Consider the dual of the linear relaxation of IP\ref{IP}.
|
|
|
|
\begin{equation}\label{lp:dualcutint}
|
|
\begin{aligned}
|
|
\max& & \sum_T z_T &- b\mu & &\\
|
|
s.t.& & \sum_{T\ni e} z_T &\leq w(e) & &\forall e\in E\\
|
|
& & \sum_{T\ni e} z_T &\leq c(e)\mu & &\forall e \in E\\
|
|
& & z_T,\mu &\geq 0 & &
|
|
\end{aligned}
|
|
\end{equation}
|
|
|
|
Again we first assume the $\mu$ is fixed. Then for each pair of constraints $\sum z_T \leq w(e)$ and $\sum z_T \leq c(e)\mu$ only one of them works. The real capacity for this fractional tree packing is $\min\{w(e),c(e)\mu\}$, which is exactly the truncated weight $w_\tau$.
|
|
\end{frame}
|
|
|
|
\begin{frame}{Integrality Gap}
|
|
\begin{conjecture}\label{conj:gap2}
|
|
IP\ref{IP} has an integrality gap of 2.
|
|
\end{conjecture}
|
|
|
|
Suppose that $\mu^*$ is the optimal solution to LP\ref{lp:dualcutint}.
|
|
% Let $\lambda^{fr}$ and $\lambda^{int}$ be the fractional and integral mincut with capacity $w_{\mu^*}$.
|
|
\newline
|
|
|
|
Conjecture \ref{conj:gap2} implies $w_{\mu^*}(C^*)+b\mu^* \leq 2(\text{value of mincut with $w_{\mu^*}$})$, \newline which is stronger than Theorem \ref{thm:2approx}.
|
|
\newline
|
|
|
|
However, computational experiments show that the integrality gap of IP\ref{IP} is not a constant.
|
|
\end{frame}
|
|
|
|
|
|
\begin{frame}{Counterexample}
|
|
Consider a cycle $C_n$ of $n$ vertices with two special edges $e_1,e_2$. Let $L$ be a large number.
|
|
\[
|
|
w(e)=\begin{cases}
|
|
1 & e=e_1\\
|
|
L & e=e_2\\
|
|
2 & \text{else}
|
|
\end{cases},\quad
|
|
c(e)=\begin{cases}
|
|
L & e=e_1\\
|
|
1 & \text{else}
|
|
\end{cases}, \quad b=2-\epsilon
|
|
\]
|
|
|
|
For IP, it is clear that $F=\{e_2\}, C\setminus F=\{e_1\}$ and the optimum is 1\newline
|
|
For LP, we assign $x=0$ and $y_e=\frac{1}{n-2}$ for every edge except $e_1$. The optimum is 0.
|
|
\end{frame}
|
|
|
|
|
|
\begin{frame}{Gaps}
|
|
\vspace{-22pt}
|
|
\begin{figure}
|
|
\hspace{25pt}
|
|
\includegraphics[width=0.9\linewidth]{images/gaps.png}
|
|
\end{figure}
|
|
\end{frame}
|
|
|
|
\begin{frame}{References}
|
|
\bibliographystyle{plainnat}
|
|
\bibliography{ref}
|
|
\end{frame}
|
|
|
|
\end{document} |