@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",
}