\documentclass[landscape,a4paper]{slides}
%\pdfpagewidth=11in
%\pdfpageheight=8.5in
\oddsidemargin=0in
\topmargin=-1.2in
\textwidth=10in
\textheight=7.2in
\parskip=0in
\usepackage{graphicx,color}
\usepackage{array,amsmath,latexsym}

\definecolor{backgroundcolor}{rgb}{.5,0,0}
\definecolor{textcolor}{rgb}{1,1,1}
\definecolor{headcolor}{rgb}{1,1,0}
\definecolor{fillcolor}{rgb}{.8,0,0}
\definecolor{filllcolor}{rgb}{.3,0,0}
%\definecolor{backgroundcolor}{rgb}{1,1,1}
%\definecolor{textcolor}{rgb}{0,0,0}
%\definecolor{headcolor}{rgb}{.3,.3,.3}
%\definecolor{fillcolor}{rgb}{.2,.2,.2}
%\definecolor{filllcolor}{rgb}{.6,.6,.6}

\newcommand{\slt}[1]{\hfill\textcolor{headcolor}{\Large\textbf{#1}}\hfill\hbox{}\vfill\raggedright\par}
\newcommand{\prog}[1]{\texttt{#1}}
\newlength\contboxwidth
\newcommand{\cont}{\setbox0=\hbox{\small\space(continued)}%
	\contboxwidth=\wd0\box0\hspace{-\contboxwidth}}

\let\saveendslide=\endslide
\let\saveendoverlay=\endoverlay
\renewcommand{\endslide}{\vfill\saveendslide}
\renewcommand{\endoverlay}{\vfill\saveendoverlay}
\let\saveslide=\slide
\renewcommand{\slide}{\saveslide\flushright}
\let\saveoverlay=\overlay
\renewcommand{\overlay}{\saveoverlay\flushright}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}{Corollary}
\newtheorem{lemma}{Lemma}
\newenvironment{proof}{\par\noindent\textbf{Proof}\space}
{\hfill$\Box$\par}

\newcommand{\func}[1]{\texttt{[#1]}}
\newcommand{\SJF}{\textit{SJF}}
\newcommand{\OPT}{\textit{OPT}}
\newcommand{\oone}{\func{min-time-spent}}
\newcommand{\otwo}{\func{min-weighted-sum}}
\newcommand{\othree}{\func{min-makespan}}
\newcommand{\ofour}{\func{min-number-of-jobs}}
\newcommand{\ofall}{\func{*}}
\newcommand{\theprob}{{\normalfont CD-LBSP}}
\renewcommand{\SS}{\textsc{Subset Sum} problem}
\newcommand{\s}{{\mathit start}}
\newcommand{\f}{{\mathit finish}}

\title{\textcolor{headcolor}{\Huge\bfseries
Common-Deadline\\Lazy Bureaucrat Scheduling Problems
}}
\author{\vspace{1em}\textcolor{textcolor}{\LARGE
	Behdad Esfahbod, Mohammad Ghodsi, Ali Sharifi\\\ \\
	\texttt{\{behdad,ghodsi\}@sharif.edu, ali@bamdad.org}%
}}
\date{\textcolor{headcolor}{%
Computer Engineering Department\\
Sharif University of Technology\\
Tehran, Iran
}}

\pagecolor{backgroundcolor}
\color{textcolor}
\begin{document}
\color{textcolor}

\maketitle

\begin{slide}
\slt{Introduction}
\begin{itemize}
\item Scheduling problems:  A number of jobs to be performed by some employees.
\item Common studies: To be as efficient as possible.
The \emph{employer}'s point of view.
\item Lazy bureaucrat: To be as inefficient as possible.
The \emph{lazy employee}'s point of view.
These are called \emph{Lazy Beauracrat Scheduling Problems} (LBSP).
\item Some restrictions are needed to get out of degenerate
cases.
\item Similar considerations:  Shortest vs longest path
problems.
\end{itemize}
\end{slide}

\begin{slide}
\slt{Problem Definition}
\begin{itemize}
\item A set $J$ of jobs $j_1,\dots,j_n$, processing times (job
    lengths) $t_1,\dots,t_n$,
arrival times $a_1,\dots,a_n$, deadlines $d_1,\dots,d_n$.
\item Jobs should be processed completely, if ever.  We consider
the case with no preemption.
\item Hard deadlines.  Processed jobs should be done so not
before their arrival neither after their deadline.  We call the
interval $[a_i,d_i]$ the \emph{window} for job $i$.
\item Offline scheduling.  We now the arrival times and deadlines
beforehand.
\item All the numbers are non-negative integers.  Assume WLOG
that there is a job arriving at time 0.  Let $D=max(d_i)$.
\end{itemize}
\end{slide}

\begin{slide}
\slt{More Definitions}
\begin{itemize}
\item \textbf{Executable Job:}  Job $j_i$ is \emph{executable} at
time $t$, iff it is not processed yet, and $a_i\leq t\leq d_i-t_i$.
\item \textbf{Greedy Requirement:}  
At any time, the bureaucrat should work on an executable job, if
there is any.
\item The goal is to be as inefficient as possible.  
This is captured by any of the following objective functions that
is to minimize.
\end{itemize}
\end{slide}

\begin{slide}
\slt{Objective Functions}
\begin{enumerate}
\item \oone: Minimize the total amount of time spent working.
\item \otwo: Minimize the weighted sum of completed jobs.
\item \othree: Minimize the makespan, the maximum completion time of the jobs.
\item \ofour: Minimize the total number of completed jobs.
\end{enumerate}
Objective functions 1 and 4 are special cases of 2.\\
If all jobs have the same arrival time, the  objective functions 1 and
3 are equivalent.
\end{slide}

\begin{slide}
\slt{Some Previous Results}
Non-preemptive and multi-employee cases have also been studied.
They are not listed here.
\begin{itemize}
\item LBSP is strongly NP-hard under all objective functions
and is not approximable to within any fixed factor.

\item LBSP with the same arrival times for all jobs, is weakly NP-hard, and
can be solved by a pseudo-polynomial dynamic programming algorithm.

\item LBSP with all the jobs having unit lengths, can be solved in
polynomial time by the Latest Deadline First (LDF) scheduling policy.
\end{itemize}
\end{slide}

\begin{slide}
\slt{Some Previous Results\cont}
\begin{itemize}
\item Assuming for each job $i$, $d_i-a_i<2t_i$, LBSP can be
solved in $O(nD\max(n,D))$ time.

\item Even with a bound on $\delta$ (the ratio of the longest job to the
shortest job), LBSP is strongly NP-hard.
It cannot be approximated to within a factor of $\delta - \epsilon$,
for any $\epsilon>0$, unless $P=NP$.

\item Given bounds on $R$ (the maximum ratio of window length to job length)
and $\delta$, LBSP can be solved
in $O(Dn^{4R\lg\delta})$.

\item Assuming $d_i-a_i<2t_i$ for each job $i$ ($R\leq 2$), 
LBSP can be solved in $O(nD)$ time.
\end{itemize}
\end{slide}

\begin{slide}
\slt{Our Problem --- Notation}
\begin{itemize}
\item \textbf{Common-Deadline LBSP (\theprob):}
When deadlines for all jobs are the same ($D$).
\item \textbf{\theprob\func{\emph{objective-function}}:}
When considered with one of defined objective functions.
\item \textbf{\theprob\ofall:} All/any of the objective functions.
\end{itemize}
\end{slide}

\begin{slide}
\slt{Results}
\begin{itemize}
\item \theprob\ofall\ is still NP-hard.
\item \theprob\ofour\ is not approximable to within any fixed factor.
\item There is a tight 2-approximation algorithm for \theprob\othree.
\item \theprob\ofall\  is \emph{weakly} NP-hard:
There exists a pseudo-polynomial time dynamic programming algorithm.
\end{itemize}
\end{slide}

\begin{slide}
\slt{NP-Hardness}
\begin{theorem}
{\normalfont \theprob}\ofall\ is NP-hard.
\end{theorem}
\proof
\begin{itemize}
\item Reduce  the \SS\ to this problem,
\item Given:
$S=\{x_1,\ldots, x_n\}$ of $n$ positive integers, where
$\Sigma_{i=1}^n x_i = s$, and integer $b$ ($0<b<s$),
\item Is there any $T\subset S$, satisfying
$\Sigma_{x\in T}\, x = b$?
\item WLOG, we assume
that $b\le \lfloor \frac{s}{2}\rfloor$ and $x_i<b$ for all $i$.
\item Construct an instance of \theprob\ containing $n+1$ jobs.
\end{itemize}
\end{slide}

\begin{slide}
\slt{NP-Hardness\cont}
\begin{itemize}
\item All deadlines $D=2s$,
\item $\forall x_i\in S$, define job $j_i$ with $a_i=0$, and $t_i=2x_i$,
\item Define $j_{n+1}$ with $a_{n+1}=2b$ and $t_{n+1}=2s-2b-1$.
\item The employee can finish his work by time $2s$ or $2s-1$,
\item He can finish by $2s-1$ iff he finds a solution for the \SS.
\end{itemize}
\endproof
\end{slide}

\begin{slide}
\slt{Approximablity}
\begin{theorem}
\theprob\ofour\ is not approximable to within any fixed factor
$\Delta>1$, unless $P=NP$.
\end{theorem}
\proof
\begin{itemize}
\item Reduce \SS\ again!  This time to reach contradiction.
\item Assume that there is an approximation algorithm with a fixed
factor $\Delta$.
\item Let $m=\lceil\Delta\rceil$ and $D=b+m(n+2)s$ (a huge number).
\end{itemize}
\end{slide}

\begin{slide}
\slt{Approximablity\cont}
\begin{itemize}
\item Construct an instance of \theprob\ofour\ containing the following jobs, 
all with deadline $D$:
\begin{itemize}
\item $\forall x_i\in S$, define an {\em element job}
$j_i$ having $a_i=0$, and $t_i=x_i$,
\item Define one {\em long job}, $j_{n+1}$ with $a_{n+1}=b$ and $t_{n+1}=D-b$.
\item And define $m(n+2)-1$ {\em extra jobs} (lots of them), all having
arrival times  $b$, and processing times $s$.
\end{itemize}
\item The bureaucrat wants to do as few jobs as possible:  He
should process the long job, to avoid too many extra jobs,
\item So he can process as few as $n+1$ jobs iff he finds a
solution for the \SS.
\end{itemize}
\end{slide}

\begin{slide}
\slt{Approximablity\cont}
\begin{itemize}
\item The hypothetical $\Delta$-approximation would produce at
most $m(n+1)$ jobs.
\item There are $m(n+2)-1$ extra jobs, that all can be processed
if the long job is not.
\item So the approximation algorithm is forced to produce the optimal
solution $\Rightarrow$ solution for the \SS\ $\Rightarrow$ $P=NP$.
\end{itemize}
\endproof
\begin{corollary}
\theprob\otwo\ is not approximable to within any fixed factor
$\Delta>1$, unless $P=NP$.
\end{corollary}
\end{slide}

\begin{slide}
\slt{Approximation}
\begin{theorem}
The Shortest Job First (SJF) scheduling policy is a 2-approximation
algorithm for \theprob\othree\ and this bound is tight.
\end{theorem}

\proof
\begin{itemize}
\item Let $\sigma_{OPT}$ be an optimal solution and $\sigma$ be 
the schedule which the SJF policy
has generated, and \OPT\ and \SJF\ be their makespans respectively,
\item We show that $\SJF-\OPT<\OPT$,
\item WLOG suppose that $j_1,\dots,j_k$ are the jobs processed in
$\sigma$ in that order,
\item Let $j_q\in\sigma$ be the job satisfying
$\s_q(\sigma)<\OPT\leq\f_q(\sigma)$,
\end{itemize}
\end{slide}

\begin{slide}
\slt{Approximation\cont}
\begin{itemize}
\item We know that $a_i<\OPT$ for all jobs,
\item SJF policy forces that $t_{q+1}\leq t_{q+2}\leq\ldots\leq t_k$,
\item Greedy requirement forces that $j_i\in\sigma_{OPT}$ for all $q+1\le i\le k$
\item If $j_q\in\sigma_{OPT}$ then 
$\SJF-\OPT< \Sigma_{i=q}^{k}t_i \le OPT$, and we are done,
\item Otherwise, there exists some job in $\sigma_{OPT}$ that is
arrived before $j_q$, and not shorter than $j_q$,
which is not processed in $\sigma$, call it $j_p$,
\item So we have
$$\SJF-\OPT<t_q+\Sigma_{i=q+1}^{k}t_i\leq t_p+\Sigma_{i=q+1}^{k}t_i \leq \OPT.$$
\end{itemize}
\end{slide}

\begin{slide}
\slt{Tightness}
\begin{itemize}
\item Given $n$ and $0<\epsilon<1$, we construct an
instance of \theprob\ with $n$ jobs, which SJF does no better
than $2-\epsilon$,
\item All jobs have $a_i=0$ and
$d_i=D$, where $D=n-3+2L-1=n+2L-4$ with $L=2n/\epsilon$: 
\item $t_1=L-1$, $t_2=L$, $t_3=L+1$, $t_i=1$ ($4\leq i\leq n$),
\item OPT would process all unit jobs and then $j_3$,
having  makespan  $\OPT=n-3+L+1=n+L-2$,
\item SJF would process $j_4,\ldots,j_n$, $j_1$, and $j_2$
having  makespan  $\SJF=n-3+L-1+L=n+2L-4$.
\item With some magical math, we would have
$\frac{\SJF}{\OPT}>2-\epsilon$.\endproof
\end{itemize}
\end{slide}

\begin{slide}
\slt{Pseudo-Polynomial Time Algorithms}
\begin{itemize}
\item Assume that the jobs are numbered in order of their arrival
times,
\item Let $T_i=\{j_i,\dots,j_n\}$, $T_{i,k}=\{j_i,\dots,j_k\}$,
\item We can assume that in the optimal schedule, the consecutive
jobs are performed in order of their arrival times,
\end{itemize}
\begin{lemma}
For a given $(T_i,\alpha,U)$, we can find an optimal schedule
without any gaps from some jobs in $T_i$, and up to time $\alpha$, 
so that all jobs in $U$ appear in the schedule, if any such
schedule exists, in time $O(n\alpha)$.
\end{lemma}
\proof It can be solved much like the binary knapsack problem.
\endproof
\end{slide}

\begin{slide}
\slt{Pseudo-Polynomial Time Algorithms\cont}
\begin{theorem}
\theprob\ofall\  is weakly NP-hard.
\end{theorem}
\proof
\begin{itemize}
\item Let $P_i$ be the subproblem of scheduling the jobs in
$T_i$.  $P_1$ is the original problem,
\item Let $\alpha$ be the first \emph{rest time} in an optimal
schedule $\sigma$ for $P_i$,
\item So the schedule can be broken into two independent
subschedules, one before $\alpha$, and one after $\alpha$,
\item For $\alpha$ to be a rest time, there are some jobs forced
to be in the first schedule,
\end{itemize}
\end{slide}

\begin{slide}
\slt{Pseudo-Polynomial Time Algorithms\cont}
\begin{itemize}
\item The first subschedule can be found by applying the lemma from
previous page,
\item The second one is the optimal solution to subproblem
$P_k$, where $j_k$ is the first job arriving after $\alpha$,
\item All we need to do is to search for $\alpha$.
\item This all takes time $O(n^2D^2)$ to solve $P_1$.
\item So \theprob\ofall\ is weakly NP-hard.
\end{itemize}
\endproof
\end{slide}

\begin{slide}
\slt{Conclusion}
We studied a new class of the Lazy Bureaucrat Scheduling
Problems (LBSP), called  common-deadline LBSP, 
where the deadlines of all jobs are the same. We proved that this
problem is still NP-hard under all four
pre-defined objective functions. We also showed that this problem is not
approximable to within any fixed factor in cases of \otwo\ and \ofour\ objective
functions. The problem is shown to have a tight
2-approximation algorithm under \othree. But, it is
still open whether it is approximable  under \oone. In
the rest of the paper, we presented  pseudo-polynomial time
dynamic programming algorithms for this problem under all objective functions.
Further work on this problem is underway.

\noindent{\bf\textcolor{yellow}{Acknowledgements}} The authors would like to thank the anonymous referees for their
useful comments.
\end{slide}

\begin{slide}
\slt{References}
\noindent
        Arkin, E.~M., Bender, M.~A., Mitchell, J.~S.~B., Skiena, S.~S.:
	\emph{The lazy bureaucrat scheduling problem}.
	Workshop on Algorithms and Data Structures (WADS'99), LNCS 1663, pp.~122--133,
	Springer-Verlag, 1999.

\noindent
Gary, M.~R., Johnson D.~ S.: \emph{Computers and intractability, a guide to the
theory of NP-completeness}. W.~H.~ Freeman and Company, New York, 1979. 

\noindent
         Farzan, A., Ghodsi, M.:
	\emph{New results for lazy bureaucrat scheduling problem}.
	7th CSI Computer Conference (CSICC'2002),
	Iran Telecommunication Research Center,
	March 3--5, 2002, pp.~66--71.

\noindent
        Hepner, C., Stein, C.:
        \emph{Minimizing makespan for the lazy bureaucrat problem}.
        Scandinavian Workshop on Algorithm Theory (SWAT'2002), LNCS 2368, pp.~40--50, Springer-Verlag, 2002.
\end{slide}

\end{document}

\begin{slide}
\slt{}
\begin{itemize}
\item
\end{itemize}
\end{slide}