@inproceedings{de08eda1f8604c728b6e5dde66f7fd63,

title = "Inapproximability results for combinatorial auctions with submodular utility functions",

abstract = "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.",

author = "Subhash Khot and Lipton, {Richard J.} and Evangelos Markakis and Aranyak Mehta",

year = "2005",

doi = "10.1007/11600930_10",

language = "English (US)",

isbn = "3540309004",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "92--101",

booktitle = "Internet and Network Economics - First International Workshop, WINE 2005, Proceedings",

note = "1st International Workshop on Internet and Network Economics, WINE 2005 ; Conference date: 15-12-2005 Through 17-12-2005",

}