[Colloquium] 6/21 Thesis Defense: Haris Angelidakis, TTIC

[Mary Marre via Colloquium]

 *When:*      Thursday, June 21st at 10:00 am

*Where:    * TTIC, 6045 S. Kenwood Avenue, 5th Floor, Room 526

*Who:        *Haris Angelidakis, TTIC


*Title:        *Shortest Path Queries, Graph Partitioning and Covering
Problems in Worst and Beyond Worst Case Settings

*Abstract*

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 (a
notion introduced in order to explain why certain heuristics for shortest
paths are very successful in real-life road networks). 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 and adversarial)
perturbations of the parameters of the input (e.g. edge or vertex weights).
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.



Thesis Advisor: Yury Makarychev  <yury at ttic.edu> <yury at ttic.edu>




Mary C. Marre
Administrative Assistant
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Room 504*
*Chicago, IL  60637*
*p:(773) 834-1757*
*f: (773) 357-6970*
*mmarre at ttic.edu <mmarre at ttic.edu>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20180614/fa4ec193/attachment.html>