Academic
Publications
An Experimental Study of Minimum Mean Cycle Algorithms

An Experimental Study of Minimum Mean Cycle Algorithms,Loukas Georgiadis,Andrew V. Goldberg,Robert Endre Tarjan,Renato Fonseca F. Werneck

An Experimental Study of Minimum Mean Cycle Algorithms   (Citations: 5)
BibTex | RIS | RefWorks Download
We study algorithms for the minimum mean cycle prob- lem, a parametric version of shortest path feasibility (SPF). The three basic approaches to the problem are cycle-based, binary search, and tree-based. The first two use an SPF algorithm as a subroutine, while the latter uses a parametric approach. When implementing the SPF-based methods, one has a choice of SPF algo- rithms and incremental optimization strategies. There are also several ways to handle precision issues. This leads to dozens of variants, which we systematically compare. Our experimental setup is more compre- hensive than in previous studies. In our experiments, the tree-based method and two implementations of the cycle-based method outperformed other approaches, in- cluding binary search.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...the MCR value can be computed in polynomial time by means of specialized algorithms [7,12]; for a graph with n nodes and m arcs the typical runtime is O(nm log n )o r worse...
    • ...It is however more common (and efficient) to use dedicated MCR computation algorithms (see [16,12,7])...
    • ...Our MCR algorithm is a variant of the cycle class, as described in [12]...

    Michele Lombardiet al. Precedence Constraint Posting for Cyclic Scheduling Problems

    • ...A more thorough experimental study of MMCC algorithms was recently conducted by Georgiadis et al. [8]...
    • ...1 Georgiadis et al. [8] claim that Howard’s algorithm is not robust...
    • ...conversations with the authors of [8] it turns out, however, that the version they used is substantially different from Howard’s algorithm [11]...

    Thomas Dueholm Hansenet al. Lower Bounds for Howard's Algorithm for Finding Minimum Mean-Cost Cycl...

Sort by: