The Submodular Welfare Problem with Demand Queries

by Uriel Feige and Jan Vondrák

Theory of Computing, Volume 6(11), pp. 247-290, 2010

Bibliography with links to cited articles

[1]   Steven J. Brams and Alan D. Taylor: Fair division: From cake-cutting to dispute resolution. Cambridge University Press, 1996.

[2]   Gruia Calinescu, Chandra Chekuri, Martin Pál, and Jan Vondrák: Maximizing a submodular set function subject to a matroid constraint. In Proc. 12th Intern. Conf. Integer Program. Comb. Opt. (IPCO), volume 4513 of LNCS, pp. 182–196. Springer, 2007. [doi:10.1007/978-3-540-72792-7_15]

[3]   Deeparnab Chakrabarty and Gagan Goel: On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and GAP. SIAM J. Comput., 39(6):2189–2211, 2010. Preliminary version appeared in Proc. 49th FOCS, 2008. [doi:10.1137/080735503]

[4]   Shahar Dobzinski, Noam Nisan, and Michael Schapira: Approximation algorithms for combinatorial auctions with complement-free bidders. Math. Oper. Res., 35(1):1–13, 2010. Preliminary version appeared in Proc. 37th STOC, 2005. [doi:10.1287/moor.1090.0436]

[5]   Shahar Dobzinski and Michael Schapira: An improved approximation algorithm for combinatorial auctions with submodular bidders. In Proc. 17th SODA, pp. 1064–1073, 2006. [doi:10.1145/1109557.1109675]

[6]   Uriel Feige: A threshold of lnn for approximating set cover. J. ACM, 45(4):634–652, 1998. [doi:10.1145/285055.285059]

[7]   Uriel Feige: Maximizing social welfare when utility functions are subadditive. In Proc. 38th STOC, pp. 41–50. ACM Press, 2006. [doi:10.1145/285055.285059]

[8]   Uriel Feige, Magnus Halldorsson, Guy Kortsarz, and Aravind Srinivasan: Approximating the domatic number. SIAM J. Comput., 32(1):172–195, 2002. [doi:10.1137/S0097539700380754]

[9]   Uriel Feige and Jan Vondrák: Approximation algorithms for combinatorial allocation problems: Improving the factor of 1 - 1e. In Proc. 47th FOCS, pp. 667–676. IEEE Comp. Soc. Press, 2006. [doi:10.1109/FOCS.2006.14]

[10]   Marshall L. Fisher, George L. Nemhauser, and Lawrence A. Wolsey: An analysis of approximations for maximizing submodular set functions—II. Math. Program. Stud., 8:73–87, 1978. [doi:10.1007/BFb0121195]

[11]   Johan Håstad: Clique is hard to approximate within n to the power 1 - ϵ. Acta Math., 182(1):105–142, 1999. [doi:10.1007/BF02392825]

[12]   Elad Hazan, Shmuel Safra, and Oded Schwartz: On the complexity of approximating k-dimensional matching. In Proc. 6th Intern. Workshop Approx. Algorithms for Comb. Opt. (APPROX), volume 2764 of LNCS, pp. 83–97. Springer, 2003. [doi:10.1007/978-3-540-45198-3_8]

[13]   Subhash Khot, Richard Lipton, Evangelos Markakis, and Aranyak Mehta: Inapproximability results for combinatorial auctions with submodular utility functions. Algorithmica, 52(1):3–18, 2008. Preliminary version appeared in Proc. 1st Intern. Workshop Internet and Network Economics (WINE), 2005. [doi:10.1007/s00453-007-9105-7]

[14]   Benny Lehmann, Daniel Lehmann, and Noam Nisan: Combinatorial auctions with decreasing marginal utilities. Games Econom. Behav., 55(2):270–296, 2006. Preliminary version appeared in Proc. Conf. Electron. Commerce 2001. [doi:10.1016/j.geb.2005.02.006]

[15]   Carsten Lund and Mihalis Yannakakis: On the hardness of approximating minimization problems. J. ACM, 41(5):960–981, 1994. [doi:10.1145/185675.306789]

[16]   Noam Nisan and Ilya Segal: The communication requirements of efficient allocations and supporting prices. J. Econom. Theory, 129(1):192–224, 2006. [doi:10.1016/j.jet.2004.10.007]

[17]   Tuomas Sandholm: Algorithm for optimal winner determination in combinatorial auctions. Artificial Intelligence, 135:1–54, 2002. [doi:10.1016/S0004-3702(01)00159-X]

[18]   Jan Vondrák: Submodularity in combinatorial optimization. PhD thesis, Charles University, Prague, Czech republic, 2007.

[19]   Jan Vondrák: Optimal approximation for the submodular welfare problem in the value oracle model. In Proc. 40th STOC, pp. 67–74. ACM Press, 2008. [doi:10.1145/1374376.1374389]