Suppose we want to assign $n$ items to $m$ customers ($n \geq m$). Each assignment of an item $i$ to a customer $j$ has an associated cost $c(i,j)$. Find an assignment that maximizes the total cost. Here, we must assign every item; therefore, a customer might receive more than one item. Moreover, we require that each customer must receive at least one item.
This can be modeled as an integer linear program. However, I wonder whether there might be a better approach, namely, a polynomial algorithm. Note that if we do not require that each customer must receive at least one item, then we just assign each item to the customer with the maximum cost. Does anyone have any idea?
