Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Improved Algorithms for Computing the Cycle of Minimum Cost-to-Time Ratio in Directed Graphs
Speaker:Karl Bringmann
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Tuesday, 25 July 2017
Duration:30 Minutes
Building: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)

Name(s):Karl Bringmann
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Karl Bringmann, 07/21/2017 03:06 PM
Last modified:
Uwe Brahm/MPII/DE, 07/25/2017 04:01 AM
  • Karl Bringmann, 07/21/2017 03:06 PM -- Created document.