Winner Determination by Polynomial Sparse Pursuit: Approximation Guarantees and Certified Optimality Gaps
Winner determination in combinatorial auctions is a weighted set-packing problem and is NP-hard in general. This paper develops a deterministic polynomial-time sparse-pursuit framework that couples the global linear-programming relaxation with CoSaMP-type identify–merge–re-estimate–prune dynamics. The re-estimation step keeps only a logarithmic-size moving window integral while all other bid variables remain fractionally relaxed, so each partially integral … Read more