Anytime Winner Determination Problem

Ploy(3) solutions to winner determination - Convex and Greedy

Winner Determination Problem (WDP) is classically NP complete. The usual approach to solve it using mixed integer linear program (CPLEX). It gives an exact solution. However, CPLEX is excruciatingly slow. We prove that by recasting WDP as L0 minimization; we can use the theory of compressed sensing to propose convex and greedy surrogates (both running in O(n^3)).