  A basic combinatorial online resource allocation problem is considered, where
multiple servers have individual capacity constraints, and at each time slot, a
set of jobs arrives, that have potentially different weights to different
servers. At each time slot, a one-to-one matching has to be found between jobs
and servers, subject to individual capacity constraints, in an online manner.
The objective is to maximize the aggregate weight of jobs allotted to servers,
summed across time slots and servers, subject to individual capacity
constraints. This problem generalizes the well known adwords problem, and is
also relevant for various other modern applications. A simple greedy algorithm
is shown to be 3-competitive, whenever the weight of any edge is at most half
of the corresponding server capacity. Moreover, a randomized version of the
greedy algorithm is shown to be 6-competitive for the unrestricted edge weights
case. For parallel servers with small-weight jobs, we show that a
load-balancing algorithm is near-optimal.
