Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Wednesday, February 22, 2006, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Satoru Iwata (Tokyo University)
In this talk, we present 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 system achieves a required average performance by an appropriate control policy. With the aid of the topological sweeping method for line arrangement, our algorithm runs in O(n2) time, where n is the cardinality of the ground set. This is much faster than direct applications of general submodular function minimization algorithms.
This is a joint work with Toshinari Itoko.
Automatic MiSe System Software Version 1.4803M | admin login