The Art Gallery Guardian

Processor distribution and proportional apportionment


I saw an interview problem about assigning identical processors to embarrassingly parallel jobs. The running time of a job equals the running time on a single processor divided by the number of processors. We are interested in minimizing the maximum running time. Formally, we get the following problem.

Problem1

Given positive reals a_1,\ldots,a_n and positive integer k, find non-negative integers x_1,\ldots,x_n, such that \sum_{i} x_i \leq k and \theta = \max_{i} a_i/x_i is minimized.

If there is no integral requirement on x_i's, then the problem is easy. Let A=\sum_{i} a_i. There is a closed solution of x_i = k \frac{a_i}{A}, and \theta = A / k.

Otherwise, it is easy to check if \theta'>0 is a feasible solution. \theta' is feasible iff \sum_{i} \ceil{a_i/\theta'} \leq k. Therefore one can apply binary search, and get the result in O(n\log k) time.

One can also get a O(n\log n) time algorithm. First compute y_i = \ceil{k \frac{a_i}{A}}. Greedily find a i such that a_i/y_i is maximized, and decrease y_i by 1. We stop when we have \sum_{i} y_i=k. This takes O(\log n) per operation using a binary search tree.

Linear time algorithm also exists. It is connected to proportional apportionment. This is the problem of finding the smallest \lambda, such that \sum_{i} \ceil{\lambda a_i} = k. Cheng and Eppstein found a O(n) time algorithm [1]. Reitzig and Wild found a simpler algorithm later [2].

There is a similar interview problem. Given n points on the real line, add k more points, such that it minimizes the maximum length between adjacent points. The problem is the same as the following one.

Problem2

Given positive a_1,\ldots,a_n and positive integer k, find non-negative integers x_1,\ldots,x_n, such that \sum_{i} x_i \leq k and \theta = \max_{i} a_i/(x_i+1) is minimized.

The linear time algorithm for proportional apportionment should also work for the above problem. It is interesting how much can we change the problem before the linear time algorithm no longer works.

References

[1] Z. Cheng, D. Eppstein, Linear-time algorithms for proportional apportionment, in: H.-K. Ahn, C.-S. Shin (Eds.), Algorithms and Computation: 25th International Symposium, Isaac 2014, Jeonju, Korea, December 15-17, 2014, Proceedings, Springer International Publishing, Cham, 2014: pp. 581–592 10.1007/978-3-319-13075-0_46.

[2] R. Reitzig, S. Wild, Building fences straight and high: An optimal algorithm for finding the maximum length you can cut k times from given sticks, Algorithmica. (2017) 10.1007/s00453-017-0392-3.

Posted by Chao Xu on 2016-08-02.
Tags: optimization, integer.