Oberseminar: Vorträge von Jonas Sauer (KIT) und Alexej Bochkarev

Im Oberseminar der Arbeitsgruppe Optimierung

am 13.12.2022
um 17:15 Uhr
in 48-208

wird Jonas Sauer vom Karlsruher Institut für Technologie (KIT) zu Gast sein und einen Vortrag zum Thema Efficient Algorithms for Multimodal Journey Planning halten. Interessierte Gäste sind herzlich willkommen.

Abstract:
We study multi-modal route planning in a network and present an overview of state-of-the-art algorithms. We sketch the historical development of these algorithms (including preprocessing techniques), explain the algorithmic ideas, and report about running times of implementations of these algorithms. Finally, we discuss current research topics in this area.

Bereits vorher

um 13:00 Uhr
in 14-420

wird Alexej Bochkarev (ehemals Clemson University, ab 2023 bei uns in Kaiserslautern!) über Binary Decision Diagrams vortragen. Auch hier sind Gäste herzlich willkommen.

Abstract:
The talk focuses on Binary Decision Diagrams and their applications in optimization. This data structure was developed to efficiently manipulate Boolean functions, and sometimes it seems handy to represent a logical (binary) constraint as a diagram. So, some optimization problems can be naturally reformulated as linked network flows through a collection of diagrams (and we are looking for a Consistent path through several diagrams). Informally speaking, the latter can be solved relatively easily if the diagrams have their layers in the same order. Good order of layers may make a diagram small, but in a bad case the size of the diagram grows exponentially. Finding a best order of layers is NP-hard, even for a single diagram.