September 30, 2002

Constraint Programming 2002, Cornell

6

Winner Determination Problem

nEquivalent to weighted set packing

nInput: *m bids
*

nObjective: find
revenue-maximizing non-conflicting
allocation

nEven constant factor
approximation is NP-Hard

nSquare-root
approximation known

nPolynomial in the
number of bids