Submodular Maximization over Multiple Matroids via Generalized Exchange Properties

References

• Ageev A., Sviridenko M. Pipage rounding: A new method of constructing algorithms with proven performance guarantee. J. Combin. Optim. (2004) 8(3):307–328Crossref, Google Scholar
• Arkin E., Hassin R. On local search for weighted k-set packing. Math. Oper. Res. (1998) 23(3):640–648Link, Google Scholar
• Berman P. A d/2 approximation for maximum weight independent set in d-claw free graphs. Nordic J. Comput. (2000) 7(3):178–184Google Scholar
• Brylawski T. Some properties of basic families of subsets. Discrete Math. (1973) 6:333–341Crossref, Google Scholar
• Calinescu G., Chekuri C., Pál M., Vondrák J. Maximizing a submodular set function subject to a matroid constraint. Proc. 12th Internat. Workshop on Integer Programming and Combinat. Optim. (IPCO 2007) (2007) Ithaca, NY:182–196Google Scholar
• Calinescu G., Chekuri C., Pál M., Vondrák J. Maximizing a submodular set function subject to a matroid constraint. SIAM J. Comp. (2010) . ForthcomingGoogle Scholar
• Chandra B., Halldórsson M. Greedy local improvement and weighted set packing approximation. J. Algorithms (2001) 39(2):223–240Crossref, Google Scholar
• Conforti M., Cornuéjols G. Submodular set functions, matroids and the greedy algorithm: Tight worst-case bounds and some generalizations of the Rado-Edmonds theorem. Discrete Appl. Math. (1984) 7(3):251–274Crossref, Google Scholar
• Cornuéjols G., Fischer M., Nemhauser G. Location of bank accounts to optimize float: An analytic study of exact and approximation algorithms. Management Sci. (1977a) 23(8):789–810Link, Google Scholar
• Cornuéjols G., Fischer M., Nemhauser G. On the uncapacitated location problem. Ann. Discrete Math. (1977b) 1:163–178Crossref, Google Scholar
• Feige U. A threshold of ln n for approximating set cover. J. ACM (1998) 45:634–652Crossref, Google Scholar
• Feige U., Mirrokni V., Vondrák J. Maximizing non-monotone submodular functions. Proc. 48th Annual IEEE Sympos. on Foundations of Comput. Sci. (FOCS 2007) (2007) 461–471Crossref, Google Scholar
• Fisher M., Nemhauser G., Wolsey L. An analysis of approximations for maximizing submodular set functions—II. Math. Programming Stud. (1978) 8:73–87Crossref, Google Scholar
• Greene C. A multiple exchange property for bases. Proc. Amer. Math. Soc. (1973) 39:45–50Crossref, Google Scholar
• Greene C., Magnanti T. Some abstract pivot algorithms. SIAM J. Appl. Math. (1975) 29:530–539Crossref, Google Scholar
• Hausmann D., Korte B. K-greedy algorithms for independence systems. Zeitschrift Oper. Res. Ser. A–B (1978) 22(5Google Scholar
• Hausmann D., Korte B., Jenkyns T. Worst case analysis of greedy type algorithms for independence systems. Math. Programming Stud. (1980) 12:120–131Crossref, Google Scholar
• Hazan E., Safra S., Schwartz O. On the complexity of approximating k-set packing. Comput. Complexity (2006) 15(1):20–39Crossref, Google Scholar
• Hurkens C., Schrijver A. On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems. SIAM J. Discrete Math. (1989) 2(1):68–72Crossref, Google Scholar
• Iwata S., Fleischer L., Fujishige S. A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions. J. ACM (2001) 48:761–777Crossref, Google Scholar
• Jenkyns T. The efficacy of the greedy algorithm. Congressus Numerantium (1976) 17:341–350Google Scholar
• Lazebnik F., Ustimenko V., Woldar A. A new series of dense graphs of high girth. Bull. Amer. Math. Soc. (1995) 32(1):73–79Crossref, Google Scholar
• Lee J., Sviridenko M., Vondrák J. Submodular maximization over multiple matroids via generalized exchange properties. Proc. 12th Internat. Workshop on Approximation Algorithms for Combinat. Optim. Problems (APPROX 2009) (2009) (Springer, New York) 244–257Crossref, Google Scholar
• Lee J., Mirrokni V., Nagarajan V., Sviridenko M. Maximizing non-monotone submodular functions under matroid and knapsack constraints. SIAM J. Discrete Math. (2010) 23(4):2053–2078(Preliminary version appeared in STOC 2009)Crossref, Google Scholar
• Lovász L., Bachem A., Grötschel M., Korte B. Submodular functions and convexity. Mathematical Programmming—The State of the Art. Proc. 11th Internat. Sympos. on Math. Programming (1983) (Springer-Verlag, Berlin) 234–257Crossref, Google Scholar
• Nemhauser G., Wolsey L. Best algorithms for approximating the maximum of a submodular set function. Math. Oper. Res. (1978) 3(3):177–188Link, Google Scholar
• Nemhauser G., Wolsey L., Fisher M. An analysis of approximations for maximizing submodular set functions—I. Math. Programming (1978) 14:265–294Crossref, Google Scholar
• Oveis-Gharan S., Vondrák J. Submodular maximization by simulated annealing. ACM-SIAM Sympos. on Discrete Algorithms (SODA 2011) (2011) . ForthcomingGoogle Scholar
• Oxley J.Matroid Theory (1992) (Oxford University Press, New York) Google Scholar
• Reichel J., Skutella M. Evolutionary algorithms and matroid optimization problems. Genetic and Evolutionary Comput. Conf. (GECCO 2007) (2007) 947–954Crossref, Google Scholar
• Schrijver A. A combinatorial algorithm minimizing submodular functions in strongly polynomial time. J. Combin. Theory, Ser. B (2000) 80:346–355Crossref, Google Scholar
• Schrijver A.Combinatorial Optimization: Polyhedra and Efficiency (2003) (Springer, Berlin) Google Scholar
• Vondrák J. Optimal approximation for the submodular welfare problem in the value oracle model. Proc. 40th Annual ACM Sympos. Theory of Comput. (STOC 2008) (2008) 67–74Crossref, Google Scholar
• Vondrák J. Symmetry and approximability of submodular maximization problems. Proc. 50th Annual Sympos. on Foundations of Comput. Sci. (FOCS 2009) (2009) 651–670Crossref, Google Scholar
• Woodall D. An exchange theorem for bases of matroids. J. Combin. Theory, Ser. B (1974) 16:227–228Crossref, Google Scholar