  We are interested in the intersection of approximation algorithms and
complexity theory, in particular focusing on the complexity class APX.
Informally, APX $\subseteq$ NPO is the complexity class comprising optimization
problems where the ratio $\frac{OPT(I)}{ALG(I)} \leq c$ for all instances I. We
will do a deep dive into studying APX as a complexity class, in particular,
investigating how researchers have defined PTAS and L reductions, as well as
the notion of APX-completeness, thereby clarifying where APX lies on the
polynomial hierarchy. We will discuss the relationship of this class with
FPTAS, PTAS, APX, log-APX and poly-APX). We will sketch the proof that Max
3-SAT is APX-hard, and compare this complexity class in relation to $BPP$,
$ZPP$ to elucidate whether randomization is powerful enough to achieve certain
approximation guarantees and introduce techniques that complement the design of
approximation algorithms such as through \textit{primal-dual} analysis,
\textit{local search} and \textit{semi-definite programming}. Through the PCP
theorem, we will explore the fundamental relationship between hardness of
approximation and randomness, and will recast the way we look at the complexity
class NP. We will finish by looking at the \textit{"real world"} applications
of this material in Economics. Finally, we will touch upon recent breakthroughs
in the Metric Travelling Salesman and asymmetric travelling salesman problem,
as well original directions for future research, such as quantifying the amount
of additional compute power that access to an APX oracle provides, elucidating
fundamental combinatorial properties of log-APX problems and unique ways to
attack the problem of whether the minimum set-cover problem is self-improvable.
