An Inequality for Discrete Convex Hulls and Applications
Hans S. Witsenhausen · SIAM Journal on Applied Mathematics · 1975
For a set S in $R_ + ^n $, let $S_k = \{ {k^{ - 1} \sum _{\alpha = 1}^k x_\alpha | {x_\alpha \in S,\alpha = 1, \cdots ,k} } \}$ be its discrete convex hull of order k. Then the infimum of $\| x \|_\infty $ over $S_k $ cannot exceed the infimum, over the convex hull of k, of $k^{ - 1} \| x \|_1 + ( {1 - k^{ - 1} } )\| x \|_\infty $, and this bound is sharp. One application is the proof of a conjecture of Graham and Garey arising from their work on multiprocessor scheduling. Another application is to two person zero sum games. If the minimizes is restricted to a single use of a random device producing one of k equiprobable outputs, the lowest expected payoff he can guarantee is bounded from above in terms of the value of a game, whose payoff matrix is obtained from the given payoff matrix by multiplication by the matrix $k^{ - 1} E + ( {1 - k^{ - 1} } )I$, where E is the all ones matrix. Another consequence is that for positive integers n, v, k and real $x_\alpha ^i \geqq 0,i = 1, \cdots ,n,\alpha = 1, \cdots , u $, there exist nonnegative integers $m^1 , \cdots m^{ u } $, of which at most n are positive, with $\sum _{\alpha = 1}^{ u } m^\alpha = k$ and there exist real $q_j \geqq 1, j = 1, \cdots ,n$, with $\sum _{j = 1}^n q_j = n + k - 1$ such that for $i = 1, \cdots ,n,\alpha = 1, \cdots , u $,\[ \sum\limits_{\beta = 1}^{ u } {m^\beta x_\beta ^i } \leqq \sum\limits_{j = 1}^n {q_j x_\alpha ^i } . \]