# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Improved Algorithms for Computing the Cycle of Minimum Cost-to-Time Ratio in Directed Graphs

##### Fulltext (public)

arXiv:1704.08122.pdf

(Preprint), 725KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Bringmann, K., Dueholm Hansen, T., & Krinninger, S. (2017). Improved Algorithms for Computing the Cycle of Minimum Cost-to-Time Ratio in Directed Graphs. Retrieved from http://arxiv.org/abs/1704.08122.

Cite as: http://hdl.handle.net/11858/00-001M-0000-002D-89BC-3

##### 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 $ \tilde O (m^{3/4} n^{3/2}) $, which gives the first improvement
over Megiddo's $ \tilde O (n^3) $ algorithm [JACM'83] for sparse graphs. We
further demonstrate how to obtain both an algorithm with running time $ n^3 /
2^{\Omega{(\sqrt{\log n})}} $ on general graphs and an algorithm with running
time $ \tilde O (n) $ on constant treewidth 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.