The Generalized Maximum Coverage Problem

We define a new problem called the Generalized Maximum Coverage Problem (GMC). GMC is an extension of the Budgeted Maximum Coverage Problem, and it has important applications in wireless OFDMA scheduling. We use a variation of the greedy algorithm to produce a -approximation for every ε>0, and then use partial enumeration to reduce the approximation ratio to .