RhodeCode

@defgroup min_mean_cycle Minimum Mean Cycle Algorithms

@ingroup algs

\brief Algorithms for finding minimum mean cycles.

This group contains the algorithms for finding minimum mean cycles.

The \e minimum \e mean \e cycle \e problem is to find a directed cycle

of minimum mean length (cost) in a digraph.

The mean length of a cycle is the average length of its arcs, i.e. the

ratio between the total length of the cycle and the number of arcs on it.

This problem has an important connection to \e conservative \e length

\e functions, too. A length function on the arcs of a digraph is called

conservative if and only if there is no directed cycle of negative total

length. For an arbitrary length function, the negative of the minimum

cycle mean is the smallest \f$\epsilon\f$ value so that increasing the

arc lengths uniformly by \f$\epsilon\f$ results in a conservative length

function.

LEMON contains three algorithms for solving the minimum mean cycle problem:

- \ref Karp "Karp"'s original algorithm.

- \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved

  version of Karp's algorithm.

- \ref Howard "Howard"'s policy iteration algorithm.

In practice, the Howard algorithm proved to be by far the most efficient

one, though the best known theoretical bound on its running time is

exponential.

Both Karp and HartmannOrlin algorithms run in time O(ne) and use space

O(n<sup>2</sup>+e), but the latter one is typically faster due to the

applied early termination scheme.

*/

/**

/// \ingroup min_mean_cycle

  /// \addtogroup min_mean_cycle

  /// It is an improved version of \ref Karp "Karp"'s original algorithm,

  /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e).

/// \ingroup min_mean_cycle

  /// \addtogroup min_mean_cycle

  /// This class provides the most efficient algorithm for the

  /// minimum mean cycle problem, though the best known theoretical

  /// bound on its running time is exponential.

/// \ingroup min_mean_cycle

  /// \addtogroup min_mean_cycle

  /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e).