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

[Shubhendu Trivedi via Colloquium]

Reminder:


---------- Forwarded message ----------
From: Mary Marre <mmarre at ttic.edu>
Date: Wed, Jun 20, 2018 at 11:50 AM
Subject: [TTIC Talks] REMINDER: 6/21 Thesis Defense: Haris Angelidakis, TTIC
To: TTIC Talks <talks at ttic.edu>, theory at mailman.cs.uchicago.edu,
colloquium at cs.uchicago.edu, Yury Makarychev <ymakarychev at gmail.com>


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

*Where:    * TTIC, 6045 S. Kenwood Avenue, 5th Floor, Room 526
<https://maps.google.com/?q=6045+S.+Kenwood+Avenue,+5th+Floor,+Room+526&entry=gmail&source=g>

*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
<https://maps.google.com/?q=6045+S.+Kenwood+Avenue+Room+504+Chicago,+IL+%C2%A060637&entry=gmail&source=g>*
*Room 504
<https://maps.google.com/?q=6045+S.+Kenwood+Avenue+Room+504+Chicago,+IL+%C2%A060637&entry=gmail&source=g>*
*Chicago, IL  60637
<https://maps.google.com/?q=6045+S.+Kenwood+Avenue+Room+504+Chicago,+IL+%C2%A060637&entry=gmail&source=g>*
*p:(773) 834-1757*
*f: (773) 357-6970*
*mmarre at ttic.edu <mmarre at ttic.edu>*

On Thu, Jun 14, 2018 at 4:12 PM, Mary Marre <mmarre at ttic.edu> wrote:

> *When:*      Thursday, June 21st at 10:00 am
>
> *Where:    * TTIC, 6045 S. Kenwood Avenue, 5th Floor, Room 526
> <https://maps.google.com/?q=6045+S.+Kenwood+Avenue,+5th+Floor,+Room+526&entry=gmail&source=g>
>
> *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
> <https://maps.google.com/?q=6045+S.+Kenwood+Avenue+Room+504+Chicago,+IL+%C2%A060637&entry=gmail&source=g>*
> *Room 504
> <https://maps.google.com/?q=6045+S.+Kenwood+Avenue+Room+504+Chicago,+IL+%C2%A060637&entry=gmail&source=g>*
> *Chicago, IL  60637
> <https://maps.google.com/?q=6045+S.+Kenwood+Avenue+Room+504+Chicago,+IL+%C2%A060637&entry=gmail&source=g>*
> *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/20180621/3808f875/attachment.html>