Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

New for: D1
<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:ETH-tight algorithms for geometric network problems
Speaker:Sandor Kisfaludi-Bak
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Advanced Mini-Course
Visibility:D1, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Thursday, 12 September 2019
Duration:60 Minutes
Building:E1 4
In this talk, I will give a brief overview of the topic of my PhD thesis

and mention some related problems that I am still working on.

Several classical NP-complete graph problems - for example Independent
Set and Dominating Set - have algorithms with running time 2^{O(n)}.
Under the Exponential Time Hypothesis (ETH) significant speedups are not
possible. However, if we introduce geometric constraints on our graphs,
then these running times can be beaten: often 2^O(sqrt(n)) time is
sufficient. In this talk, I will showcase separation techniques that
yield these improved running times when we consider various geometric
intersection graphs, i.e., graphs where the vertices correspond to a set
of objects in Euclidean space, and edges are added between pairs of
intersecting objects. Our lower bound framework shows that the obtained
running times have the best (asymptotic) exponents under ETH. If time
allows, I will end by pushing these algorithmic and lower bound
techniques to their limits, either by allowing more general objects or
by changing the underlying space.

Name(s):Stefano Leucci
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Mouna Litz, 09/12/2019 01:20 PM
  • Stefano Leucci, 09/06/2019 03:38 PM -- Created document.