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 a1,,ana_1,\ldots,a_n and positive integer kk, find non-negative integers x1,,xnx_1,\ldots,x_n, such that ixik\sum_{i} x_i \leq k and θ=maxiai/xi\theta = \max_{i} a_i/x_i is minimized.

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

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

One can also get a O(nlogn)O(n\log n) time algorithm. First compute yi=kaiAy_i = \ceil{k \frac{a_i}{A}}. Greedily find a ii such that ai/yia_i/y_i is maximized, and decrease yiy_i by 11. We stop when we have iyi=k\sum_{i} y_i=k. This takes O(logn)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 iλai=k\sum_{i} \ceil{\lambda a_i} = k. Cheng and Eppstein found a O(n)O(n) time algorithm [1]. Reitzig and Wild found a simpler algorithm later [2].

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

Problem2

Given positive a1,,ana_1,\ldots,a_n and positive integer kk, find non-negative integers x1,,xnx_1,\ldots,x_n, such that ixik\sum_{i} x_i \leq k and θ=maxiai/(xi+1)\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 kk times from given sticks, Algorithmica. (2017) 10.1007/s00453-017-0392-3.

Posted by Chao Xu on .
Tags: optimization, integer.