First, for the sake of notation, suppose a finite set A, where A is a set of real numbers. Then the function f(A) is defined as the sum of all the elements in A. Then here's the following problem.

I have a set X = {x_1, x_2, ..., x_n}, where x_i is a real number in (0,1], and I want to partition X into C_1, C_2, ...., C_m such that f(C_i) is a real number in (0,1] for all i <= m, and m is as small as possible.

I believe there is no polynomial-time algorithm for solving this problem exactly. So I have to design a greedy that approximates the solution (desired: 2-approximation)

So I came up with the following greedy algorithm. Consider x_1,x_2,...,x_n in any arbitrary, fixed order. Then the natural thing to do (in a greedy manner) is to fill C_1 as much as possible (until f(C_1) is greater than 1), and then we move onto C_2 and do the same, and so on. You continue until every element in X is assigned. Suppose C_1, C_2,..., C_k is returned by the algorithm, and I want to know how large k could be.

First, it's easy to see that k is at least f(X), which is the sum of all the elements in X. But I have difficulty deriving an upper bound on k (desired: 2 * f(X), and hence this is going to prove that the algorithm is 2-approximation). Any key insight on how to derive the upper bound would be greatly appreciated.

Edit: I realized that that there are at least k-1 C_i such that |C_i| >= 1/2. This observation led to an upper bound opt >= 2*k!

  • $\begingroup$ It's not true that there are at least $k-1$ many bits which are at least half full. Consider the sequence $\epsilon,1,\epsilon,1,\ldots$. $\endgroup$ – Yuval Filmus Nov 23 '17 at 10:19
  • $\begingroup$ Yea I agree. So I changed my algorithm slightly. So in every iteration I scan through the array of "partially packed" C_i and if a number can fit in any of those sets, I put it in. Otherwise, create a new set and put it in. $\endgroup$ – Ted Nov 23 '17 at 14:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.