Help
Cart
Skip main navigation

Available Issues

February 19, 2019 - May 1, 2026

Available Issues

February 19, 2019 - May 1, 2026

Multiobjective Maximization of Monotone Submodular Functions with Cardinality Constraint

Published Online:10 Dec 2020https://doi.org/10.1287/ijoo.2019.0041

References

  • Arora S, Hazan E, Kale S (2012) The multiplicative weights update method: A meta-algorithm and applications. Theory Comput. 8(1):121–164.Google Scholar
  • Azar Y, Gamzu I (2012) Efficient submodular function maximization under linear packing constraints (ICALP). Czumaj A, Mehlhorn K, Pitts A, Wattenhofer R, eds. Automata, Languages, and Programming (Springer, Berlin, Heidelberg), 38–50.Google Scholar
  • Badanidiyuru A, Vondrák J (2014) Fast algorithms for maximizing submodular functions. Chekuri C, ed. Proc. 25th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 14:1497–1514.Google Scholar
  • Bienstock D (2006) Potential Function Methods for Approximately Solving Linear Programming Problems: Theory and Practice, vol. 53 (Springer, New York).Google Scholar
  • Bogunovic I, Mitrović S, Scarlett J, Cevher V (2017) Robust submodular maximization: A non-uniform partitioning approach. Precup D, Teh YW, eds. Proc. 34th Internat. Conf. Machine Learn., vol. 70, 508–516.Google Scholar
  • Calinescu G, Chekuri C, Pál M, Vondrák J (2007) Maximizing a submodular set function subject to a matroid constraint. Fischetti M, Wiliamson DP, eds. Integer Programming and Combinatorial Optimization (Springer, Berlin, Heidelberg), 7:182–196.Google Scholar
  • 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.Google Scholar
  • Chekuri C, Jayram T, Vondrak J (2015) On multiplicative weight updates for concave and submodular function maximization. Roughgarden T, ed. Proc. 2015 Conf. Innovation Theoret. Comput. Sci. (ACM, New York), 201–210.Google Scholar
  • Chekuri C, Vondrák J, Zenklusen R (2009) Dependent randomized rounding for matroid polytopes and applications. Preprint, submitted September 24, https://arxiv.org/abs/0909.4348.Google Scholar
  • Chekuri C, Vondrák J, Zenklusen R (2010) Dependent randomized rounding via exchange properties of combinatorial structures. Trevisan L, ed. 51st Annual IEEE Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 10:575–584.Google Scholar
  • Chekuri C, Vondrák J, Zenklusen R (2014) Submodular function maximization via the multilinear relaxation and contention resolution schemes. Siam J. Comput. 43(6):1831–1879.Google Scholar
  • Chen RS, Lucier B, Singer Y, Syrgkanis V (2017) Robust optimization for non-convex objectives. Adv. Neural Inform. Processing Systems 31:4705–4714.Google Scholar
  • El-Arini K, Veda G, Shahaf D, Guestrin C (2009) Turning down the noise in the blogosphere. Proc. 15th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining (ACM, New York), 289–298.Google Scholar
  • Feige U (1998) A threshold of ln n for approximating set cover. J. ACM 45(4):634–652.Google Scholar
  • Feldman M, Naor J, Schwartz R (2011) A unified continuous greedy algorithm for submodular maximization. 5nd Annual Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 11:570–579.Google Scholar
  • Fleischer L (2000) Approximating fractional multicommodity flow independent of the number of commodities. SIAM J. Discrete Math. 13(4):505–520.Google Scholar
  • Globerson A, Roweis S (2006) Nightmare at test time: Robust learning by feature deletion. Cohen WW, Moore AW, eds. Proc. 23rd Internat. Conf. Machine Learn. (ACM, New York), 353–360.Google Scholar
  • Grigoriadis M, Khachiyan L (1994) Fast approximation schemes for convex programs with many blocks and coupling constraints. SIAM J. Optim. 4(1):86–107.Google Scholar
  • Guestrin C, Krause A, Singh A (2005) Near-optimal sensor placements in Gaussian processes. Proc. 22nd Internat. Conf. Machine Learn. (ACM, New York), 265–272.Google Scholar
  • He X, Kempe D (2016) Robust influence maximization. Krishnapuram B, Shah M, Smola AJ, Aggarwal CC, Shen D, Rastogi R, eds. Proc. 22nd ACM SIKDD Internat. Conf. Knowledge Discovery Data Mining (ACM, New York), 885–894.Google Scholar
  • Kempe D, Kleinberg J, Tardos É (2015) Maximizing the spread of influence through a social network. Theory Comput. 11:105–147.Google Scholar
  • Krause A, Guestrin C (2005) Near-optimal nonmyopic value of information in graphical models. Proc. 21st Annual Meeting Assoc. Comput. Linguistics: Human Language Tech. (Association for Computational Linguistics), 324–331.Google Scholar
  • Krause A, Guestrin C, Gupta A, Kleinberg J (2006) Near-optimal sensor placements: Maximizing information while minimizing communication cost. Proc. 5th Internat. Conf. Inform. Processing Sensor Networks (ACM, New York), 2–10.Google Scholar
  • Krause A, McMahan HB, Guestrin C, Gupta A (2008a) Robust submodular observation selection. J. Machine Learn. Res. 9:2761–2801.Google Scholar
  • Krause A, Leskovec J, Guestrin C, VanBriesen J, Faloutsos C (2008b) Efficient sensor placement optimization for securing large water distribution networks. J. Water Resource Planning Management 134(6):516–526.Google Scholar
  • Leskovec J, Chakrabarti D, Kleinberg J, Faloutsos C, Ghahramani Z (2010) Kronecker graphs: An approach to modeling networks. J. Machine Learn. Res. 11:985–1042.Google Scholar
  • Leskovec J, Krause A, Guestrin C, Faloutsos C, VanBriesen J, Glance N (2007) Cost-effective outbreak detection in networks. Berkhin P, Caruana R, Wu X, eds. Proc. 13th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining (ACM, New York), 420–429.Google Scholar
  • Lin H, Bilmes J (2011) A class of submodular functions for document summarization. Lin D, Matsumoto Y, Mihalcea R, eds. 49th Annual Meeting Assoc. Comput. Linguistics: Human Language Tech. Proc. (Association for Computational Linguistics), 510–520.Google Scholar
  • Mirzasoleiman B, Badanidiyuru A, Karbasi A, Vondrák J, Krause A (2015) Lazier than Lazy Greedy (AAAI, Palo Alto, CA).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.Google Scholar
  • Orlin JB, Schulz AS, Udwani R (2018) Robust monotone submodular function maximization. Math. Programming 172(1):505–537.Google Scholar
  • Ostfeld A, Uber J, Salomons E, Berry J, Hart PCWE, Watson J, Dorini G, et al.. (2008) The battle of the water sensor networks (BWSN): A design challenge for engineers and algorithms. J. Water Resource Planning Management 134(6):556–568.Google Scholar
  • Papadimitriou C, Yannakakis M (2000) On the approximability of trade-offs and optimal access of web sources. 41st Annual Sympos. Foundations Comput. Sci (IEEE, Piscataway, NJ), 86–92.Google Scholar
  • Plotkin S, Shmoys D, Tardos E (1991) Fast approximation algorithms for fractional packing and covering problems. Math. Oper. Res. 20(2):257–301.Google Scholar
  • Singla A, Bogunovic I (2014) Near-optimally teaching the crowd to classify. Proc. 31st Internat. Conf. Machine Learn. 32:154–162.Google Scholar
  • Thoma M, Cheng H, Gretton A, Han J, Kriegel H, Smola A, Song L, et al.. (2009) Near-optimal supervised feature selection among frequent subgraphs. Thoma M, Cheng H, Han J, Kriegel H, Smola A, Song L, et al., eds. Proc. SIAM Internat. Conf. Data Mining (SIAM, Philadelphia), 1076–1087.Google Scholar
  • Udwani R (2018) Multi-objective maximization of monotone submodular functions with cardinality constraint. Bengio S, Wallach HM, Larochelle H, Grauman K, Cesa-Bianchi N, Garnett R, eds. Adv. Neural Inform. Processing Systems 32:9493–9504.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. (ACM, New York), 67–74.Google Scholar
  • Vondrák J (2010) Submodularity and curvature: The optimal algorithm (combinatorial optimization and discrete algorithms). RIMS Kokyuroku Bessatsu 23:253–266.Google Scholar
  • Vondrák J (2013) Symmetry and approximability of submodular maximization problems. SIAM J. Comput. 42(1):265–304.Google Scholar
  • Young N (1995) Randomized rounding without solving the linear program. Clarkson KL, ed. Proc. 6th Annual ACM-SIAM Sympos. Discrete Algorithms (ACM, New York/SIAM, Philadelphia), 95:170–178.Google Scholar
  • Young NE (2001) Sequential and parallel algorithms for mixed packing and covering. 42nd Annual Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ). 538–546.Google Scholar
Previous
Back to Top
Next
INFORMS site uses cookies to store information on your computer. Some are essential to make our site work; Others help us improve the user experience. By using this site, you consent to the placement of these cookies. Please read our Privacy Statement to learn more.
Agree