English

# Item

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

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.

Item is

show hide
Genre: Paper

### Files

show Files
hide Files
:
arXiv:1704.08122.pdf (Preprint), 725KB
Name:
arXiv:1704.08122.pdf
Description:
File downloaded from arXiv at 2017-07-04 11:36 Accepted to the 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
-
-

show

### Creators

show
hide
Creators:
Bringmann, Karl1, Author
Dueholm Hansen, Thomas2, Author
Krinninger, Sebastian2, Author
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019
2External Organizations, ou_persistent22

### Content

show
hide
Free keywords: Computer Science, Data Structures and Algorithms, cs.DS
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.

### Details

show
hide
Language(s): eng - English
Dates: 2017-04-262017
Publication Status: Published online
Pages: 19 p.
Publishing info: -
Rev. Method: -
Identifiers: arXiv: 1704.08122
URI: http://arxiv.org/abs/1704.08122
BibTex Citekey: DBLP:journals/corr/BringmannHK17
Degree: -

show

show

show

show