presentation.tex

%------------------------------------------------------------
% Edited by Sajid Samsad
% 1405118, Dept of CSE, BUET
%------------------------------------------------------------

\documentclass{beamer}
\usepackage[utf8]{inputenc}

\usepackage{utopia} %font utopia imported
\usepackage{physics}
\usepackage{fixltx2e}
\usepackage[outline]{contour}
\usepackage{amsmath}
\usepackage{graphicx}
\graphicspath{ {images/} }

\usetheme{Madrid}
\usecolortheme{default}

%------------------------------------------------------------
%This block of code defines the information to appear in the
%Title page
\title[Online Facility Assignment] %optional
{Online Facility Assignment}


\author[Reyan, Saidur, Kobourov] % (optional)
{Abu Reyan Ahmed\inst{1} \and Md.~Saidur rahman\inst{2} \and Stephen Kobourov\inst{1}}

\institute[CSE]
{
  \inst{1}%
  Department of Computer Science\\
  University of Arizona
  \and
  \inst{2}%
  Department of Computer Science and Engineering\\
  Bangladesh University of Engineering and Technology
}


\date[BUET 2018] % (optional)
{Thesis Presentation, April 30, 2018}



%End of title page configuration block
%------------------------------------------------------------





\begin{document}

%The next statement creates the title page.
\frame{\titlepage}




\section{First section}

%---------------------------------------------------------
%Changing visibility of the text
\begin{frame}
\frametitle{Abstract}
Online facility assignment problem consists of a set of facilities \textit{F} of equal capacity
\textit{l}. In the facilities customer arrive one by one in an online manner. \pause

\begin{itemize}
    \item<1-> Assign customer c\textsubscript{i} to facility f\textsubscript{j} before customer c\textsubscript{i+1}
    \item<3-> Cost of the assignment is the distance between c\textsubscript{i} and f\textsubscript{j}
    \item<4-> Total number of customer at most is \textit{$\abs{F}$l}
	\item<5-> The objective is to minimize the sum of all assignment costs.
\end{itemize}
\end{frame}

%---------------------------------------------------------


%---------------------------------------------------------

\begin{frame}
\frametitle{Abstract}
A case is considered where \pause
\begin{itemize}
	\item<1-> facilities are placed on a line \pause
	\item<2-> distance between adjacent facilities is the same \pause
	\item<3-> customer appear anywhere on the line \pause
\end{itemize}

For this case scenario, \pause
\begin{itemize}
	\item<4-> a greedy algorithm described with competitive ratio 4$\abs{F}$
	\item<5-> another algorithm described with competitive ration $\abs{F}$
\end{itemize}

\end{frame}
%---------------------------------------------------------

%---------------------------------------------------------

\begin{frame}
\frametitle{Abstract}
A variant is considered where \pause
\begin{itemize} [after=\vspace{10cm}]
	\item<1-> facilities are placed on the vertices of a graph \pause
	\item<2-> 2 algorithms are designed for this settings \pause
\end{itemize}
\bigskip
\bigskip
A generalized version of this problem is also considered where different facilities may have differernt capacities.

\end{frame}
%---------------------------------------------------------

\section{Second section}

%---------------------------------------------------------
\begin{frame}
\frametitle{Facility Assignment on a Line}

\begin{block}{Facilities} 
F = \textit{\{f\textsubscript{1}, f\textsubscript{2}, f\textsubscript{3}, ........., f\textsubscript{F}\}} is a set of facilities placed on a line.
\end{block} \pause

\begin{block}{Distance}
Distance between every adjacent facilities is d, where d is a constant.
\end{block}  \pause

\begin{block}{Input Sequence} 
\textit{I = \{c\textsubscript{1}, c\textsubscript{2}, c\textsubscript{3}, ........., c\textsubscript{n},\}} is a set of \textit{n} customers who arrive one at a time in an online manner, with c\textsubscript{i} corresponding to the location of customer \textit{i} on the line.
\end{block}

\end{frame}
%---------------------------------------------------------

\section{Third Section}

%---------------------------------------------------------
\begin{frame}
\frametitle{Algorithm Greedy}
Before diving to the algorithm and all those complex staffs, we first need to know some terminology. 
\bigskip

\begin{block} {Well Distributed Input Sequence}
At least one customer between any two adjacent facilities.
\end{block}

\begin{block} {Competitive Ratio}
Worst case ratio between the cost of the solution found by the algorithm and the cost of the optimal solution. Mathematically \(\frac{Cost\_Algorithm(I)}{Cost\_OPT(I)}\) 
\end{block}

\end{frame}
%---------------------------------------------------------

