September 30, 2002
Constraint Programming 2002, Cornell
6
Winner Determination Problem
n
Equivalent to weighted set packing
n
Input:
m bids
n
Objective: find revenue-maximizing non-
conflicting allocation
n
n
n
n
n
n
n
n
Even constant factor approximation is
NP
-Hard
n
Square-root approximation known
n
Polynomial in the number of bids