Comparing Apples and Oranges: Query Trade-off in Submodular Maximization

References

• Ageev AA, Sviridenko MI (1999) An 0.828 approximation algorithm for the uncapacitated facility location problem. Discrete Appl. Math. 93(2):149–156.Crossref, Google Scholar
• Austrin P, Benabbas S, Georgiou K (2013) Better balance by being biased: A 0.8776-approximation for max bisection. Khanna S, ed. Proc. 24th Annual ACM-SIAM Sympos. Discrete Algorithms, SODA ’12 (SIAM, Philadelphia), 277–294.Crossref, Google Scholar
• Bach F (2013) Learning with submodular functions: A convex optimization perspective. Foundations and Trends in Machine Learn. 6(2–3):145–373.Crossref, 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, SODA ’14 (SIAM, Philadelphia), 1497–1514.Crossref, Google Scholar
• Boykov YY, Jolly MP (2001) Interactive graph cuts for optimal boundary and region segmentation of objects in N-D images. Proc. 8th Internat. Conf Comput. Vision, ICCV ’01, Vol. 1, (IEEE Computer Society, Washington, DC), 105–112.Crossref, Google Scholar
• Brualdi RA (1969) Comments on bases in dependence structures. Bull. Australian Math. Soc. 1(02):161–167.Crossref, Google Scholar
• Buchbinder N, Feldman M, Naor J(S), Schwartz R (2014) Submodular maximization with cardinality constraints. Chekuri C, ed. Proc. 25th Annual ACM-SIAM Sympos. Discrete Algorithms, SODA ’14 (SIAM, Philadelphia), 1433–1452.Crossref, Google Scholar
• Calinescu G, Chekuri C, Pal 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
• Chekuri C, Khanna S (2005) A polynomial time approximation scheme for the multiple knapsack problem. SIAM J. Comput. 35(3):713–728.Crossref, Google Scholar
• Chekuri C, Vondrák J, Zenklusen R (2010) Dependent randomized rounding via exchange properties of combinatorial structures. Proc. 51th Annual IEEE Sympos. Foundations Comput. Sci., FOCS ’10 (IEEE Computer Society, Washington, DC), 575–584.Crossref, Google Scholar
• Cohen R, Katzir L, Raz D (2006) An efficient approximation for the generalized assignment problem. Inform. Processing Lett. 100(4):162–166.Crossref, Google Scholar
• Cornuejols G, Fisher ML, Nemhauser GL (1977) Location of bank accounts to optimize float: An analytic study of exact and approximate algorithms. Management Sci. 23(8):789–810.Link, Google Scholar
• Cornuejols G, Fisher ML, Nemhauser GL (1977) On the uncapacitated location problem. Ann. Discrete Math. 1:163–177.Crossref, Google Scholar
• Doerr B (2011) Analyzing randomized search heuristics: Tools from probability theory. Auger A, Doerr B, eds. Theory of Randomized Search Heuristics (World Scientific Publishing, Singapore), 1–20.Crossref, Google Scholar
• Feige U (1998) A threshold of ln n for approximating set cover. J. ACM 45(4):634–652.Crossref, Google Scholar
• Feige U, Goemans MX (1995) Aproximating the value of two prover proof systems, with applications to max 2sat and max dicut. Proc. 3rd Sympos. Theory Comput. Systems, ISTCS ’95 (IEEE Computer Society, Washington, DC), 182–189.Crossref, Google Scholar
• Feige U, Vondrák J (2006) Approximation algorithms for allocation problems: Improving the factor of 1 − 1/e. Proc. 47th Annual IEEE Sympos. Foundations Comput. Sci., FOCS ’06 (IEEE Computer Society, Washington, DC), 667–676.Crossref, Google Scholar
• Feige U, Mirrokni VS, Vondrák J (2011) Maximizing non-monotone submodular functions. SIAM J. Comput. 40(4):1133–1153.Crossref, Google Scholar
• Feldman M, Naor J(S), Schwartz R (2011) A unified continuous greedy algorithm for submodular maximization. Proc. 52nd Annual IEEE Sympos. Foundations Comput. Sci., FOCS ’11 (IEEE Computer Society, Washington, DC), 570–579.Crossref, Google Scholar
• Fleischer L, Goemans MX, Mirrokni VS, Sviridenko M (2006) Tight approximation algorithms for maximum general assignment problems. Proc. 17th Annual ACM-SIAM Sympos. Discrete Algorithms, SODA ’06 (SIAM, Philadelphia), 611–620.Crossref, Google Scholar
• Frieze AM, Jerrum M (1997) Improved approximation algorithms for MAX k-cut and MAX BISECTION. Algorithmica 18(1):67–81.Crossref, Google Scholar
• Gharan SO, Vondrák J (2011) Submodular maximization by simulated annealing. Randall D, ed. Proc. 22nd Annual ACM-SIAM Sympos. Discrete Algorithms, SODA ’11 (SIAM, Philadelphia), 1098–1117.Crossref, Google Scholar
• Goemans MX, Williamson DP (1995) Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42(6):1115–1145.Crossref, Google Scholar
• Halperin E, Zwick U (2001) Combinatorial approximation algorithms for the maximum directed cut problem. Kosaraju SR, ed. Proc. 12th Annual ACM-SIAM Sympos. Discrete Algorithms, SODA ’12 (SIAM, Philadelphia), 1–7.Google Scholar
• Hartline J, Mirrokni V, Sundararajan M (2008) Optimal marketing strategies over social networks. Proc. 17th Internat. World Wide Web Conf., WWW ’08 (ACM, New York), 189–198.Crossref, Google Scholar
• Hȧstad J (2001) Some optimal inapproximability results. J. ACM 48(4):798–859.Crossref, Google Scholar
• Jegelka S, Bilmes J (2011) Submodularity beyond submodular energies: Coupling edges in graph cuts. Proc. 2011 IEEE Conf. Comput. Vision and Pattern Recognition (IEEE, Piscataway, NJ), 1897–1904.Crossref, Google Scholar
• Karp RM (1972) Reducibility among combinatorial problems. Miller RE, Thatcher JW, eds. Complexity of Computer Computations (Plenum Press, New York), 85–103.Crossref, Google Scholar
• Kempe D, Kleinberg J, 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 (ACM, New York), 137–146.Crossref, Google Scholar
• Khot S, Kindler G, Mossel E, O’Donnell R (2007) Optimal inapproximability results for max-cut and other 2-variable csps? SIAM J. Comput. 37(1):319–357.Crossref, Google Scholar
• Khuller S, Moss A, Naor J (1999) The budgeted maximum coverage problem. Inform. Processing Lett. 70(1):39–45.Crossref, Google Scholar
• Krause A, Guestrin C (2005) Near-optimal nonmyopic value of information in graphical models. Proc. 21st Conf. Uncertainty Artifical Intelligence, UAI ’05 (AUAI Press, Corvallis, OR), 5.Google Scholar
• Krause A, Singh A, Guestrin C (2008) Near-optimal sensor placements in Gaussian processes: Theory, efficient algorithms and empirical studies. J. Mach. Learn. Res. 9:235–284.Google Scholar
• Krause A, Leskovec J, Guestrin C, VanBriesen J, Faloutsos C (2008) Efficient sensor placement optimization for securing large water distribution networks. J. Water Resources Planning and Management 134(6):516–526.Crossref, Google Scholar
• Lin H, Bilmes J (2010) Multi-document summarization via budgeted maximization of submodular functions. Proc. 2010 Annual Conf. North Amer. Chapter Assoc. Computational Linguistics/Human Language Tech. Conf., NAACL/HLT-2010 (Association for Computational Linguistics, Stroudsburg, PA), 912–920.Google Scholar
• Lin H, Bilmes J (2011) A class of submodular functions for document summarization. Proc. 49th Annual Meeting Association for Computational Linguistics: Human Language Technologies, HLT ’11, Vol. 1 (Association for Computational Linguistics, Stroudsburg, PA), 510–520.Google Scholar
• Mirzasoleiman B, Badanidiyuru A, Karbasi A, Vondrák J, Krause A (2015) Lazier than lazy greedy. Proc. 29th AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 1812–1818.Google Scholar
• 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
• 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
• Schrijver A (2003) Combinatorial Optimization: Polyhedra and Eciency (Springer, Berlin).Google Scholar
• Trevisan L, Sorkin GB, Sudan M, Williamson DP (2000) Gadgets, approximation, and linear programming. SIAM J. Comput. 29(6):2074–2097.Crossref, Google Scholar
• Vondrák J (2013) Symmetry and approximability of submodular maximization problems. SIAM J. Comput. 42(1):265–304.Crossref, Google Scholar