[DMANET] IGAFIT Algorithmic Colloquium - 2pm CET, April 8: Fine-Grained Complexity of Optimization Problems by Karl Bringmann

Dear all,

Please note the next talk on the IGAFIT Algorithmic
Colloquium *this Thursday:*

*April 8, 2021, 14:00 CEST*

Speaker: Karl Bringmann, Saarland University

Title: Fine-Grained Complexity of Optimization Problems
Abstract: Fine-grained complexity theory is the area of theoretical computer
science that proves conditional lower bounds based on conjectures such
as the Strong Exponential Time Hypothesis. This enables the design of
"best-possible" algorithms, where the running time of the algorithm
matches a conditional lower bound.

This talk surveys the developments of fine-grained complexity on classic
optimization problems such as Subset Sum. In particular, since recently
we know a best-possible algorithm for solving Subset Sum in
pseudopolynomial time. We survey this result and the subsequent
developments on approximation algorithms, output sensitive algorithms,
and pseudopolynomial algorithms under different parameters. We also
discuss extensions to other optimization problems such as Knapsack and
Partition, scheduling, and integer linear programming.


We would like to invite you to take part in the event including the
networking session. This new event aims to integrate the European
algorithmic community and keep it connected during the times of the
pandemic. The meeting will be held using Airmeet platform and to attend
please go to https://www.airmeet.com/e/c5d58880-9240-11eb-974a-f53cdfe77b59.
You can find more information about the talk on IGAFIT web page:
http://igafit.mimuw.edu.pl/?page_id=483786.

In order to access Airmeet platform, you will need to register, so that
others know who you are. Then before and after the talk, you will be
located inside a Social Lounge, where discussion tables are visible. Most
of the tables can have up to 8 chairs, and you can join a table by clicking
the "Take a Seat" button on a table. This way you will be able to talk to
people seating currently at the table. When the session starts you will be
automatically switched to see the stage. You can find more instructions on
how to use Airmeet here:
https://www.airmeet.com/hub/step-by-step-guide-use-airmeet-for-attendees/.

We invite you to take part in the event. Please advertise broadly and bring
your students/postdocs as well.

Organization Committee:
Nikhil Bansal
Artur Czumaj
Andreas Feldmann
Danupon Nanongkai
Adi Rosen
Eva Rotenberg
Piotr Sankowski
Christian Sohler

**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************