Motivated by the problem of centralized market clearing in a market with probabilistic supply and demand, we introduce the Stochastic Packing-Market Planning problem (SPMP), which is a stochastic generalization of the Maximum k-Set Packing problem. We provide an O(k) approximation algorithm for SPMP, as well as a O(k) approximation mechanism that is truthful in expectation. This matches up to constants the best approximation ratio known for Maximum k-Set Packing. Along the way, we develop techniques for obtaining sparse subhypergraphs of an input hypergraph that preserves Ep(•) up to an O(k) factor, where Ep(G) measures the expected weight of a maximum weight set packing in a random subhypergraph of G. We also give a linear programming based approximation for Ep(G). These techniques may be of independent interest.>>> af++
US9616247B2
. 2017-04-11
