Amir Ali Ahmadi, Raphaël M. Jungers, et al.
SICON
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.
Amir Ali Ahmadi, Raphaël M. Jungers, et al.
SICON
Shu Tezuka
WSC 1991
Jianke Yang, Robin Walters, et al.
ICML 2023
Ziv Bar-Yossef, T.S. Jayram, et al.
Journal of Computer and System Sciences