direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Es gibt keine deutsche Übersetzung dieser Webseite.

New lower bounds for the Bicriteria Shortest Path problem

Danny Hermelin (Ben-Gurion University of the Negev)


The Bicriteria Shortest Path problem asks to find a path in a given graph that does not exceed two different edge criteria bounds. This problem has several natural applications in network routing systems, and is also used as a subroutine in many scheduling and supply chain management algorithms. In this talk, I will present new lower bounds for this problem which rely on the Strong Exponential Time Hypothesis (SETH).

These results are based on joint work with Amir Abboud, Karl Bringmann, and Dvir Shabtay.


Danny Hermelin
TEL 512

Back to the research colloquium site.

Nach oben

Zusatzinformationen / Extras