algorithm.tex

\documentclass[13pt, letterpaper]{article}
\usepackage[left=1in, right=1in, top=1in, bottom=1in]{geometry}
\usepackage{mathexam}
\usepackage{amsmath}
\usepackage{mathtools}
\usepackage{amsfonts}
\usepackage{inputenc}
\usepackage{bbm}
\usepackage{tgtermes}
\usepackage{xcolor}
\usepackage{cases}
\usepackage[english]{babel}
\usepackage{float}
\usepackage{booktabs}
\usepackage{graphicx}
\usepackage{enumitem} %[label=\alph*)] [label=(\roman*)]
\usepackage{cancel}
\usepackage{fancyhdr}
%\usepackage{hyperref}
\usepackage[ruled,vlined]{algorithm2e}



\newcommand{\N}{\mathcal{N}}
\newcommand{\abs}[1]{\lvert #1 \rvert}
\newcommand{\bigabs}[1]{\Bigl \lvert #1 \Bigr \rvert}
\newcommand{\bigbracket}[1]{\Bigl [ #1 \Bigr ]}
\newcommand{\bigparen}[1]{\Bigl ( #1 \Bigr )}
\newcommand{\ceil}[1]{\lceil #1 \rceil}
\newcommand{\bigceil}[1]{\Bigl \lceil #1 \Bigr \rceil}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\bigfloor}[1]{\Bigl \lfloor #1 \Bigr \rfloor}
\newcommand{\norm}[1]{\| #1 \|}
\newcommand{\bignorm}[1]{\Bigl \| #1 \Bigr \| #1}
\newcommand{\inner}[1]{\langle #1 \rangle}
\newcommand{\set}[1]{{ #1 }}
 
\title{CS 170 Project Algorithm}
\author{Smeet Patel}
\date{\today}

\begin{document}
{\let\newpage\relax\maketitle} 
\maketitle


\section{QIP}
\begin{algorithm}[H]

\SetAlgoLined
\KwIn{$i,j$, \ $h_{i,j}$, \  $s_{i,j}$ \ $\forall i, j$,  \ , R, $S_{max}$}
 \vspace*{.1cm}
\KwOut{\{room$_r$: [people $\in$ room$_r$]\}}
 \vspace*{.1cm}
 \textbf{Initialization}: \\
 $e_{{i,j}_k} \leftarrow \{0,1\}, \ \  \forall i,j \And k = \{1, \dots K\} $\\
 $v_{i_{k}} \leftarrow \{0,1\}, \ \ \forall i \And k = \{1, \dots K\}$\\ 
 placements $\leftarrow \left[ \right]$ \\
 output $\leftarrow \{\}$\\
  \vspace*{.1cm}
 \textbf{Objective}: \\
 max$\{e_{{i,j}_{k}} * h_{i,j}\}, \ \ \forall i,j \And k = \{1, \dots K\}$
  \vspace*{.1cm}

 \textbf{Constraints}: 
 \vspace*{.1cm}

$\sum_{k = 1}^{K} e_{{i,j}_{k}} = 1, \ \  \forall i,j $ \\
$\sum_{(i,j)} e_{{i,j}_{k}} \leq \frac{S_{max}}{K}, \ \ k = \{1, \dots K\}$\\
$e_{{i,j}_{k}} = v_{i}v_{j}, \ \ \forall i,j \And k = \{1, \dots K\}$\\
placements $\leftarrow \textit{split}(v_{i}'s, k), \ \ k = \{1, \dots K\}$\\
\For{k in range(K)}{temp $= []$\;
\For{i in range(N)}{\If{\text{placement}[i][k] \textgreater 0}{temp = [i]\; 
output[k] = temp\;
\KwRet{output}
}}}





 \caption{Quadratic Integer program for Graph Partitioning with Dynamic Constraints}
\end{algorithm}

 

\section{ILP}
\begin{algorithm}[H]

\SetAlgoLined
\KwIn{$i,j$, \ $h_{i,j}$, \  $s_{i,j}$ \ $\forall i, j$,  \ , K, $S_{max}$}
 \vspace*{.1cm}
\KwOut{\{room$_r$: [people $\in$ room$_r$]\}}
 \vspace*{.1cm}
 \textbf{Initialization}: \\
 $e_{{i,j}_k} \leftarrow \{0,1\}, \ \  \forall i,j \And k = \{1, \dots K\} $\\
 $v_{i_{k}} \leftarrow \{0,1\}, \ \ \forall i \And k = \{1, \dots K\}$\\ 
 placements $\leftarrow \left[ \right]$ \\
 output $\leftarrow \{\}$\\
  \vspace*{.1cm}
 \textbf{Objective}: \\
 max$\{e_{{i,j}_{k}} * h_{i,j}\}, \ \ \forall i,j \And k = \{1, \dots K\}$

  \vspace*{.1cm}
 \textbf{Constraints}:

 \vspace*{.1cm}
$\sum_{k = 1}^{K} e_{{i,j}_{k}} = 1, \ \  \forall i,j $ \\
$\sum_{(i,j)} e_{{i,j}_{k}} \leq \frac{S_{max}}{K}, \ \ k = \{1, \dots K\}$\\
$e_{{i,j}_{k}} \leq v_{i_{k}} \ \ \forall i \And k = \{1, \dots K\}$ \\ 
$e_{{i,j}_{k}} \leq v_{j_{k}} \ \ \forall i \And k = \{1, \dots K\}$\\
$e_{{i,j}_{k}} \geq v_{i_{k}} +  v_{j_{k}} -1 \ \ \forall i,j \And k = \{1, \dots K\}$\\
placements $\leftarrow \textit{split}(v_{i}'s, k), \ \ k = \{1, \dots K\}$\\
\For{k in range(K)}{temp $= []$\;
\For{i in range(N)}{\If{\text{placement}[i][k] \textgreater 0}{temp = [i]\; 
output[k] = temp\;
\KwRet{output}
}}}
 \caption{Integer Linear program for Graph Partitioning with Dynamic Constraints}
\end{algorithm}









\label{totalpag} 
\end{document}