Algorithm solves linear weighted cycle minimum mean problem efficiently
An Algorithm for Linear Parametric Minimum Cycle Mean Problem
Discrete Mathematics
Summary
Some problems involve finding the cycle in a network that has the smallest average cost per step. This paper studies a version where those costs change based on a parameter. The authors developed an algorithm that can find these minimum cycle means faster and handle the changing costs. Their method also helps compute special mathematical properties of so-called tropical matrices, which are related to this problem.
What this means in practice
- •For network schedulers: Optimize schedules in systems where edge costs change linearly over time using a practical algorithm for minimum cycle mean problems.
- •For control system engineers: Analyze discrete event systems with time-varying parameters by computing exact minimum cycle means efficiently.
Authors
Yuki Nishida
Abstract
The minimum cycle mean problem (MCM) on weighted digraphs is the problem of finding the minimum value of the cycle mean, that is, the ratio of the cost to the length, over all cycles. Despite its wide range of applications to discrete event systems, the parametric counterpart of the MCM has received relatively little attention in the literature, unlike other parametric problems in network optimization. In this paper, we consider the linear parametric MCM, where all edges $e$ have cost $a(e)-b(e)t$ with parameter $t$. We propose an algorithm to solve the linear parametric MCM in $O((m+n\log n)n^2W)$ time, where $n$ is the number of vertices, $m$ is the number of edges, and $W$ is the maximum absolute value of the coefficients $b(e) \in \mathbb{Z}$. The central technique of the proposed method is the algorithm for the parametric shortest path problem. The MCM is closely related to spectral theory in the tropical semiring, where the ``$\min$'' operation is regarded as addition and ``$+$'' as multiplication. By exploiting the connection between them, we provide a method to compute the eigenvalues and eigenvectors of tropical parametric matrices.