A $mlog m$ Algorithm to Compute the Most Probable Configurations of a System With Multi-Mode Independent Components
Antoine B. Rauzy · IEEE Transactions on Reliability · 2005
In this note, we propose a m log m algorithm to find the k most probable configurations of a system of n multi-mode independent components, with at most d modes each. m denotes the size of the problem, i.e. max (nd, k). This problem originates in network performance analyzes, in which focusing on the most probable configurations is a means to reduce computational costs. Up to this note, the best known algorithm to extract the most probable configurations was in O(n/sup 2/d/sup 2/ + k log k). Our algorithm achieves thus a substantial improvement.