Springe direkt zu Inhalt

Lecture by Raphael Steiner (ETH Zürich): Shortest paths on combinatorial polytopes: Hardness and approximation

Jan 08, 2024 | 02:15 PM

I will present some of my joint work with Jean Cardinal on the complexity of computing and approximating shortest paths in the skeleton of a combinatorially defined polytope. In particular, I will discuss proofs for the inapproximability of finding shortest paths on the skeleton of perfect matching polytopes, and of polymatroids, and discuss various related context and problems in which our work is embedded.

After the talk, around 15:30, there will be a tea "break" at the usual place, Room 134 in the first floor (glass door, facing the exit from the stairway).

Time & Location

Jan 08, 2024 | 02:15 PM

Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
Seminar room 053 (ground floor)

Freie Universität Berlin
Technische Universität Berlin
Humboldt-Universität zu Berlin
Deutsche Forschungsgemeinschaft (DFG)