Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature

References

• Ageev A, Sviridenko M (2004) Pipage rounding: A new method of constructing algorithms with proven performance guarantee. J. Combinatorial Optim. 8(3):307–328.Crossref, Google Scholar
• Alon N, Spencer JH (2000) The Probabilistic Method, 2nd ed. (John Wiley & Sons, New York).Crossref, Google Scholar
• Boutsidis C, Drineas P, Magdon-Ismail M (2014) Near-optimal column-based matrix reconstruction. SIAM J. Comput. 43(2):687–717.Crossref, Google Scholar
• Brualdi RA (1969) Comments on bases in dependence structures. Bull. Australian Math. Soc. 1(02):161–167.Crossref, Google Scholar
• Calinescu G, Chekuri C, Pál M, Vondrák J (2007) Maximizing a submodular set function subject to a matroid constraint (extended abstract). Fischetti M, Williamson DP, eds. Proc. 12th Internat. Conf. Integer Programming Combinatorial Optimization, IPCO, ’07 (Springer, Berlin), 182–196.Crossref, Google Scholar
• Calinescu G, Chekuri C, Pál M, Vondrák J (2011) Maximizing a submodular set function subject to a matroid constraint. SIAM J. Comput. 40(6):1740–1766.Crossref, Google Scholar
• Çivril A, Magdon-Ismail M (2009) On selecting a maximum volume sub-matrix of a matrix and related problems. Theoret. Comput. Sci. 410(47–49):4801–4811.Crossref, Google Scholar
• Chekuri C, Vondrák J, Zenklusen R (2010) Dependent randomized rounding via exchange properties of combinatorial structures. Proc. 51st Annual IEEE Sympos. Foundations Comput. Sci., FOCS ’10 (IEEE Computer Society, Washington, DC), 575–584.Crossref, Google Scholar
• Chekuri C, Vondrák J, Zenklusen R (2011a) Multi-budgeted matchings and matroid intersection via dependent rounding. Randall D, ed. Proc. 22nd Annual ACM-SIAM Sympo. Discrete Algorithms, SODA ’11 (SIAM, Philadelphia), 1080–1097.Crossref, Google Scholar
• Chekuri C, Vondrák J, Zenklusen R (2011b) Submodular function maximization via the multilinear relaxation and contention resolution schemes. Fortnow L, Vadhan SP, ed. Proc. 43rd ACM Sympos. Theory Comput., STOC ’11 (ACM, New York), 783–792.Google Scholar
• Conforti M, Cornuéjols G (1984) Submodular set functions, matroids and the greedy algorithm: Tight worst-case bounds and some generalizations of the Rado-Edmonds theorem. Discrete Appl. Math. 7(3):251–274.Crossref, Google Scholar
• Deshpande A, Rademacher L (2010) Efficient volume sampling for row/column subset selection. Proc. 51st Annual IEEE Sympos. Foundations Comput. Sci., FOCS ’10 (IEEE Computer Society, Washington, DC), 329–338.Crossref, Google Scholar
• Deshpande A, Vempala S (2006) Adaptive sampling and fast low-rank matrix approximation. Diaz J, Jansen K, Rolim JDP, Zwick U, eds. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Springer, Berlin), 292–303.Crossref, Google Scholar
• Dobzinski S, Schapira M (2006) An improved approximation algorithm for combinatorial auctions with submodular bidders. Proc. Seventeenth Annual ACM-SIAM Sympos. Discrete Algorithms, SODA ’06 (ACM, New York), 1064–1073.Crossref, Google Scholar
• Dobzinski S, Nisan N, Schapira M (2005) Gabow HN, Fagin R, eds. Approximation algorithms for combinatorial auctions with complement-free bidders. Proc. 37th Annual ACM Sympos. Theory Comput., STOC ’05 (ACM, New York), 610–618.Crossref, Google Scholar
• Edmonds J (1971) Matroids and the greedy algorithm. Math. Programming 1(1):127–136.Crossref, Google Scholar
• Feige U (1998) A threshold of ln n for approximating set cover. J. ACM 45(4):634–652.Crossref, Google Scholar
• Feldman M, Naor JS, Schwartz R (2011) Ostrovsky R, ed. A unified continuous greedy algorithm for submodular maximization. Proc. IEEE 52nd Annual Sympos. Foundation Comput. Sci., FOCS ’11 (IEEE Computer Society, Washington, DC), 570–579.Crossref, Google Scholar
• Filmus Y, Ward J (2014) Monotone submodular maximization over a matroid via non-oblivious local search. SIAM J. Comput. 43(2):514–542.Crossref, Google Scholar
• Fisher M, Nemhauser G, Wolsey L (1978) An analysis of approximations for maximizing submodular set functions—II. Balinski M, Hoffman AJ, eds. Polyhedral Combinatorics. Mathematical Programming Studies, 8 (Springer, Berlin), 73–87.Crossref, Google Scholar
• Goel G, Karande C, Tripathi P, Wang L (2009) Approximability of combinatorial problems with multi-agent submodular cost functions. Proc. 50th Annual IEEE Sympos. Foundationi Comput. Sci., FOCS ’09 (IEEE Computer Society, Washington, DC), 755–764.Crossref, Google Scholar
• Il’ev VP (2001) An approximation guarantee of the greedy descent algorithm for minimizing a supermodular set function. Discrete Appl. Math. 114(1–3):131–146.Crossref, Google Scholar
• Iyer R, Jegelka S, Bilmes J (2013) Curvature and optimal algorithms for learning and minimizing submodular functions. Advances in Neural Information Processing Systems 26 (NIPS 2013), Lake Tahoe, CA, 2742–2750.Google Scholar
• Kelmans A (1983) Multiplicative submodularity of a matrix’s principal minor as a function of the set of its rows. Discrete Math. 44(1):113–116.Crossref, Google Scholar
• Kempe D, Kleinberg JM, Tardos É (2003) Maximizing the spread of influence through a social network. Getoor L, Senator TE, Domingos PM, Faloutsos C, eds. Proc. 9th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining, KDD ’03 (ACM, New York), 137–146.Crossref, Google Scholar
• Ko C, Lee J, Queyranne M (1996) An exact algorithm for maximum entropy sampling. Oper. Res. 43(4):684–691.Link, Google Scholar
• Krause A, Guestrin C (2011) Submodularity and its applications in optimized information gathering. ACM Trans. Intelligent Systems Tech. 2(4):Article 32.Crossref, Google Scholar
• Krause A, Singh A, Guestrin C (2008) Near-optimal sensor placements in Gaussian processes: Theory, efficient algorithms and empirical studies. J. Machine Learn. Res. 9:235–284.Google Scholar
• Krause A, Guestrin C, Gupta A, Kleinberg J (2006) Near-optimal sensor placements: Maximizing information while minimizing communication cost. Stankovic JA, Gibbons PB, Wicker ST, Paradiso JA, eds. Proc. 5th Internat. Conf. Inform. Processing Sensor Networks, IPSN ’06 (ACM, New York), 2–10.Crossref, Google Scholar
• Krause A, Rajagopal R, Gupta A, Guestrin C (2009) Simultaneous placement and scheduling of sensors. Proc. 8th Internat. Conf. Inform. Processing Sensor Networks, IPSN ’09 (ACM, New York), 181–192.Google Scholar
• Lee J (2002) Maximum entropy sampling. El-Shaarawi AH, Piegorsch WW, eds. Encyclopedia of Environmetrics, Vol. 3, (John Wiley & Sons, Chichester, UK), 1229–1234.Google Scholar
• Lehmann B, Lehmann DJ, Nisan N (2006) Combinatorial auctions with decreasing marginal utilities. Games Econom. Behav. 55(2):1884–1899.Crossref, Google Scholar
• Mirrokni VS, Schapira M, Vondrák J (2008) Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions. Fortnow L, Riedl J, Sandholm T, eds. Proc. 9th ACM Conf. Electronic Commerce, EC ’08 (ACM, New York), 70–77.Crossref, Google Scholar
• Nemhauser G, Wolsey L (1978) Best algorithms for approximating the maximum of a submodular set function. Math. Oper. Res. 3(3):177–188.Link, Google Scholar
• Nemhauser G, Wolsey L, Fisher M (1978) An analysis of approximations for maximizing submodular set functions—I. Math. Programming 14(1):265–294.Crossref, Google Scholar
• Nikolov A (2015) Randomized rounding for the largest simplex problem. Servedio RA, Rubinfeld R, eds. Proc. 47th Annual ACM Sympos. Theory Comput., STOC ’15 (ACM, New York), 861–870.Crossref, Google Scholar
• Panconesi A, Srinivasan A (1997) Randomized distributed edge coloring via an extension of the Chernoff-Hoeffding bounds. SIAM J. Comput. 26(2):350–368.Crossref, Google Scholar
• Schrijver A (2003) Combinatorial Optimization: Polyhedra and Efficiency (Springer, Berlin).Google Scholar
• Summa MD, Eisenbrand F, Faenza Y, Moldenhauer C (2015) On largest volume simplices and sub-determinants. Indyk P, ed. Proc. 26th Annual ACM-SIAM Sympos. Discrete Algorithms, SODA ’15 (SIAM, Philadelphia), 315–323.Crossref, Google Scholar
• Vondrák J (2008) Optimal approximation for the submodular welfare problem in the value oracle model. Dwork C, ed. Proc. 40th Annual ACM Sympos. Theory Comput., STOC ’08 (ACM, New York), 67–74.Crossref, Google Scholar
• Vondrák J (2010) Submodularity and curvature: The optimal algorithm. Iwata S, ed. RIMS Kokyuroku Bessatsu, Vol. B23 (Kyoto University, Kyoto, Japan), 253–266.Google Scholar