blob: 0be5a9a3ecc030131ae2447553670f90fdafa2cb (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
|
\documentclass[10pt,a4paper]{article}
\usepackage{fancyhdr}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0pt}
\fancyhead{}
\fancyfoot[C]{Copyright {\textcopyright} 2015 Camil Staps}
\pagestyle{fancy}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\DeclareMathAlphabet{\pazocal}{OMS}{zplm}{m}{n}
\usepackage[hidelinks]{hyperref}
\usepackage{url}
\newcommand*\iN{\bar{N}}
\newcommand*\ex{-}
\newcommand*\with{+}
\DeclareMathOperator{\ms}{\alpha}
\providecommand*{\lemmaautorefname}{Lemma}
\newtheorem{lemma}{Lemma}
\newtheorem{theorem}{Theorem}
\numberwithin{lemma}{subsection}
\numberwithin{theorem}{subsection}
\newenvironment{thmproof}[3][]{%
\begin{samepage}
\begin{#2}%
\def\templabel{#1}%
\def\tempname{#2}%
\def\temptheorem{theorem}%
\ifx\templabel\empty\else\ifx\tempname\temptheorem\label{thm:#1}\else\label{lem:#1}\fi\fi%
#3%
\end{#2}%
\begin{proof}%
}{\end{proof}\end{samepage}}
\newcommand{\refeq}[2][]{\begin{equation}\label{eq:#1}#2\end{equation}}
\usepackage{algorithm}
\usepackage{algorithmic}
\providecommand*{\algorithmautorefname}{Algorithm}
\renewcommand*{\sectionautorefname}{Section}
\renewcommand*{\subsectionautorefname}{subsection}
\renewcommand*{\subsubsectionautorefname}{subsection}
\usepackage{minted}
\title{Miss Algorithm}
\author{Camil Staps}
\begin{document}
\maketitle
\thispagestyle{fancy}
\begin{abstract}
No, this report is not about a new beauty pageant. It is about the realisation and implementation of a maximum independent set size (miss) algorithm.
Garbage collectors and the local government of Nijmegen have agreed to place garbage bins on the at most 100 intersections of the at most 200 streets of the city, with the restriction that no two neighbouring intersections may both have a garbage bin. It is given that on one intersection at most four streets come together. In this report we will discuss an algorithm that can check whether $k$ bins can be placed following that rule.
This problem is of course just a fancy formulation of the maximum independent set problem. So to answer the question, we implement an algorithm that computes the size of the maximum independent set, and verify if $k$ is small enough.
\end{abstract}
\section{Report organisation}
\autoref{sec:notation} will define the notation used throughout this report. In \autoref{sec:algorithm} I will describe the algorithm and argue its correctness. First, we will discuss the basic structure in \autoref{sec:algorithm:basic-structure} through \ref{sec:algorithm:further-optimisations}. After that, we will discuss some helper functions in \autoref{sec:algorithm:helper-function}.
When we have seen the algorithm, \autoref{sec:implementation} will go into details about its implementation in Java. \autoref{sec:analysis} will contain a complexity analysis, both time- and space-wise, of the algorithm and its Java implementation.
\input{notation}
\input{algorithm}
\input{implementation}
\input{analysis}
\input{discussion}
\section{Acknowledgements}
\label{sec:acknowledgements}
I'm grateful to Tom van der Zanden for pointing me to the term `maximum independent set' when discussing what I until then called a `colouring maximising problem'. The term `maximum independent set' eventually led me to Robson's algorithm \cite{robson}.
\begin{thebibliography}{9}
\bibitem{robson}{Robson, J.M. (1985). \emph{Algorithms for Maximum Independent Sets}.}
\end{thebibliography}
\end{document}
|
