Constrained Submodular Maximization via a Nonsymmetric Technique

References

• [1] Ageev AA, Sviridenko MI (1999) An 0.828 approximation algorithm for the uncapacitated facility location problem. Discrete Appl. Math. 93(2/3):149–156.Crossref, Google Scholar
• [2] Alon N, Spencer JH (2000) The Probabilistic Method, 2nd ed. (John Wiley & Sons, Hoboken, NJ).Crossref, Google Scholar
• [3] Austrin P, Benabbas S, Georgiou K (2016) Better balance by being biased: A 0.8776-approximation for max bisection. ACM Trans. Algorithms 13(1):2.Crossref, Google Scholar
• [4] Bach F (2013) Learning with submodular functions: A convex optimization perspective. Foundations Trends Machine Learn. 6(2/3):145–373.Crossref, Google Scholar
• [5] Boykov YY, Jolly MP (2001) Interactive graph cuts for optimal boundary & region segmentation of objects in N-D images. Proc. 8th IEEE Internat. Conf. Comput. Vision, vol. 1 (IEEE, Piscataway, NJ), 105–112.Crossref, Google Scholar
• [6] 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
• [7] Buchbinder N, Feldman M, Naor JS, Schwartz R (2014) Submodular maximization with cardinality constraints. Proc. 25th Annual ACM-SIAM Sympos. Discrete Algorithms, Portland, Oregon, 1433–1452.Crossref, Google Scholar
• [8] Călinescu 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
• [9] Chekuri C, Ene A (2011) Approximation algorithms for submodular multiway partition. IEEE 52nd Annual Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 807–816.Crossref, Google Scholar
• [10] 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
• [11] Chekuri C, Vondrák J, Zenklusen R (2010) Dependent randomized rounding via exchange properties of combinatorial structures. IEEE 51st Annual Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 575–584.Crossref, Google Scholar
• [12] 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.Crossref, Google Scholar
• [13] 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
• [14] 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
• [15] 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
• [16] Cornuejols G, Fisher ML, Nemhauser GL (1977) On the uncapacitated location problem. Ann. Discrete Math. 1:163–177.Crossref, Google Scholar
• [17] Ene A, Nguyen HL (2016) Constrained submodular maximization: Beyond 1/e. Proc. 57th Annual Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 248–257.Crossref, Google Scholar
• [18] Feige U (1998) A threshold of ln⁡n for approximating set cover. J. ACM 45(4):634–652.Crossref, Google Scholar
• [19] Feige U, Goemans MX (1995) Approximating the value of two power proof systems, with applications to MAX 2SAT and MAX DICUT. Proc. 3rd Israel Sympos. Theory Comput. Systems (IEEE, Piscataway, NJ), 182–189.Crossref, Google Scholar
• [20] Feige U, Vondrák J (2006) Approximation algorithms for allocation problems: Improving the factor of 1–1/e. 47th Annual IEEE Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 667–676.Crossref, Google Scholar
• [21] Feige U, Mirrokni VS, Vondrák J (2011) Maximizing non-monotone submodular functions. SIAM J. Comput. 40(4):1133–1153.Crossref, Google Scholar
• [22] Feldman M (2013) Maximization problems with submodular objective functions. Unpublished PhD thesis, Technion–Israel Institute of Technology, Haifa, Israel.Google Scholar
• [23] Feldman M, Naor J, Schwartz R (2011) A unified continuous greedy algorithm for submodular maximization. Proc. 52nd Annual Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 570–579.Crossref, Google Scholar
• [24] Feldman M, Naor JS, Schwartz R, Ward J (2011) Improved approximations for k-exchange systems. Demetrescu C, Halldórsson MM, eds. Algorithms—ESA 2011: Proc. 19th Annual European Sympos., Lecture Notes in Computer Science, vol. 6942 (Springer, Berlin), 784–798.Google Scholar
• [25] Fisher ML, Nemhauser GL, Wolsey LA (1978) An analysis of approximations for maximizing submodular set functions–II. Polyhedral Combinatorics, Mathematical Programming Studies, vol. 8 (Springer, Berlin), 73–87.Crossref, Google Scholar
• [26] 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 (Society for Industrial and Applied Mathematics, Philadelphia), 611–620.Crossref, Google Scholar
• [27] Frieze AM, Jerrum M (1995) Improved approximation algorithms for MAX k-CUT and MAX BISECTION. Balas E, Clausen J, eds. Proc. 18th Internat. Conf. Integer Program. Combinatorial Optimization, Lecture Notes in Computer Science, vol. 920 (Springer, Berlin), 1–13.Google Scholar
• [28] Gharan SO, Vondrák J (2011) Submodular maximization by simulated annealing. Proc. 22nd Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1098–1117.Crossref, Google Scholar
• [29] 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
• [30] Grötschel M, Lovász L, Schrijver A (1981) The ellipsoid method and its consequences in combinatorial optimization. Combinatoria 1(2):169–197.Crossref, Google Scholar
• [31] Halperin E, Zwick U (2001) Combinatorial approximation algorithms for the maximum directed cut problem. Proc. 12th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1–7.Google Scholar
• [32] Hartline J, Mirrokni V, Sundararajan M (2008) Optimal marketing strategies over social networks. Proc. 17th Internat. Conf. World Wide Web (ACM, New York), 189–198.Crossref, Google Scholar
• [33] Hȧstad J (2001) Some optimal inapproximability results. J. ACM 48(4):798–859.Crossref, Google Scholar
• [34] Hausmann D, Korte B (1978) K-greedy algorithms for independence systems. Oper. Res. Ser. A-B 22(1):219–228.Google Scholar
• [35] Hausmann D, Korte B, Jenkyns T (1980) Worst case analysis of greedy type algorithms for independence systems. Math. Programming Stud. 12:120–131.Crossref, Google Scholar
• [36] Jegelka S, Bilmes J (2011) Submodularity beyond submodular energies: Coupling edges in graph cuts. Proc. 2011 IEEE Conf. Comput. Vision Pattern Recognition (IEEE, Piscataway, NJ), 1897–1904.Crossref, Google Scholar
• [37] Jenkyns T (1976) The efficacy of the greedy algorithm. Cong. Num. 17:341–350.Google Scholar
• [38] 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
• [39] Kempe D, Kleinberg J, Tardos E (2003) Maximizing the spread of influence through a social network. Proc. 9th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining (ACM, New York), 137–146.Crossref, Google Scholar
• [40] 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
• [41] Khuller S, Moss A, Naor J (1999) The budgeted maximum coverage problem. Inform. Processing Lett. 70(1):39–45.Crossref, Google Scholar
• [42] Korte B, Hausmann D (1978) An analysis of the greedy heuristic for independence systems. Ann. Discrete Math. 2:65–74.Crossref, Google Scholar
• [43] 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
• [44] Krause A, Guestrin C (2005) Near-optimal nonmyopic value of information in graphical models. Proc. 21st Conf. Uncertainty Artificial Intelligence, 5.Google Scholar
• [45] 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 Management 134(6):516–526.Crossref, Google Scholar
• [46] 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
• [47] Lee J, Sviridenko M, Vondrák J (2010) Submodular maximization over multiple matroids via generalized exchange properties. Math. Oper. Res. 35(4):795–806.Link, Google Scholar
• [48] Lee J, Mirrokni VS, Nagarajan V, Sviridenko M (2010) Maximizing non-monotone submodular functions under matroid or knapsack constraints. SIAM J. Discrete Math. 23(4):2053–2078.Crossref, Google Scholar
• [49] Lin H, Bilmes J (2010) Multi-document summarization via budgeted maximization of submodular functions. Proc. 2010 Annual Conf. North Amer. Chapter Assoc. Comput. Linguistics/Human Language Tech. (ACM, Stroudsburg, PA).Google Scholar
• [50] Lin H, Bilmes J (2011) A class of submodular functions for document summarization. Proc. 49th Annual Meeting Assoc. Comput. Linguistics: Human Language Tech. (Association for Computational Linguistics, Stroudsburg, PA), 510–520.Google Scholar
• [51] Lovász L (1983) Submodular functions and convexity. Bachem A, Grötschel M, Korte B, eds. Mathematical Programming: The State of the Art (Springer-Verlag, Berlin, Heidelberg), 235–257.Crossref, Google Scholar
• [52] 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
• [53] 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
• [54] Sviridenko M (2004) A note on maximizing a submodular set function subject to knapsack constraint. Oper. Res. Lett. 32(1):41–43.Crossref, Google Scholar
• [55] Trevisan L, Sorkin GB, Sudan M, Williamson DP (2000) Gadgets, approximation, and linear programming. SIAM J. Comput. 29(6):2074–2097.Crossref, Google Scholar
• [56] Vondrák J (2013) Symmetry and approximability of submodular maximization problems. SIAM J. Comput. 42(1):265–304.Crossref, Google Scholar