Tight Approximation for Unconstrained XOS Maximization

References

• [1] Badanidiyuru A, Dobzinski S, Oren S (2012) Optimization with demand oracles. Faltings B, Leyton-Brown K, Ipeirotis P, eds. Proc. 13th ACM Conf. Electronic Commerce (Association for Computing Machinery, New York), 110–127.Google Scholar
• [2] Buchbinder N, Feldman M (2018) Deterministic algorithms for submodular maximization problems. ACM Trans. Algorithms 14(3):32.Crossref, Google Scholar
• [3] Buchbinder N, Feldman M, Garg M (2019) Deterministic (1/2 + ε)-approximation for submodular maximization over a matroid. Chan TM, ed. Proc. 30th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 241–254.Google Scholar
• [4] Buchbinder N, Feldman M, Naor J, Schwartz R (2015) A tight linear time (1/2)-approximation for unconstrained submodular maximization. SIAM J. Comput. 44(5):1384–1402.Crossref, Google Scholar
• [5] Calinescu G, Chekuri C, Pál M, Vondrák J (2011) Maximizing a monotone submodular function subject to a matroid constraint. SIAM J. Comput. 40(6):1740–1766.Crossref, Google Scholar
• [6] Feige U (2007) On maximizing welfare when utility functions are subadditive. SIAM J. Comput. 29(1):122–142.Crossref, Google Scholar
• [7] Feige U, Mirrokni VS, Vondrák J (2011) Maximizing non-monotone submodular functions. SIAM J. Comput. 40(4):1133–1153.Crossref, Google Scholar
• [8] Grötschel M, Lovász L, Schrijver A (1981) The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2):169–197.Crossref, Google Scholar
• [9] Grötschel M, Lovász L, Schrijver A (1988) Geometric Algorithms and Combinatorial Optimization (Springer, New York).Crossref, Google Scholar
• [10] Gul F, Stacchetti E (1999) Walrasian equilibrium with gross substitutes. J. Econom. Theory 87(1):95–124.Crossref, Google Scholar
• [11] Iwata S, Fleischer L, Fujishige S (2001) A combinatorial strongly polynomial algorithm for minimizing submodular functions. J. ACM 48(4):761–777.Crossref, Google Scholar
• [12] Knuth DE (1974) The asymptotic number of geometries. J. Combinational Theory Series A 16(3):398–400.Crossref, Google Scholar
• [13] Knuth DE (2005) The Art of Computer Programming, Volume 4, Fascicle 3: Generating all Combinations and Partitions (Addison-Wesley, Boston).Google Scholar
• [14] Kulik A, Shachnai H, Tamir T (2013) Approximations for monotone and nonmonotone submodular maximization with knapsack constraints. Math. Oper. Res. 38(4):729–739.Link, Google Scholar
• [15] Lehmann B, Lehmann D, Nisan N (2006) Combinatorial auctions with decreasing marginal utilities. Games Econom. Behav. 55(2):270–296.Crossref, Google Scholar
• [16] Mirrokni V, Schapira M, Vondrák J (2008) Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions. Gini M, Kauffman RJ, Sarppo D, Dellarocas C, Dignum F, eds. Proc. 9th ACM Conf. Electronic Commerce (Association for Computing Machinery, New York), 70–77.Google Scholar
• [17] Nemhauser GL, Wolsey LA (1978) Best algorithms for approximating the maximum of a submodular set function. Math. Oper. Res. 3(3):177–188.Link, Google Scholar
• [18] Nemhauser GL, Wolsey LA, Fisher ML (1978) An analysis of approximations for maximizing submodular set functions—I. Math. Programming 14(1):265–294.Crossref, Google Scholar
• [19] Oxley JG (2011) Matroid Theory, 2nd ed. (Oxford Univ. Press, UK).Crossref, Google Scholar
• [20] Schrijver A (1998) Theory of Linear and Integer Programming (John Wiley & Sons, Hoboken, NJ).Google Scholar
• [21] Schrijver A (2000) A combinatorial algorithm minimizing submodular functions in strongly polynomial time. J. Combinational Theory Series B 80(2):346–355.Crossref, Google Scholar
• [22] Singer Y (2010) Budget feasible mechanisms. Beame P, Trevisan L, eds. Proc. 51st Annual IEEE Sympos. Foundations Comput. Sci. (IEEE Computer Society, Los Alamitos, CA), 765–774.Google Scholar
• [23] Sviridenko M (2004) A note on maximizing a submodular set function subject to a knapsack constraint. Oper. Res. Lett. 32(1):41–43.Crossref, Google Scholar