Computational geometric approach to submodular function minimization for multiclass queueing systems
Computational geometric approach to submodular function minimization for multiclass queueing systems
复制标题
多类排队系统子模函数最小化的计算几何方法
DOI：
10.1007/s13160-012-0074-0
复制
发表时间：
2012
影响因子：
0.9
通讯作者：
T. Itoko and S. Iwata
中科院分区：
文献类型：
--
作者：
田村元秀、西川淳、オリビエギヨン、小久保英一郎、芝井広、深川美里、村上浩、中川貴雄、片坐宏一、塩谷圭吾、馬場直志、村上尚史;他;T. Itoko and S. Iwata
本文提出了一个有效的算法，以最小化一类子模函数，出现在多类嵌入系统的分析。特别地，该算法可以用于测试给定的多类M/M/1是否通过适当的控制策略达到预期的性能。借助于拓扑扫描法进行直线排列，算法的时间复杂度为O（n2），其中基集的基数为.这比直接应用一般的次模函数最小化算法要快得多。
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 inO(n2) time, wherenis the cardinality of the ground set. This is much faster than direct applications of general submodular function minimization algorithms.