%\documentstyle[10pt,twoside]{article} %\documentstyle[twoside]{article} \documentclass[twoside]{article} \setlength{\oddsidemargin}{0 in} \setlength{\evensidemargin}{0 in} \setlength{\topmargin}{-0.6 in} \setlength{\textwidth}{6.7 in} \setlength{\textheight}{8.5 in} \setlength{\headsep}{0.75 in} \setlength{\parindent}{0 in} \setlength{\parskip}{0.1 in} \usepackage{amsmath,amssymb,enumerate,algorithm,ifthen,algorithmic,epsfig,graphicx} % The following commands sets up the lecnum (lecture number) % counter and make various numbering schemes work relative % to the lecture number. % \newcounter{lecnum} \renewcommand{\thepage}{\thelecnum-\arabic{page}} \renewcommand{\thesection}{\thelecnum.\arabic{section}} \renewcommand{\theequation}{\thelecnum.\arabic{equation}} \renewcommand{\thefigure}{\thelecnum.\arabic{figure}} \renewcommand{\thetable}{\thelecnum.\arabic{table}} \newtheorem{theorem}{Theorem} \newtheorem{lemma}{Lemma} \newtheorem{claim}{Claim} \newtheorem{proposition}{Proposition} \newtheorem{prob}{Problem} \newtheorem{corollary}{Corollary} \newtheorem{question}{Question} \newtheorem{conjecture}{Conjecture} \newtheorem{example}{Example} \newtheorem{definition}{Definition} \newtheorem{remarka}{Remark} \def\P{\mathop{\rm P}\nolimits} \def\NP{\mathop{\rm NP}\nolimits} \def\DTIME{\mathop{\rm DTIME}\nolimits} \def\BPTIME{\mathop{\rm BPTIME}\nolimits} \def\ZPTIME{\mathop{\rm ZPTIME}\nolimits} \def\polylog{\mathop{\rm polylog}\nolimits} \newenvironment{remark}{\begin{remarka}\rm}{\end{remarka}} \newenvironment{proof}{{\bf Proof.}}{\hfill\rule{2mm}{2mm}} \newenvironment{pproof}[1]{\noindent{\textbf{Proof of #1.}}}{\hfill\rule{2mm}{2mm}} \newcommand{\calI}{{\cal I}} \newcommand{\calT}{{\cal T}} \newcommand{\calP}{{\cal P}} \newcommand{\opt}{\mbox{\sc opt}} \newcommand{\OPT}{\mbox{\sc OPT}} \newcommand{\QQ}{\mathbb{Q}} \newcommand{\RR}{\mathbb{R}} \newcommand{\ZZ}{\mathbb{Z}} \newenvironment{proofof}{{\bf Proof of }}{\hfill\rule{2mm}{2mm}} % % The following macro is used to generate the header. % \newcommand{\lecture}[5]{ \pagestyle{myheadings} \thispagestyle{plain} \newpage \setcounter{lecnum}{#1} \setcounter{page}{1} \noindent \begin{center} \framebox{ \vbox{\vspace{2mm} \hbox to 6.28in { {\bf CMPUT 498/501: Advanced Algorithms \hfill Fall 2025} } \vspace{4mm} \hbox to 6.28in { {\Large \hfill Lecture #1 (#2): #3 \hfill} } \vspace{2mm} \hbox to 6.28in { {\it Lecturer: #4 \hfill Scribe: #5} } \vspace{2mm}} } \end{center} \markboth{Lecture #1: #3}{Lecture #1: #3} \vspace*{4mm} } % % Convention for citations is authors' initials followed by the year. % For example, to cite a paper by Leighton and Maggs you would type % \cite{LM89}, and to cite a paper by Strassen you would type \cite{S69}. % (To avoid bibliography problems, for now we redefine the \cite command.) % \renewcommand{\cite}[1]{[#1]} \input{epsf} %Use this command for a figure; it puts a figure in wherever you want it. %usage: \fig{NUMBER}{FIGURE-SIZE}{CAPTION}{FILENAME} \newcommand{\fig}[4]{ \vspace{0.2 in} \setlength{\epsfxsize}{#2} \centerline{\epsfbox{#4}} \begin{center} Figure \thelecnum.#1:~#3 \end{center} } % Use these for theorems, lemmas, proofs, etc. % Some useful equation alignment commands, borrowed from TeX \makeatletter \def\eqalign#1{\,\vcenter{\openup\jot\m@th \ialign{\strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$\hfil \crcr#1\crcr}}\,} \def\eqalignno#1{\displ@y \tabskip\@centering \halign to\displaywidth{\hfil$\displaystyle{##}$\tabskip\z@skip &$\displaystyle{{}##}$\hfil\tabskip\@centering &\llap{$##$}\tabskip\z@skip\crcr #1\crcr}} \def\leqalignno#1{\displ@y \tabskip\@centering \halign to\displaywidth{\hfil$\displaystyle{##}$\tabskip\z@skip &$\displaystyle{{}##}$\hfil\tabskip\@centering &\kern-\displaywidth\rlap{$##$}\tabskip\displaywidth\crcr #1\crcr}} \makeatother % **** IF YOU WANT TO DEFINE ADDITIONAL MACROS FOR YOURSELF, PUT THEM HERE: \begin{document} %FILL IN THE RIGHT INFO. %\lecture{**LECTURE-NUMBER**}{**DATE**}{**LECTURER**}{**SCRIBE**} \lecture{1}{Sep 4, 2025}{Template file}{Mohammad R. Salavatipour}{Mohammad R. Salavatipour} % **** YOUR NOTES GO HERE: % Some general latex examples and examples making use of the % macros follow. %**** IN GENERAL, BE BRIEF. LONG SCRIBE NOTES, NO MATTER HOW WELL WRITTEN, %**** ARE NEVER READ BY ANYBODY. %This lecture's notes illustrate some uses of %various \LaTeX\ macros. %Take a look at this and imitate. % %\section{Some theorems and stuff} % Don't be this informal in your notes! % %We now delve right into the proof. % %\begin{lemma} %This is the first lemma of the lecture. %\end{lemma} % %\begin{proof} %The proof is by induction on \ldots. %For fun, we throw in a figure. %%%%NOTE USAGE ! %\fig{1}{1in}{A Fun Figure}{funfig.eps} % %This is the end of the proof, which is marked with a little box. %\end{proof} % %\subsection{A few items of note} % %Here is an itemized list: %\begin{itemize} %\item this is the first item; %\item this is the second item. %\end{itemize} % %Here is an enumerated list: %\begin{enumerate} %\item this is the first item; %\item this is the second item. %\end{enumerate} % %Here is an exercise: % %{\bf Exercise:} Show that ${\rm P}\ne{\rm NP}$. % %Here is how to define things in the proper mathematical style. %Let $f_k$ be the $AND-OR$ function, defined by % %\[ f_k(x_1, x_2, \ldots, x_{2^k}) = \left\{ \begin{array}{ll} % % x_1 & \mbox{if $k = 0$;} \\ % % AND(f_{k-1}(x_1, \ldots, x_{2^{k-1}}), % f_{k-1}(x_{2^{k-1} + 1}, \ldots, x_{2^k})) % & \mbox{if $k$ is even;} \\ % % OR(f_{k-1}(x_1, \ldots, x_{2^{k-1}}), % f_{k-1}(x_{2^{k-1} + 1}, \ldots, x_{2^k})) % & \mbox{otherwise.} % \end{array} % \right. \] % %\begin{theorem} %This is the first theorem. %\end{theorem} % %\begin{proof} %This is the proof of the first theorem. We show how to write pseudo-code now. %%*** USE PSEUDO-CODE ONLY IF IT IS CLEARER THAN AN ENGLISH DESCRIPTION % %Consider a comparison between $x$ and~$y$: %\begin{tabbing} %\hspace*{.25in} \= \hspace*{.25in} \= \hspace*{.25in} \= \hspace*{.25in} \= \hspace*{.25in} \=\kill %\>{\bf if} $x$ or $y$ or both are in $S$ {\bf then } \\ %\>\> answer accordingly \\ %\>{\bf else} \\ %\>\> Make the element with the larger score (say $x$) win the comparison \\ %\>\> {\bf if} $F(x) + F(y) < \frac{n}{t-1}$ {\bf then} \\% %\>\>\> $F(x) \leftarrow F(x) + F(y)$ \\ %\>\>\> $F(y) \leftarrow 0$ \\ %\>\> {\bf else} \\ %\>\>\> $S \leftarrow S \cup \{ x \} $ \\ %\>\>\> $r \leftarrow r+1$ \\ %\>\> {\bf endif} \\ %\>{\bf endif} %\end{tabbing} % %This concludes the proof. %\end{proof} % % %\section{Next topic} % %Here is a citation, just for fun \cite{CW87}. % % **** THIS ENDS THE EXAMPLES. DON'T DELETE THE FOLLOWING LINE: \section{Introduction} You can write stuff here. This document does not have a coherent content and is intended to be used to see some examples of using Latex for typesetting mathematical forumals and content. So things will look out of place as they are borrowed from various (irrelevant) places. Recall that $\P$ is the class of problems solvable in polynomial time and $\NP$ (informally) are those (decision) problems whose solutions can be verified by a polynomial time algorithm. Here is how to create numeric itemized list: \begin{enumerate} \item first item, \label{first} \item second item, \label{second} \item and third item \label{third} \end{enumerate} We can talk about $\P \ne \NP$ or polynmial time algorithms. Here is a different itemized list with reference to the previous one: \begin{itemize} \item relax (\ref{third}), then we are into study of special cases of the problem. \item relax (\ref{second}), we will be in the field of integer programming and the techniques there such as branch-and-bound, etc. \item relax (\ref{first}), we are into study of heuristics and approximation algorithms. \end{itemize} \subsection{A Linear Program} Consider linear program (\ref{lp:primal}) below. \begin{alignat}{3} \text{minimize:} & \quad & \sum_e c(e) \cdot x_e \tag{{\bf TSP-LP}} \label{lp:primal} \\ \text{subject to:} && x(\delta(S)) \geq \quad & 2 \quad && \text{for each cut } \emptyset \subsetneq S \subsetneq V \label{cnst:cut} \\ && x(\delta(v)) = \quad & 2 \quad && \text{for each vertex } v \in V \label{cnst:deg} \\ && x \geq \quad & 0 \notag \end{alignat} Constraints (\ref{cnst:cut}) are the {\em cut constraints} and Constraints (\ref{cnst:deg}) are the {\em degree constraints}. \subsection{Tips} Use $\log n$, not $log~n$. $V = \{v_1, v_2, \ldots, v_n\}$. Check out $\sum_{i=1}^n i$ vs. $\displaystyle \sum_{i=1}^n i$. A displayed equation: \[ H_n = \sum_{k=1}^n \frac{1}{k} = \int_1^n \frac{dx}{x} + O(1) = \ln n + O(1) \] A matrix: \[ \left( \begin{array}{rrr} x_1 & y_1 & z_1 \\ x_2 & y_2 & z_2 \\ 0 & 0 & 1 \end{array} \right) \] Problem names should look like this: \textsc{Set Cover}. Multiple lines under a sum: \[ \sum_{\substack{k = 1\\k \text{ odd}}}^n k = \left\lceil\frac{n}{2}\right\rceil^2 \] \subsection{An Algorithm} Algorithm \ref{alg:kruskal} describes Kruskal's \textsc{Minimum Spanning Tree} procedure. Notice how the algorithm is not appearing right after this paragraph even though it does in the \texttt{.tex}. This is ok for scribe notes, the \LaTeX compiler will still put it close. \begin{algorithm}[h] \caption{Kruskal's \textsc{Minimum Spanning Tree} Algorithm}\label{alg:kruskal} {\bf Input}: Undirected graph $G = (V,E)$ with edge costs $c(e) \geq 0, e \in E$. \\ {\bf Output}: A minimum spanning tree of $G$. \begin{algorithmic} \STATE $T \gets \emptyset$ \FOR{each edge $e \in E$ in increasing order of cost $c(e)$} \IF{$T \cup \{e\}$ does not contain a cycle} \STATE{$T \gets T \cup \{e\}$} \ENDIF \ENDFOR \RETURN $T$ \end{algorithmic} \end{algorithm} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5 \section{NP Optimization problems} An $\NP$ optimization problem, $\Pi$, is a minimization (maximization) problem which consists of the following items: \begin{description} \item{Valid instances:} each valid instance $I$ is recognizable in polynomial time. (note: 'Polynomial time' means polynomial time in terms of the size of the input.) The set of all valid instances is denoted by $D_{\Pi}$. The size of an instance $I \in D_{\Pi} $, denoted by $|I|$, is the number of bits required to represent $I$ in binary. \item{Feasible solutions:} Each $I \in D_{\Pi} $ has a set $S_{\Pi}(I)$ of feasible solutions and for each solution $s \in S_{\Pi}(I)$, $|s|$ is polynomial (in $|I|$). \item{Objective function:} A polynomial time computable function $f(s, I)$ that assigns a non-negative rational value to each feasible solution $s$ for $I$. We often have to find a solution $s$ such that this objective value is minimized (maximized). This solution is called optimal solution for $I$, denoted by $OPT(I)$. \end{description} Examples: \begin{itemize} \item{Vertex Cover:} In this case we have: \begin{description} \item{valid instances :} set of graphs with weighted vertices. \item{feasible solutions :} all the vertex covers of the given graph. \item{objective functions :} minimizing the total weight of a vertex cover. \end{description} \item{Minimum Spanning Tree (MST) problem:} Given a connected graph $G(V,E)$, with each edge $(u,v)\in E$ assigned a weight $w(u,v)$, find an acyclic subset $T \subseteq E$ that connects all the vertices and its total weight is minimized. Since $T$ is acyclic and connects all of the vertices, it is a tree. \begin{description} \item{valid instances :} a graph with weighted edges. \item{feasible solutions :} all the spanning trees of the given weighted graph. \item{objective functions :} minimizing the total weight of a spanning tree. \end{description} \end{itemize} \section{Approximation algorithms} An {\it $\alpha$-factor approximation algorithm} (or simply an $\alpha$-approximation) is a polynomial time algorithm whose solution is always within $\alpha$ factor of optimal solution. \begin{definition}\label{def:factor} For a minimization problem $\Pi$, algorithm $A$ has approximation factor $\alpha$ if it runs in polynomial time and for any instance $I \in D_{\Pi}$ it produces a solution $s \in S_{\Pi}(I)$ such that $f(s,I) \leq \alpha(|I|) \cdot OPT(I)$. $\alpha$ can be a constant or a function of the size of the instance. \end{definition} We use $A(I)$ to denote the value of the solution returned by algorithm $A$ for instance $I$; therefore, from Definition~\ref{def:factor}: $A(I) \leq \alpha(|I|) \cdot OPT(I)$. Below are some theorems and lemmas with complex formulas. \begin{theorem}\label{mainTheo} Assume that $\cal F$ and $\cal E$ are defined as above. There exists a constant $\delta$ such that for any $0<\epsilon\leq 1$ the following holds:\\ Suppose that every trial $f_i\in \cal F$ has a constant number of outcomes %set of outcomes of size polylogarithmic in $n+m$ and we can carry out the random trial in time $t_1$. Let $p_i=e^{-\epsilon|F_i|}$ and suppose that for all $S\subseteq F_i$ it holds that: \begin{itemize} \item if $|S|> \epsilon|F_i|$ then ${\rm Pr}[E_i|_S]\leq p_i$, \item if $|S|\leq \epsilon|F_i|$ then ${\rm Pr}[E_i|_S]=0$, and \item knowing the outcomes of the trials in $S$, we can evaluate whether $E_i|_S$ holds or not in time $t_2$. \end{itemize} Furthermore assume that for $x_i=e^{-\delta\epsilon^2|F_i|}$ it holds that $x_i\leq \frac{1}{e}$ and: \begin{equation}\label{mainTheoEqu} p_i^{\epsilon} \leq x_i\prod_{E_j\in N(E_i)} (1-x_j),\quad\quad 1\leq i\leq m. \end{equation} Then there is a randomized algorithm that finds the outcomes of the random trials in time $O((t_1+t_2)\times {\rm Poly}(n+m))$ with high probability, where ${\rm Poly}(n+m)$ is a polynomial in $(n+m)$, such that for every event $E_i$, the set $F_i$ is partitioned into at most 3 subsets $S_{i,1}, S_{i,2}, S_{i,3}$, so that $E_i|_{S_{i,1}}$, $E_i|_{S_{i,2}}$, and $E_i|_{S_{i,3}}$ are all false. \end{theorem} Now our goal is to prove the following lemma, by which the main lemma can be proved easily. \begin{lemma}\label{lemma1} The expected number of (1,2)-trees $T$ with order at least $\Psi$ is at most $21me^{-\Psi/20}$ . \end{lemma} For a possible (1,2)-tree $T$, we say $T$ starts from $E_0$, if $E_0$ is the initial event of the first 1-component of $T$. Define \[{\cal T}=\{ \mbox{possible (1,2)-trees $T$ with order $O_T=\Psi$ that start at $E_0$}\}.\] Now let ${\cal T}'\subseteq {\cal T}$ be the set of (1,2)-trees obtained after Step 1 of the algorithm that are also in $\cal T$. By this definition and (\ref{treeprob}): \begin{equation}\label{calTprob} E[|{\cal T}'|]=\sum_{T\in {\cal T}} {\rm Pr}[Z_T]\leq \sum_{T\in{\cal T}} \prod_{E_j:v_j\in V_C(T)} p_j. \end{equation} \begin{eqnarray}\label{expT} E[|{\cal T}''_{S_1,\ldots,S_k}|] &= &e^{-S_0}\sum_{{\rm all\;\;} l_1\mbox{\tiny's}\atop{O_{l_1}=S_1}} \sum_{{\rm all}\;\;l_2\mbox{\tiny's}\atop{O_{l_2}=S_2}}\ldots \sum_{{\rm all}\;\;l_k\mbox{\tiny's}\atop{O_{l_k}=S_k}}\prod_{t=1}^{k}\prod_{E_j\in l_t} p_j \nonumber\\ &=&e^{-S_0}\sum_{{\rm all}\;\;l_1\mbox{\tiny's}\atop{O_{l_1}=S_1}}(\prod_{E_{j_1}\in l_1}\!\!p_{j_1} \sum_{{\rm all}\;\;l_2\mbox{\tiny's}\atop{O_{l_2}=S_2} }(\prod_{E_{j_2}\in l_2}p_{j_2} \ldots\sum_{{\rm all}\;\;l_k\mbox{\tiny's}\atop{O_{l_k}=S_k}}\prod_{E_{j_k}\in l_k}\!\!p_{j_k}))\ldots). \end{eqnarray} Denote the set of all extensions $R$ with $O_R=r$ of a set $Q$ by ${\rm EXT}(Q,r)$. For a set $Q$ of events let $X_{Q,r}$ be the number of extensions $R$ such that $R\in {\rm EXT}(Q,r)$ and all events in $R$ have heads tags. Therefore: \begin{equation}\label{expX} E[X_{Q,r}]=\!\!\!\!\!\sum_{R: R\in {\rm EXT}(Q,r)}\!\!\!\!\!{\rm Pr}[Z'_R] =\!\!\!\!\!\sum_{R: R\in{\rm EXT}(Q,r)}\prod_{E_j\in R}p_j. \end{equation} By this equation, the most internal summation in (\ref{expT}) is in fact $E[X_{l_{k-1},S_k}]$. In Section \ref{detailssection}, Lemma \ref{lemma2}, we show that $E[X_{Q,r}]\leq e^{-r/8}e^{O_Q/16}$. Therefore, $E[X_{l_{k-1},S_k}]\leq e^{-S_k/8}e^{S_{k-1}/16}$. Using this fact, Inequality (\ref{expT}) can be written as: \begin{equation}\label{expT2} E[|{\cal T}''_{S_1,\ldots,S_k}|] \leq e^{-S_0} \prod_{i=0}^{k-1} e^{-S_{i+1}/8}e^{S_i/16}. \end{equation} We need the following combinatorial lemma to prove Lemma \ref{lemma1}. \begin{lemma}\label{comblemma} Let $N^+_x$ denote the set of integers greater than or equal to $x$. For $1\leq k\leq \delta\psi$, define $EQ_k$ to be the equation $S_1+S_2+\ldots+S_k=\psi$, where the domain of each variable $S_i$ ($1\leq i\leq k$) is $N^+_{\frac{1}{\delta}}$. Then for sufficiently small $\delta>0$, the sum of the number of the solutions of all equations $EQ_k$ ($1\leq k\leq\delta\psi$) is at most $e^{\psi/80}$. \end{lemma} \begin{proof} Let's call the equation $r_1+r_2+\ldots+r_{\delta\psi}=\psi$, in which the $r_i$'s are the variables whose domain is $N^+_0$, the {\em reference} equation. To each solution of equation $EQ_k$, for $1\leq k\leq\delta\psi$, we associate a unique solution of the reference equation: set $r_i=S_i$, for $1\leq i\leq k$, and $r_j=0$, for $k