Computational geometric approach to submodular function minimization for multiclass queueing systems

作者：Itoko Toshinari; Iwata Satoru^*

来源：Japan Journal of Industrial and Applied Mathematics, 2012, 29(3): 453-468.

DOI：10.1007/s13160-012-0074-0

• Submodular function
• Multiclass queue
• Arrangement
• Zonotope

This paper presents an efficient algorithm for minimizing a certain class of submodular functions that arise in analysis of multiclass queueing systems. In particular, the algorithm can be used for testing whether a given multiclass M/M/1 achieves an expected performance by an appropriate control policy. With the aid of the topological sweeping method for line arrangement, our algorithm runs in O(n(2)) time, where n is the cardinality of the ground set. This is much faster than direct applications of general submodular function minimization algorithms.

• 出版日期2012