Heng Cao, Haifeng Xi, et al.
WSC 2003
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.
Heng Cao, Haifeng Xi, et al.
WSC 2003
Jaione Tirapu Azpiroz, Alan E. Rosenbluth, et al.
SPIE Photomask Technology + EUV Lithography 2009
T. Graham, A. Afzali, et al.
Microlithography 2000
M. Tismenetsky
International Journal of Computer Mathematics