Campus Event Calendar
Event Entry
What and Who
Improved Algorithms for Computing the Cycle of Minimum Cost-to-Time Ratio in Directed Graphs
Karl Bringmann
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 25 July 2017
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
We study the problem of finding the cycle of minimum cost-to-time ratio in a directed graph with n nodes and m edges. This problem has a long history in combinatorial optimization and has recently seen interesting applications in the context of quantitative verification. We focus on strongly polynomial algorithms to cover the use-case where the weights are relatively large compared to the size of the graph. Our main result is an algorithm with running time O ̃(m^0.75 n^1.5), which gives the first improvement over Megiddo’s O ̃(n^3) algorithm for sparse graphs. To obtain our main result, we develop a parallel algorithm for negative cycle detection and single-source shortest paths that might be of independent interest.
This is the extended version of a talk at ICALP'17 (Track B)
Contact
Karl Bringmann
--email hidden
passcode not visible
logged in users only
Karl Bringmann, 07/21/2017 15:06 -- Created document.