A. Skumanich
SPIE OE/LASE 1992
We consider the following allocation problem arising in the setting of combinatorial auctions: a set of goods is to be allocated to a set of players so as to maximize the sum of the utilities of the players (i.e., the social welfare). In the case when the utility of each player is a monotone submodular function, we prove that there is no polynomial time approximation algorithm which approximates the maximum social welfare by a factor better than 1-1/e≃0.632, unless P=NP. Our result is based on a reduction from a multi-prover proof system for MAX-3-COLORING. © 2007 Springer Science+Business Media, LLC.
A. Skumanich
SPIE OE/LASE 1992
Alfred K. Wong, Antoinette F. Molless, et al.
SPIE Advanced Lithography 2000
Ronen Feldman, Martin Charles Golumbic
Ann. Math. Artif. Intell.
Ziv Bar-Yossef, T.S. Jayram, et al.
Journal of Computer and System Sciences