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 equals the running time on a single processor divided by the number of processors thrown in, and we are interested in minimizing the maximum running time. Formally, we get the following nice problem.

Problem1

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\) 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's easy to check if \(\theta'>0\) is a feasible solution. \(\theta'\) is feasible iff \(\sum_{i} \lceil a_i/\theta' \rceil \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, by first compute \(y_i = \lceil k \frac{a_i}{A} \rceil\). Greedily find \(i\) such that \(a_i/y_i\) is maximized, and decrease \(y_i\) by \(1\). Until we have \(\sum_{i} y_i=k\). This can be supported in \(O(\log n)\) per operation using a binary search tree.

Linear time is possible by seeing the connection to proportional apportionment. This is the problem of finding \(\lambda\), such that \(\sum_{i} \lceil \lambda a_i \rceil = k\). The problem can be shown to be solvable in \(O(n)\) time using [1], and later a simpler algorithm[2].

There are also similar problems common in interviews. Given \(n\) points on the real line, one can 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.

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] S. Wild, R. Reitzig, A simple and fast linear-time algorithm for proportional apportionment, CoRR. abs/1504.06475 (2015).

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