  In this thesis, we design algorithms for several NP-hard problems in both
worst and beyond worst case settings. In the first part of the thesis, we apply
the traditional worst case methodology and design approximation algorithms for
the Hub Labeling problem; Hub Labeling is a preprocessing technique introduced
to speed up shortest path queries. Before this work, Hub Labeling had been
extensively studied mainly in the beyond worst case analysis setting, and in
particular on graphs with low highway dimension. In this work, we significantly
improve our theoretical understanding of the problem and design (worst-case)
algorithms for various classes of graphs, such as general graphs, graphs with
unique shortest paths and trees, as well as provide matching inapproximability
lower bounds for the problem in its most general settings. Finally, we
demonstrate a connection between computing a Hub Labeling on a tree and
searching for a node in a tree.
  In the second part of the thesis, we turn to beyond worst case analysis and
extensively study the stability model introduced by Bilu and Linial in an
attempt to describe real-life instances of graph partitioning and clustering
problems. Informally, an instance of a combinatorial optimization problem is
stable if it has a unique optimal solution that remains the unique optimum
under small multiplicative perturbations of the parameters of the input.
Utilizing the power of convex relaxations for stable instances, we obtain
several results for problems such as Edge/Node Multiway Cut, Independent Set
(and its equivalent, in terms of exact solvability, Vertex Cover), clustering
problems such as $k$-center and $k$-median and the symmetric Traveling Salesman
problem. We also provide strong lower bounds for certain families of algorithms
for covering problems, thus exhibiting potential barriers towards the design of
improved algorithms in this framework.
