Campus Event Calendar
Event Entry
What and Who
Approximation Algorithms for Flexible Network Design
Joseph Cheriyan
Combinatorics and Optimization, University of Waterloo
AG1 Mittagsseminar (own work)
Joseph is Professor in the department of Combinatorics and Optimization at the University of Waterloo. He was a member of the group some 25 years ago. He was the only foreign postdoc who by the end of his stay was able to give talks in German.
AG 1, INET, AG 5, RG1, SWS, AG 2, AG 4, D6, AG 3
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 20 October 2022
13:00
45 Minutes
MPI-INF
024
Saarbrücken
Abstract
Adjiashvili, Hommelsheim and M\"uhlenthaler (IPCO 2020) introduced a new and "natural" model of network
design called flexible graph connectivity: given a multi-graph G=(V,E) with non-negative costs on the edges
and a partition of E into a set of safe edges and a set of unsafe edges, find a cheapest connected spanning
subgraph H=(V,F) of G that stays connected even after the failure of one unsafe edge (that is, H-e is
connected for each unsafe edge e in F). Recent research has focused on approximation algorithms for this
model and its extensions, and this has raised perplexing questions. The talk will cover the AHM model and its
extensions, as well as some approximation algorithms for these models.
Contact
passcode not visible
Kurt Mehlhorn, 10/11/2022 09:49
Kurt Mehlhorn, 09/19/2022 12:42 -- Created document.
Kurt Mehlhorn, 09/19/2022 12:42 -- Created document.