%---------------------------------------------------------
\begin{frame}
\frametitle{Algorithm Greedy}
\includegraphics[scale = .4]{greedy}
\end{frame}


\begin{frame}
\frametitle{Algorithm Greedy}
\contour{black}{Lemma 1.}
\textit{Let d be the distance between all adjacent facilities. If the assignments of OPT and Greedy are not same, then OPT's cost is at least \( \frac{d}{2} \). }

\end{frame}
%---------------------------------------------------------

%---------------------------------------------------------
\begin{frame}
\frametitle{Algorithm Greedy}
\contour{black}{Theorem 1.}
\textit{Let F = \{ f\textsubscript{1}, f\textsubscript{2}, f\textsubscript{3}, .........., f\textsubscript{F}\} be a set of facilities placed on the line, such that the distance between every pair of adjacent facilities is d, where d is a constant. then $\mathcal{R}$(Algorithm\_Greedy) $\leq$ 4$\abs{F}$}

\end{frame}
%---------------------------------------------------------

%---------------------------------------------------------

\begin{frame}
\frametitle{Algorithm Greedy}

\begin{figure}[h]
\includegraphics[scale = .45]{config_of_greedy_and_opt}
\caption{The configurations of Algorithm Greedy and OPT}
\end{figure}

\end{frame}

%---------------------------------------------------------

%---------------------------------------------------------
\begin{frame}
\frametitle{Algorithm Greedy}

\begin{itemize}
	\item<1-> The total cost of Algorithm Greedy is no more than $2\abs{F}d$ \pause
	\item<2-> In the optimum assignment all customers c\textsubscript{i} have cost $\epsilon\textsubscript{i}$ except c\textsubscript{1} \pause
	\item<3-> The cost of first customer c\textsubscript{1} is $\gamma$ , where $\gamma > \frac{d}{2}$ (\textbf{Lemma 1}) \pause
\end{itemize}

\begin{block}{Competitive Ratio}
\( \frac{Cost\_Algorithm\_Greedy(I)}{Cost\_OPT} \) $\leq$ \(  \frac{2\abs{F}d}{\frac{d}{2}} \) \newline
or, 4\( \abs{F} \)
\end{block}

\end{frame}
%---------------------------------------------------------

%---------------------------------------------------------

\begin{frame}
\frametitle{Algorithm Greedy}
Now, there will be a new scenario where the Input sequence is not well distributed. A new intuition will be provided for that.
\end{frame}

%---------------------------------------------------------

%---------------------------------------------------------

\begin{frame}
\frametitle{Poorly distributed input sequence}

\end{frame}

%---------------------------------------------------------

%---------------------------------------------------------

\begin{frame}
\frametitle{Poorly distributed input sequence}

When the input sequence is not well distributed,
\begin{itemize}
	\item<1-> \textit{k} customers have costs greater than \textit{d} in the \textit{optimum assignment}.
	\item<2-> Hence, the total cost of the optimum assignment is at least \textit{kd}.
	\item<3-> The customers at distance less than \textit{d} are assigned with cost \textit{zero} by the optimal assignment algorithm and there are \textit{$\abs{F}$ - k} such customers.
\end{itemize}

\end{frame}

%---------------------------------------------------------

%---------------------------------------------------------

\begin{frame}
\frametitle{Poorly distributed input sequence}

When the input sequence is not well distributed,
\begin{itemize}
	\item<1-> In the assignment created by Algorithm Greedy, each of the customer would have cost at most \textit{d}.
	\item<2-> If any of these customers have cost greater than \textit{d}, then the assignment \textbf{A} can be transformed to an equivalent assignment \textbf{B}.
	\item<3-> For the new assignment \textbf{B} the total cost will be equal to that of the original assignment \textbf{A} so that \textit{$\abs{F}$ - k} customers have cost no more than \textit{d}.
\end{itemize}

\end{frame}

%---------------------------------------------------------

%---------------------------------------------------------

\begin{frame}
\frametitle{Transformation of customer assignment}

\begin{figure}[h]
\includegraphics[scale = .3]{transform1}
\caption{Transforming assignment A to B}
\end{figure}

\end{frame}

%---------------------------------------------------------

%---------------------------------------------------------

\begin{frame}
\frametitle{Transformation of customer assignment}
The transformation goes as follows
\begin{itemize}
	\item<1-> c\textsubscript{1} is assigned to facility f\textsubscript{1} by \textbf{OPT}, and it has cost $\leq$ \textit{d}.
	\item<2-> c\textsubscript{1} is assigned to facility f\textsubscript{2} by \textbf{A'}, and it has cost $>$ \textit{d}.
	\item<3-> A new assignment \textbf{B} can be achieved by assigning c\textsubscript{1} to f\textsubscript{1} and c\textsubscript{2} to f\textsubscript{2} where c\textsubscript{2} was the customer assigned to f\textsubscript{1} by \textbf{A}. 
	\item<4-> Similarly, by swapping the next pair \textbf{A''} assignment can be achieved.
	\item<5-> Until achieving equivalent assignment \textbf{B} this process will be continued.
\end{itemize}

\end{frame}

%---------------------------------------------------------

%---------------------------------------------------------

\begin{frame}
\frametitle{Transformation of customer assignment}

\begin{block}{$\abs{F}$ - k customers}
There are \textit{$\abs{F}$ - k} customers in \textbf{\textit{B}} with cost at most \textit{d}.
\end{block}

\begin{block} {k customers}
Remaining \textit{k} customers have a cost at most \textit{($\abs{F}$ - 1)d}.
\end{block}


\begin{block}{Ratio}
\( \frac{Cost\_Algorithm\_Greedy}{Cost\_OPT} \) $\leq$ \( \frac{(\abs{F} - 1) dk  +  (\abs{F} - k) d}{kd} \)\bigskip
= \( \frac{(k+1)\abs{F}}{k} \) -2
\end{block}

\end{frame}

%---------------------------------------------------------

%---------------------------------------------------------

\begin{frame}
\frametitle{Worst case for Algorithm Greedy}


\end{frame}

%---------------------------------------------------------

%---------------------------------------------------------

\begin{frame}
\frametitle{Worst case for Algorithm Greedy}
Greedy Algorithm has two worst case.

\begin{alertblock}{Worst Case Scenario}
Two pairs of adjacent facilities may have different distances!
\end{alertblock}

\begin{alertblock}{Worst Case Scenario}
Different facilities may have different capacities!
\end{alertblock}

So a different approach has been taken which is known as \textbf{\textit{Capacity Sensitive Greedy Approach}}

\end{frame}

%---------------------------------------------------------


%---------------------------------------------------------
\section{Fourth section}

%---------------------------------------------------------
\begin{frame}
\frametitle{Capacity Sensitive Greedy Approach}

In the previous algorithms, competitive analysis does not depend on the initial capacity of the facilities. Almost same analysis will be taken where initial capacity is greater than one or equals to one.

\end{frame}
%---------------------------------------------------------

%---------------------------------------------------------
\begin{frame}
\frametitle{Capacity Sensitive Greedy Approach}

\contour{black}{Lemma 2.}
\textit{Let $\mathcal{M}$ be a straight line and two facilities having distance d are situated on  $\mathcal{M}$. Then Cost\_Algorithm\_Greedy(I) $\leq$ Cost\_OPT(I) + \( \frac{\abs{I}d}{2}. \) }


\end{frame}
%---------------------------------------------------------


%---------------------------------------------------------
\begin{frame}
\frametitle{Capacity Sensitive Greedy Approach}

\contour{black}{Lemma 3.}
\textit{Let $\mathcal{M}$ be a straight line and two facilities having distance d are situated on  $\mathcal{M}$. Then Cost\_CSG(I) $\leq$ Cost\_OPT(I) + \( \frac{\abs{I}d}{4}. \) }


\end{frame}
%---------------------------------------------------------

\section{Fifth section}

%---------------------------------------------------------
\begin{frame}
\frametitle{Algorithm $\sigma$-Randomized Greedy}
A new approach will be introduced now where greedy method of the previous sections along with randomness will achieve better competitive ratios.
\bigskip
This algorithm is called
\begin{block}{Algorithm}
Algorithm $\sigma$-Randomized Greedy
\end{block}
\end{frame}
%---------------------------------------------------------

%---------------------------------------------------------
\begin{frame}
\frametitle{Algorithm $\sigma$-Randomized Greedy}
Let f\textsubscript{x} be the facility which is nearest to the customer c\textsubscript{y} and let be $\sigma$ be a real number.
\begin{figure}[h]
\includegraphics[scale = .3]{sigma_random}
\caption{Algorithm $\sigma$-Randomized Greedy}
\end{figure}

\end{frame}
%---------------------------------------------------------

%---------------------------------------------------------
\begin{frame}
\frametitle{Algorithm $\sigma$-Randomized Greedy}

\begin{block}{Assignment of customer c\textsubscript{y} to facility f\textsubscript{x}}
If the distance between customer c\textsubscript{y} and facility f\textsubscript{x} is less than $\sigma$ then c\textsubscript{y} is assigned to f\textsubscript{x}. \pause
\end{block}

\begin{block}{Assignment of customer c\textsubscript{y} to facility f\textsubscript{x}}
Otherwise the algorithm tosses a fair coin before assigning a customer to a facility, choosing the nearest free facility to the right(left) if the coin comes head(tails).
\end{block}

\end{frame}
%---------------------------------------------------------

%---------------------------------------------------------
\begin{frame}
\frametitle{Algorithm $\sigma$-Randomized Greedy}

\begin{figure}[h]
\includegraphics[scale = .3]{sigma_algo}
\caption{Algorithm $\sigma$-Randomized Greedy}
\end{figure}

\end{frame}
%---------------------------------------------------------

%---------------------------------------------------------
\begin{frame}
\frametitle{Algorithm $\sigma$-Randomized Greedy}

\contour{black}{Theorem 2.}
\textit{Let I be a well distributed request sequence for Algorithm Greedy. Let $\gamma$ be the optimal cost for the first customer and $\epsilon$\textsubscript{i} be the optimal cost for the i\textsuperscript{th} customer where $i > 1$. If $\sigma > \epsilon$\textsubscript{i} for all i and $\sigma \leq \gamma$ then Algorithm $\sigma$-Randomized-Greedy is \( \frac{9}{2} \)-competitive for I.}

\end{frame}
%---------------------------------------------------------

%---------------------------------------------------------
\begin{frame}
\frametitle{Algorithm $\sigma$-Randomized Greedy}

\begin{block}{Algorithm $\sigma$-Randomized Greedy}
For every customer c\textsubscript{k}, Algorithm $\sigma$-Randomized Greedy chooses either f\textsubscript{k} or f\textsubscript{k+1} with equal probability \( \frac{1}{2} \).
\end{block}

\end{frame}
%---------------------------------------------------------

%---------------------------------------------------------
\begin{frame}
\frametitle{Algorithm $\sigma$-Randomized Greedy}

Expected cost is

\begin{figure}[h]
\includegraphics[scale = .3]{expected_cost}


Since the optimum cost is at least \textit{\( \frac{d}{2} \)}, Algorithm $\sigma$-Randomized Greedy is \textit{\( \frac{9}{2} \)} competitive for \textit{I}.
\end{figure}

\end{frame}
%---------------------------------------------------------


%---------------------------------------------------------
% Edited by 
%---------------------------------------------------------

%---------------------------------------------------------
\begin{frame}
\frametitle{Optimal Fill Algorithm}
This algorithm finds out the facility when 
customer c\textsubscript{i+1} arrives at f\textsubscript{j} for which would be selected by an optimal assignment of all customers c\textsubscript{1},c\textsubscript{2},c\textsubscript{3},......., c\textsubscript{i}.
\newline
\newline

\contour{black}{Theorem 3.}
Let F= \{ f\textsubscript{1}, f\textsubscript{2},. . . , f\textsubscript{F} \}
be a set of facilities placed on the line, such that the distance between every pair of adjacent facilities is d, where d is a
constant. Then R(Algorithm Optimal-Fill) $\leq$ F .
\end{frame}
%---------------------------------------------------------

%---------------------------------------------------------
\begin{frame}
\frametitle{Optimal Fill Algorithm}
For distributed input sequence

\begin{figure}[h]
\includegraphics[scale = .35]{example1}
\end{figure}

\end{frame}
%---------------------------------------------------------


%---------------------------------------------------------
\begin{frame}
\frametitle{Optimal Fill Algorithm}
For any input sequence 
\begin{itemize}
 \item<1->it can be proved by induction that if optimal fill algorithm, pays a cost \textit{x}, a customer has to pay at least $ \lfloor \textit{\( \frac{x}{d} \)} \rfloor $ $\times$ \textit{\( \frac{d}{2} \)}
 \item<2->if the maximum assignment cost of algorithm optimal-fill is \textit{z},then the total assignment cost is no more than \textit{\( \frac{z(z+1)}{2} \)}. Then the optimal cost is at least $ \lfloor \textit{\( \frac{x}{d} \)} \rfloor $ $\times$ \textit{\( \frac{d}{2} \)} which is approximately  \textit{\( \frac{z}{2} \)}.
 \item<3->the ratio is \textit{z+1}. 
 \item<4->the maximum value is $\abs{F}$
\end{itemize}

\end{frame}
%---------------------------------------------------------

%---------------------------------------------------------
\begin{frame}
\frametitle{Optimal Fill Algorithm (extended) }
\contour{black}{Theorem 4.}
\bigskip
Let F= \{ f\textsubscript{1}, f\textsubscript{2},. . . , f\textsubscript{F} \}
be a set of facilities placed on the line arbitrarily, where the capacity of the facilities are arbitrary, and Then $\mathcal{R}$(Algorithm Optimal-Fill) $\leq$ $\abs{F}$.

\end{frame}
%---------------------------------------------------------


%---------------------------------------------------------

\begin{frame}
\frametitle{Facility Assignment on graph}
We now consider the case where the facilities $\mathcal{F}$ are placed on the  vertices of a connected unweighted graph \textbf{\textit{G = (V, E)}} and customers arrive one by one in an online manner at vertices of \textbf{\textit{G}}.
\end{frame}
%---------------------------------------------------------

%---------------------------------------------------------
\begin{frame}
\frametitle{Facility Assignment on graph}

\begin{figure}[h]
\includegraphics[scale = .3]{graaph}
\end{figure}

\end{frame}
%---------------------------------------------------------

%---------------------------------------------------------

\begin{frame}
\frametitle{Facility Assignment on graph}
\contour{black}{Theorem 5}
Let $\mathcal{M}$ be a connected unweighted graph. Then $\mathcal{R}$(Algorithm
Greedy) $\leq$ 2$\abs{E(M)}$\
\begin{itemize}
    \item<1->the graph $\mathcal{M}$ is a tree. 
    \item<2->$\mathcal{M}$ contains at least one cycle.
\end{itemize}
\end{frame}
%---------------------------------------------------------

%---------------------------------------------------------

\begin{frame}
\frametitle{Facility Assignment on graph}
A square box represents a facility and the input customers are shown by their sequence numbers from the example it is clear that,in the worst case,
\begin{itemize}
\item<1-> Cost Greedy(I) $\leq$ \textit{2E(M)}
\item<2-> Cost Greedy(I) $\leq$ \textit{E(M)} and Cost OPT(I) is equal to one.
\end{itemize}

\end{frame}
%---------------------------------------------------------

%---------------------------------------------------------

\begin{frame}
\frametitle{Facility Assignment on graph}
\contour{black}{Theorem 6}
Let M be a connected unweighted graph and a set of facilities F
is placed on the vertices of M. Then $\mathcal{R}$(Algorithm Optimal-Fill) $\leq$  \( \frac{E(M)F}{r} \).

\begin{center}
\includegraphics[scale = .3]{sand}
\end{center}

\end{frame}
%---------------------------------------------------------


%---------------------------------------------------------

\begin{frame}

\end{frame}
%---------------------------------------------------------


% Proof:
% It is sufficient to prove for the case when M is well distributed and a tree.
% let x be a vertex in the centre of the graph and contains no facility. \newline \pause
% If no such vertex exists, the first customer c1 is placed on
% a vertex which is not a facility. \newline \pause
% Otherwise, c1 is placed on x. \newline \pause
% The adversary pays a cost which is no more than radius only for the
% first customer. Algorithm Optimal-Fill traverses an edge no more than $\abs{F}$ times.
% Hence, R(Algorithm Optimal-Fill) is at most \( \frac{E(M)F}{r} \)

%---------------------------------------------------------
\begin{frame}
\frametitle{Facility Assignment on graph}

\begin{figure}[h]
\includegraphics[scale = .4]{sand}
\end{figure}

\end{frame}
%---------------------------------------------------------


%---------------------------------------------------------

\begin{frame}{Finite service time}
Finite service time means customer will access the facility for a certain amount of time. \pause
For unit service time, both Algorithm Greedy and Algorithm
Optimal-Fill provide the optimal solution. \pause
But same is not applicable when time interval=2.
\end{frame}
%---------------------------------------------------------


\begin{frame}{Frame Title}
Theorem 6.
Let t be the time needed to provide service to a assigned customer.
No deterministic algorithm ALG is competitive for t = 2.
proof:
the adversary places the customers on the facilities except the first one like before. \pause
optimal ALG costs less than d. \pause
ALG pays at least d for each customer except the first one
\end{frame}
\begin{frame}{Frame Title}
     
\end{frame}


%---------------------------------------------------------
%Two columns
% \begin{frame}
% \frametitle{Two-column slide}

% \begin{columns}

% \column{0.5\textwidth}
% This is a text in first column.
% $$E=mc^2$$
% \begin{itemize}
% \item First item
% \item Second item
% \end{itemize}

% \column{0.5\textwidth}
% This text will be in the second column
% and on a second thought this is a nice looking
% layout in some cases.
% \end{columns}
% \end{frame}
%---------------------------------------------------------


\end{document}