[Facets-of-complexity] Invitation to Monday LectureTODAY, 14:15: Raphael Steiner (Zürich) - Shortest paths on combinatorial polytopes: Hardness and approximation

[Günter Rote <rote@inf.fu-berlin.de>]

Our next Monday Lecture takes place today, on January 8 at FU Berlin.

*_Location_*

*Seminar room 053* - Ground Floor
Freie Universität Berlin, Institut für Informatik
Takustr. 9
14195 Berlin

*_Time_: *Monday, January 8, 2024, 14:15*

*_Lecture_: Raphael Steiner (ETH Zürich)

*_Title_: Shortest paths on combinatorial polytopes: Hardness and approximation

*_Abstract_:*

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.

(Sorry for the late invitation! I just realized that I had sent it to the wrong list)