A Fast Selection Algorithm and the Problem of Optimum Distribution of Effort
Zvi Galil, Nimrod Megiddo · Journal of the ACM · 1979
An algonthm ,s developed which finds the nth largest element of a linearly ordered set S, given m the form of m patrwise disjoint subsets Each of the m subsets satisfies the property that its kth largest element can be computed m a constant amount of time The algorithm terminates m time O(m.log2([Sj/m))The selection algorithm applies to the problem of optimum distribution of effort, namely, the maxun~zation of the total utility of allocating n persons to m activities, where the utlhty of k persons assigned to actwity j ~s a concave funcuon uAk) Consequently, this problem can be solved m time O(m.logZn)