cs341a3/341-a3-q3.tex

\documentclass[a4paper]{article}

%% Language and font encodings
\usepackage[english]{babel}
\usepackage[utf8x]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{amsthm,amsfonts,amssymb}
\usepackage[ruled,noline,noend]{algorithm2e}
\usepackage{enumerate}

%% Sets page size and margins
\usepackage[a4paper,top=3cm,bottom=2cm,left=3cm,right=3cm,marginparwidth=1.75cm]{geometry}

%% Useful packages
\usepackage{amsmath}
\usepackage[colorinlistoftodos]{todonotes}
\usepackage[colorlinks=true, allcolors=blue]{hyperref}

\title{CS 341 A3 Q3}
\author{Tareef Dedhar - 20621325}

\begin{document}
\maketitle

\section{Question}
\subsection*{Hiring}

In the \textsc{Hiring} problem, you own two companies that have salary budgets $B_1 > 0$ and $B_2 > 0$, respectively. There are $n$ people $1,2,\ldots,n$ applying to work at one of your companies, where person $i$ requires salary $s_i$ and would generate revenues $r_1(i) > 0$ and $r_2(i) > 0$ to companies $1$ and $2$, respectively.

A valid solution to the \textsc{Hiring} problem is the maximum value $R$ for which there exists a pair of disjoint sets $S_1,S_2 \subseteq \{1,2,\ldots,n\}$ that satisfy
\begin{enumerate}[(i)]
\item $\sum_{i \in S_1} s_i \le B_1$,
\item $\sum_{i \in S_2} s_i \le B_2$, and
\item $\sum_{i \in S_1} r_1(i) + \sum_{i \in S_2} r_2(i) = R$.
\end{enumerate}

Design a dynamic programming algorithm to solve the \textsc{Hiring} problem. (Note that to solve the problem, the algorithm needs to find the maximum revenue $R$ as described above, but it does not need to identify the sets $S_1$ and $S_2$.) In your description of the algorithm, make sure you clearly indicate what are the subproblems and the order in which they are solved. Also: your time complexity analysis should be in terms of $n$, $B_1$, and $B_2$.

\section{Solution}
\subsection{Design}
Create a 2D array, with rows representing the amount of employees available to be hired. The first employee to be considered will be the one with the lowest salary, and in ascending order from there (this sorting would take $\Theta$(n logn) time. This is a total of n rows. There would be B1 columns in this array, with each entry representing an amount of B1's total budget to be used. These columns, however, would also have a sub-array in them, going from 0...B2. So, each entry of this 2D array would represent the maximum revenue generated with up to a certain amount of employees, with a budget constrained by a certain amount of B1 and B2. Then, we start at the lowest salary employee, and a budget of 0, 0. From there, we fill in the subsequent cells as follows:

\begin{enumerate}
\begin{item}
If we are adding a new employee with the same budget, take the max of the previous cell, adding the new employee and using the same B1 but less from B2, and adding this employee but using less of B1 and the same amount of B2.
\end{item}
\end{enumerate}
\end{document}