Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(3)
Binary Search
Experimental Study
Shortest Path
Subscribe
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
Edit
An Experimental Study of Minimum Mean Cycle Algorithms
(
Citations: 5
)
BibTex

RIS

RefWorks
Download
Loukas Georgiadis
,
Andrew V. Goldberg
,
Robert Endre Tarjan
,
Renato Fonseca F. Werneck
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 cyclebased, binary search, and treebased. The first two use an SPF algorithm as a subroutine, while the latter uses a parametric approach. When implementing the SPFbased 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 treebased method and two implementations of the cyclebased method outperformed other approaches, in cluding binary search.
Conference:
Algorithm Engineering and Experimentation  ALENEX
, pp. 113, 2009
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.
(
www.siam.org
)
(
research.microsoft.com
)
(
zeno.siam.org
)
(
www.informatik.unitrier.de
)
(
www.siam.org
)
More »
Citation Context
(2)
...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 Lombardi
,
et 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 Hansen
,
et al.
Lower Bounds for Howard's Algorithm for Finding Minimum MeanCost Cycl...
References
(17)
The Crofting Problem
(
Citations: 307
)
M. Gray
,
Adam Collier
Journal:
Economic History Review  ECON HIST REV
, vol. 7, no. 1, 1954
Adaptive negative cycle detection in dynamic graphs
(
Citations: 6
)
N. Chandrachoodan
,
S. S. Bhattacharyya
,
K. J. Ray Liu
Conference:
IEEE International Symposium on Circuits and Systems  ISCAS
, pp. 163166, 2001
Shortest Path Feasibility Algorithms: An Experimental Evaluation
(
Citations: 3
)
Boris V. Cherkassky
,
Loukas Georgiadis
,
Andrew V. Goldberg
,
Robert Endre Tarjan
,
Renato Fonseca F. Werneck
Journal:
ACM Journal of Experimental Algorithms  JEA
, vol. 14, pp. 118132, 2008
Experimental analysis of the fastest optimum cycle ratio and mean algorithms
(
Citations: 60
)
Ali Dasdan
Journal:
ACM Transactions on Design Automation of Electronic Systems  TODAES
, vol. 9, no. 4, pp. 385418, 2004
Efficient algorithms for optimum cycle mean and optimum cost to time ratio problems
(
Citations: 45
)
Ali Dasdan
,
Sandy S. Irani
,
Rajesh K. Gupta
Conference:
Design Automation Conference  DAC
, pp. 3742, 1999
Sort by:
Citations
(5)
Precedence Constraint Posting for Cyclic Scheduling Problems
Michele Lombardi
,
Alessio Bonfietti
,
Michela Milano
,
Luca Benini
Conference:
International Conference on Integration of AI and OR Techniques in Constraint Programming  CPAIOR
, pp. 137153, 2011
Discounted deterministic Markov decision processes and discounted allpairs shortest paths
(
Citations: 1
)
Omid Madani
,
Mikkel Thorup
,
Uri Zwick
Journal:
ACM Transactions on Algorithms  TALG
, vol. 6, no. 2, pp. 125, 2010
Lower Bounds for Howard's Algorithm for Finding Minimum MeanCost Cycles
Thomas Dueholm Hansen
,
Uri Zwick
Conference:
International Symposium on Algorithms and Computation  ISAAC
, pp. 415426, 2010
Using Strategy Improvement to Stay Alive
Luboš Brim
,
Jakub Chaloupka
Journal:
Electronic Proceedings in Theoretical Computer Science
, vol. 25, pp. 4054, 2010
Shortest Path Feasibility Algorithms: An Experimental Evaluation
(
Citations: 3
)
Boris V. Cherkassky
,
Loukas Georgiadis
,
Andrew V. Goldberg
,
Robert Endre Tarjan
,
Renato Fonseca F. Werneck
Journal:
ACM Journal of Experimental Algorithms  JEA
, vol. 14, pp. 118132, 2008