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

Date, Time and Location

Tuesday, 25 July 2017
30 Minutes
E1 4


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)


Karl Bringmann
--email hidden
passcode not visible
logged in users only

Karl Bringmann, 07/21/2017 15:06 -- Created document.