Sie sind hier

# 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.

Date
Speaker
Location
Language
21.08.2019
16:00
Danny Hermelin
TEL 512
English

Back to the research colloquium site.

To top