  Group-buying websites represented by Groupon.com are very popular in
electronic commerce and online shopping nowadays. They have multiple slots to
provide deals with significant discounts to their visitors every day. The
current user traffic allocation mostly relies on human decisions. We study the
problem of automatically allocating the user traffic of a group-buying website
to different deals to maximize the total revenue and refer to it as the
Group-buying Allocation Problem (\GAP). The key challenge of \GAP\ is how to
handle the tipping point (lower bound) and the purchase limit (upper bound) of
each deal. We formulate \GAP\ as a knapsack-like problem with variable-sized
items and majorization constraints. Our main results for \GAP\ can be
summarized as follows. (1) We first show that for a special case of \GAP, in
which the lower bound equals the upper bound for each deal, there is a simple
dynamic programming-based algorithm that can find an optimal allocation in
pseudo-polynomial time. (2) The general case of \GAP\ is much more difficult
than the special case. To solve the problem, we first discover several
structural properties of the optimal allocation, and then design a two-layer
dynamic programming-based algorithm leveraging those properties. This algorithm
can find an optimal allocation in pseudo-polynomial time. (3) We convert the
two-layer dynamic programming based algorithm to a fully polynomial time
approximation scheme (FPTAS), using the technique developed in
\cite{ibarra1975fast}, combined with some careful modifications of the dynamic
programs. Besides these results, we further investigate some natural
generalizations of \GAP, and propose effective algorithms.
