diff options
Diffstat (limited to 'docs/report')
| -rw-r--r-- | docs/report/report.pdf | bin | 0 -> 112770 bytes | |||
| -rw-r--r-- | docs/report/report.tex | 65 | ||||
| -rw-r--r-- | docs/report/styles/header.sty | 35 | ||||
| -rw-r--r-- | docs/report/styles/packages.sty | 12 | ||||
| -rw-r--r-- | docs/report/styles/section.sty | 35 | ||||
| -rw-r--r-- | docs/report/styles/title.sty | 29 |
6 files changed, 176 insertions, 0 deletions
diff --git a/docs/report/report.pdf b/docs/report/report.pdf Binary files differnew file mode 100644 index 0000000..5092c22 --- /dev/null +++ b/docs/report/report.pdf diff --git a/docs/report/report.tex b/docs/report/report.tex new file mode 100644 index 0000000..02472ac --- /dev/null +++ b/docs/report/report.tex @@ -0,0 +1,65 @@ +\documentclass[11pt]{scrartcl} + +% Metadata +\title{Global Min Cut} +\subtitle{CS 456: Project 5} +\author{Neil Kollack and Toby Vincent} + +% Packages +\usepackage{styles/packages} +\usepackage{styles/header} +\usepackage{styles/title} +\usepackage{styles/section} +\usepackage{csvsimple} +\usepackage{graphicx} +\usepackage{amsmath} + +\begin{document} +\maketitle + +\section{Introduction} + +The goal of this project was to analyze and compare the Edmonds-Karp algorithm with Karger's approximation algorithm for finding the global minimum cut of a graph. The global minimum cut problem consists of finding the lowest capacity cut through a graph. Being a NP Hard problem, the runtime of finding the exact solution using the Edmonds–Karp algorithm is $O(\vert V \vert ^ 2 \vert E \vert ^ 2)$, and as such, we aim to experiment with Karger's approximation algorithm to discover its viability, and what trade-offs are made compared to the Edmonds–Karp algorithm. + +\section{Results} + +\begin{table}[h] + \centering + \resizebox{\textwidth}{!}{% + \csvautotabular{../../output/constant_cuts.csv}} + \resizebox{\textwidth}{!}{% + \csvautotabular{../../output/constant_times.csv}} + \caption{\label{tab:constant} Minimum cut and associated runtimes for $10$ iterations} +\end{table} + +\begin{table}[h] + \centering + \resizebox{\textwidth}{!}{% + \csvautotabular{../../output/linear_cuts.csv}} + \resizebox{\textwidth}{!}{% + \csvautotabular{../../output/linear_times.csv}} + \caption{\label{tab:linier} Minimum cut and associated runtimes for $n$ iterations} +\end{table} + +\begin{table}[h] + \centering + \resizebox{\textwidth}{!}{% + \csvautotabular{../../output/polynomial_cuts.csv}} + \resizebox{\textwidth}{!}{% + \csvautotabular{../../output/polynomial_times.csv}} + \caption{\label{tab:polynomial} Minimum cut and associated runtimes for $n^2\ln n$ iterations} +\end{table} + +\section{Analysis} + +When looking at the probability of not finding the minimum cut we know that when repeating the contraction algorithm $n^2 ln(n)$ times that the probability of not finding the minimum cut is $1/n^2$. However, when running the algorithm only n times there is a rather noticeable change in the probability. Simplifying the probability equation down from $P_n = 1-[ 1- \binom{n}{2}^{-1}]^n$ to $P_n = 1-[ 1-\frac{2}{n^2-n} ]^n$ it becomes apparent that while running the algorithm n times is moving toward a low probability of not finding the minimum cut, it is nowhere near as effective as $n^2 ln(n)$ times. Where running n times the failure rate never really reaches a sufficiently small probability, whereas $n^2 ln(n)$ would reach a point of failure that is sufficient on graphs with very small n values. + +When also taking into account that we performed 5 repetitions, the probability of failure for $n^2 ln(n)$ drops immediately to almost zero, even at n = 2. Where n still has at least a 1\% overall failure rate. This is reflected in our data, where $n^2 ln(n)$ did not fail on any repetitions and n failed a majority of the time but at least one of the five repetitions came up with the correct answer. + +As for the runtimes, as expected with the Contraction Algorithm being $O(\vert V \vert ^2* \vert E \vert *log(V))$, which is at least a factor less than the Edmonds-Karp method, the approximation method is much faster even when ran $n^2 ln(n)$ times. Therefore, with the accuracy of the $n^2 ln(n)$ iteration Contraction Algorithm matching that of the exact method, and its runtime proving to be better, this experiment would seem to conclude that the $n^2 ln(n)$ iteration approximation is the preferable choice of all options examined + +\section{Conclusion} + +Due to the insurmountable runtimes of the algorithm on a larger graph for $n^2\ln n$ iterations, it is unfeasible to run the number of repetitions needed for a dataset large enough to conclusively show the probability of not finding the minimum cut converges to zero. Even with parallelization of the main iteration loop the runtime of larger graphs was still excessive. That being said, even five repetitions of the algorithm illustrates the disparity between the different iteration counts that where chosen for this experiment. The level of experimentation was a successfully demonstrated the viability of using Karger's algorithm as a solution to an otherwise difficult problem. + +\end{document}
\ No newline at end of file diff --git a/docs/report/styles/header.sty b/docs/report/styles/header.sty new file mode 100644 index 0000000..b86e98e --- /dev/null +++ b/docs/report/styles/header.sty @@ -0,0 +1,35 @@ +\NeedsTeXFormat{LaTeX2e} +\ProvidesPackage{styles/header}[2021/09/29 Header style] + +% ┌───────────────────────────────────┐ +% │ Title: Subtitle │ ──┬─ [Header] +% │ Author │ ──┘ +% │ Title │ ──┬─ Title +% │ Subtitle │ ──┘ +% │ │ +% │ A Section │ ──┬─ Sections +% │ ... │ │ +% │ 1.1 A Subsection │ ──┤ +% │ ... │ │ +% │ Another Section │ ──┤ +% │ ... │ │ +% │ 2.1 A Subsection │ ──┤ +% │ ... │ │ +% │ 2.2 Another Subsection │ ──┘ +% │ ... │ +% │ │ +% │ │ +% └───────────────────────────────────┘ + +\pagestyle{myheadings} + +\newsavebox{\headingbox} +\sbox{\headingbox}{% + \begin{minipage}[b]{0.5\textwidth} + \begin{flushright} + \@title \\ + \@subtitle \\ + \@author \\ + \end{flushright} + \end{minipage}} +\markright{\hfill\usebox{\headingbox}} diff --git a/docs/report/styles/packages.sty b/docs/report/styles/packages.sty new file mode 100644 index 0000000..262b9d1 --- /dev/null +++ b/docs/report/styles/packages.sty @@ -0,0 +1,12 @@ +\NeedsTeXFormat{LaTeX2e} +\ProvidesPackage{styles/packages}[2021/09/29 Package imports] + +\RequirePackage[english]{babel} +\RequirePackage[letterpaper,top=2.54cm,bottom=2.54cm,left=2.54cm,right=2.54cm,marginparwidth=1.75cm]{geometry} +\RequirePackage{lipsum} +\RequirePackage{array} +\RequirePackage[colorlinks=true, allcolors=blue]{hyperref} +\RequirePackage[autostyle, english = american]{csquotes} + +% Styles +\MakeOuterQuote{"}
\ No newline at end of file diff --git a/docs/report/styles/section.sty b/docs/report/styles/section.sty new file mode 100644 index 0000000..ed4d606 --- /dev/null +++ b/docs/report/styles/section.sty @@ -0,0 +1,35 @@ +\NeedsTeXFormat{LaTeX2e} +\ProvidesPackage{styles/section}[2021/09/29 Section style] + +% ┌───────────────────────────────────┐ +% │ Title: Subtitle │ ──┬─ Header +% │ Author │ ──┘ +% │ Title │ ──┬─ Title +% │ Subtitle │ ──┘ +% │ │ +% │ A Section │ ──┬─ [Sections] +% │ ... │ │ +% │ 1.1 A Subsection │ ──┤ +% │ ... │ │ +% │ Another Section │ ──┤ +% │ ... │ │ +% │ 2.1 A Subsection │ ──┤ +% │ ... │ │ +% │ 2.2 Another Subsection │ ──┘ +% │ ... │ +% │ │ +% │ │ +% └───────────────────────────────────┘ + +\RequirePackage{indentfirst} +% \RequirePackage{titlesec} +% \titlespacing*{\section}{0pt}{1.1\baselineskip}{\baselineskip} + +% Paragraph spacing +\setlength{\parskip}{1em} + +\RedeclareSectionCommand[ + afterindent=false, + beforeskip=.5\baselineskip, + afterskip=.5\baselineskip +]{section}
\ No newline at end of file diff --git a/docs/report/styles/title.sty b/docs/report/styles/title.sty new file mode 100644 index 0000000..fdeabbe --- /dev/null +++ b/docs/report/styles/title.sty @@ -0,0 +1,29 @@ +\NeedsTeXFormat{LaTeX2e} +\ProvidesPackage{styles/title}[2021/09/29 Title style] + +% ┌───────────────────────────────────┐ +% │ Title: Subtitle │ ──┬─ Header +% │ Author │ ──┘ +% │ Title │ ──┬─ [Title] +% │ Subtitle │ ──┘ +% │ │ +% │ A Section │ ──┬─ Sections +% │ ... │ │ +% │ 1.1 A Subsection │ ──┤ +% │ ... │ │ +% │ Another Section │ ──┤ +% │ ... │ │ +% │ 2.1 A Subsection │ ──┤ +% │ ... │ │ +% │ 2.2 Another Subsection │ ──┘ +% │ ... │ +% │ │ +% │ │ +% └───────────────────────────────────┘ + +\renewcommand{\maketitle}{ + \begin{flushleft} + {\Huge \bfseries \sffamily \@title }\\[2ex] + {\Large \sffamily \@subtitle }\\[4ex] + \end{flushleft} +} |