This Article Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Saks, M. E. Search for Related Content

A Limit Theorem for (min, +) Matrix Multiplication

Bell Communications Research, 435 South Street, Morristown, New Jersey 07960 and Rutcor/Department of Mathematics, Hill Center for the Mathematical Sciences, Rutgers University, New Brunswick, New Jersey 08903

A natural model for the sequential performance of tasks involves a system that can be configured into any one of a possible set S of states where the cost of performing a given task depends on the state. The cost of processing a sequence of tasks (taken from a set T of possible tasks) is the sum of the costs of performing each task plus the cost incurred by moving between states. A quantity of interest is the supremum over all task sequences of the average cost per task to process the sequence. We answer a question of R. Graham by proving that when the underlying costs are integral this supremum is rational.

Key Words: matrices; integer valued; sequential tasks; scheduling