skip to main content
10.1145/1536414.1536459acmconferencesArticle/Chapter ViewAbstractPublication PagesstocConference Proceedingsconference-collections
research-article

Non-monotone submodular maximization under matroid and knapsack constraints

Published:31 May 2009Publication History

ABSTRACT

Submodular function maximization is a central problem in combinatorial optimization, generalizing many important problems including Max Cut in directed/undirected graphs and in hypergraphs, certain constraint satisfaction problems, maximum entropy sampling, and maximum facility location problems. Unlike submodular minimization, submodular maximization is NP-hard. In this paper, we give the first constant-factor approximation algorithm for maximizing any non-negative submodular function subject to multiple matroid or knapsack constraints. We emphasize that our results are for non-monotone submodular functions. In particular, for any constant k, we present a (1/k+2+1/k+ε)-approximation for the submodular maximization problem under k matroid constraints, and a (1/5-ε)-approximation algorithm for this problem subject to k knapsack constraints (ε>0 is any constant). We improve the approximation guarantee of our algorithm to 1/k+1+{1/k-1}+ε for k≥2 partition matroid constraints. This idea also gives a ({1/k+ε)-approximation for maximizing a monotone submodular function subject to k≥2 partition matroids, which improves over the previously best known guarantee of 1/k+1.

References

  1. . Ageev, R. Hassin and M. Sviridenko, An 0.5-approximation algorithm for MAX DICUT with given sizes of parts. SIAM J. Discrete Math. 14 (2001), no. 2, 246--255 (electronic). Google ScholarGoogle ScholarDigital LibraryDigital Library
  2. . Ageev and M. Sviridenko. An 0.828 Approximation algorithm for the uncapacitated facility location problem, phDiscrete Applied Mathematics 93(2--3): 149--156 (1999). Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. . Ageev and M. Sviridenko, Pipage rounding: a new method ofconstructing algorithms with proven performance guarantee. J. Comb. Optim. 8 (2004), no. 3, 307--328.Google ScholarGoogle Scholar
  4. . Alimonti. Non-oblivious local search for MAX 2-CCSP withapplication to MAX DICUT, In Proceedings of the 23rd International Workshop on Graph-theoretic Concepts in Computer Science, 1997. Google ScholarGoogle ScholarDigital LibraryDigital Library
  5. K. M. Anstreicher, M. Fampa, J. Lee and J.Williams. Using continuous nonlinear relaxations to solve constrained maximum--entropy sampling problems. Mathematical Programming, Series A, 85:221--240, 1999.Google ScholarGoogle ScholarCross RefCross Ref
  6. . Burer and J. Lee. Solving maximum-entropysampling problems using factored masks. Mathematical Programming, Volume 109, Numbers 2--3, 263--281, 2007Google ScholarGoogle Scholar
  7. . Calinescu, C. Chekuri, M. Pál and J. Vondrák. Maximizing a monotone submodular function under a matroid constraint, IPCO 2007.Google ScholarGoogle Scholar
  8. . Cherenin. Solving some combinatorial problems of optimal planning by the method of successive calculations, Proc. of the Conference of Experiences and Perspectives of the Applications of Mathematical Methods and Electronic Computers in Planning (in Russian), Mimeograph,Novosibirsk (1962).Google ScholarGoogle Scholar
  9. . Cornuéjols, M. Fischer and G. Nemhauser. Location of bank accounts to optimize oat: An analytic study of exact and approximation algorithms, Management Science, 23 (1977), 789--810.Google ScholarGoogle ScholarDigital LibraryDigital Library
  10. . Cornuéjols, M. Fischer and G. Nemhauser. On the uncapacitated location problem, Annals of Discrete Math 1 (1977), 163--178.Google ScholarGoogle ScholarCross RefCross Ref
  11. . P. Cornuéjols, G. L. Nemhauser and L. A. Wolsey.The uncapacitated facility location problem. In Discrete Location Theory (1990), 119--171.Google ScholarGoogle Scholar
  12. . Edmonds. Matroids, submodular functions, and certain polyhedra, Combinatorial Structures and Their Applications (1970), 69--87.Google ScholarGoogle Scholar
  13. . Feige. A threshold of łn n for approximating set cover. Journal of ACM 45 (1998), 634--652. Google ScholarGoogle ScholarDigital LibraryDigital Library
  14. . Feige and M. X. Goemans. Approximating the value of two-prover systems, with applications to MAX-2SAT and MAX-DICUT. Proc. of the 3rd Israel Symposium on Theory and Computing Systems, Tel Aviv (1995), 182--189. Google ScholarGoogle ScholarDigital LibraryDigital Library
  15. . Feige, V. Mirrokni and J. Vondrák. Maximizing non-monotone submodular functions, FOCS 2007. Google ScholarGoogle ScholarDigital LibraryDigital Library
  16. . Frank. Matroids and submodular functions, Annotated Biblographies in Combinatorial Optimization (1997), 65--80.Google ScholarGoogle Scholar
  17. . Fujishige. Canonical decompositions of symmetric submodular systems, Discrete Applied Mathematics 5 (1983), 175--190.Google ScholarGoogle ScholarCross RefCross Ref
  18. M. Goemans, N. Harvey, S. Iwata, V. Mirrokni. Approximating submodular functions everywhere. In SODA 2009. Google ScholarGoogle ScholarDigital LibraryDigital Library
  19. . X. Goemans and D. P. Williamson.Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of ACM 42 (1995), 1115--1145. Google ScholarGoogle ScholarDigital LibraryDigital Library
  20. . Goldengorin, G. Sierksma, G. Tijsssen and M. Tso. The data correcting algorithm for the minimization of supermodular functions, Management Science, 45:11 (1999), 1539--1551. Google ScholarGoogle ScholarDigital LibraryDigital Library
  21. . Goldengorin, G. Tijsssen and M. Tso.The maximization of submodular Functions: Old and new proofs for the correctness of the dichotomy algorithm, SOM Report, University of Groningen (1999).Google ScholarGoogle Scholar
  22. . Halperin and U. Zwick. Combinatorial approximation algorithms for the maximum directed cut problem. Proc. of 12th SODA (2001), 1--7. Google ScholarGoogle ScholarDigital LibraryDigital Library
  23. J. Hartline, V. Mirrokni and M. Sundararajan. Optimal marketing strategies over social networks, World Wide Web Conference (WWW), 2008, 189--198. Google ScholarGoogle ScholarDigital LibraryDigital Library
  24. . Hazan, S. Safra and O. Schwartz. On the complexityof approximating k-set packing. Computational Complexity, 15(1), 20--39, 2006. Google ScholarGoogle ScholarDigital LibraryDigital Library
  25. . Håstad. Some optimal inapproximability results. Journal of ACM 48 (2001): 798--869. Google ScholarGoogle ScholarDigital LibraryDigital Library
  26. S. Iwata, L. Fleischer and S. Fujishige. A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions, Journal of ACM 48:4 (2001), 761--777. Google ScholarGoogle ScholarDigital LibraryDigital Library
  27. . R. Khachaturov, Mathematical Methods of Regional Programming, Nauka, Moscow (in Russian), 1989.Google ScholarGoogle Scholar
  28. . Kulik, H. Shachnai and T. Tamir. Maximizing submodular functionssubject to multiple linear constraints. Proc. of SODA, 2009. Google ScholarGoogle ScholarDigital LibraryDigital Library
  29. C.-W. Ko, J. Lee and M. Queyranne. An exactalgorithm for maximum entropy sampling. Operations Research 43(4):684--691, 1995.Google ScholarGoogle ScholarDigital LibraryDigital Library
  30. . Krause, A. Singh and C. Guestrin.Near-optimal sensor placements in Gaussian processes: Theory, efficient algorithms and empirical studies, Journal of Machine Learning Research 9 (2008) 235--284. Google ScholarGoogle ScholarDigital LibraryDigital Library
  31. . Lee, G. Nemhauser and Y. Wang.Maximizing a submodular function by integer programming: Polyhedral results for the quadratic case, European Journal of Operational Research 94, 154--166.Google ScholarGoogle Scholar
  32. J. Lee. Maximum entropy sampling. In: A.H. El-Shaarawi and W.W. Piegorsch, editors, "Encyclopedia of Environmetrics". Wiley, 2001.Google ScholarGoogle Scholar
  33. J. Lee. Semidefinite programming in experimental design.In: H. Wolkowicz, R. Saigal and L. Vandenberghe, editors, "Handbook of Semidefinite Programming", International Series in Operations Research and Management Science, Vol. 27, Kluwer, 2000.Google ScholarGoogle Scholar
  34. J. Lee. Constrained maximum-entropy sampling.phOperations Research, 46:655--664, 1998. Google ScholarGoogle ScholarDigital LibraryDigital Library
  35. . Lee, V. Mirrokni, V. Nagarajan and M. Sviridenko. Maximizing Non-Monotone Submodular Functions under Matroid and Knapsack Constraints. IBM Research Report RC24679, 2008.Google ScholarGoogle Scholar
  36. . Lovász. Submodular functions and convexity. In: A. Bachem et. al., eds, "Mathematical Programmming: The State of the Art," 235--257.Google ScholarGoogle Scholar
  37. . Mirrokni, J. Vondrák and M. Schapira. Tight Information-Theoretic Lower Bounds for Welfare Maximization in Combinatorial Auctions. Proc. of EC, 2008, 70--77. Google ScholarGoogle ScholarDigital LibraryDigital Library
  38. . Motwani and P. Raghavan. Randomized Algorithms,Cambridge University Press, 1995. Google ScholarGoogle ScholarDigital LibraryDigital Library
  39. . L. Nemhauser, L. A. Wolsey and M. L. Fisher. An analysis of approximations for maximizing submodular set functions I. Mathematical Programming 14 (1978), 265--294.Google ScholarGoogle ScholarDigital LibraryDigital Library
  40. . L. Nemhauser, L. A. Wolsey and M. L. Fisher. An analysis of approximations for maximizing submodular set functions II. Mathematical Programming Study 8 (1978), 73--87.Google ScholarGoogle ScholarCross RefCross Ref
  41. . G. Oxley,"Matroid theory," Oxford Science Publications. The Clarendon Press, Oxford University Press, New York, 1992.Google ScholarGoogle Scholar
  42. . Queyranne. A combinatorial algorithm for minimizing symmetric submodular functions, ACM-SIAM Symposium on Discrete Algorithms (1995), 98--101. Google ScholarGoogle ScholarDigital LibraryDigital Library
  43. . Reichel and M. Skutella, Evolutionary algorithms and matroid optimization problems, in Proceedings of the 9th Genetic and Evolutionary Computation Conference (GECCO'07), 947--954, 2007. Google ScholarGoogle ScholarDigital LibraryDigital Library
  44. . Robertazzi and S. Schwartz, An accelated sequential algorithm for producing D-optimal designs. SIAM Journal on Scientific and Statistical Computing 10, 341--359. Google ScholarGoogle ScholarDigital LibraryDigital Library
  45. . Schrijver. A combinatorial algorithm minimizing submodular functions in strongly polynomial time, Journal of Combinatorial Theory, Series B 80 (2000), 346--355. Google ScholarGoogle ScholarDigital LibraryDigital Library
  46. . Schrijver. "Combinatorial Optimization," Volumes A-C. Springer-Verlag, Berlin, 2003.Google ScholarGoogle Scholar
  47. . Schulz, N. Uhan, Encouraging Cooperation in Sharing Supermodular Costs, APPROX-RANDOM 2007: 271--285 Google ScholarGoogle ScholarDigital LibraryDigital Library
  48. . C. Shewry, H. P. Wynn, Maximum entropy sampling. J. Appl. Stat. 14 (1987), 165--170.Google ScholarGoogle ScholarCross RefCross Ref
  49. . Sviridenko. A note on maximizing a submodular set function subject to knapsack constraint. Operations Research Letters 32 (2004), 41--43. Google ScholarGoogle ScholarDigital LibraryDigital Library
  50. Z. Svitkina and L. Fleischer. Submodular approximation: Sampling-based algorithms and lower bounds. In FOCS 2008. Google ScholarGoogle ScholarDigital LibraryDigital Library
  51. . Vondrák.Optimal approximation for the submodular welfare problem in the value oracle model. In STOC, 2008. Google ScholarGoogle ScholarDigital LibraryDigital Library
  52. . Vondrák, Personal communication, 2008.Google ScholarGoogle Scholar

Index Terms

  1. Non-monotone submodular maximization under matroid and knapsack constraints

    Recommendations

    Comments

    Login options

    Check if you have access through your login credentials or your institution to get full access on this article.

    Sign in
    • Published in

      cover image ACM Conferences
      STOC '09: Proceedings of the forty-first annual ACM symposium on Theory of computing
      May 2009
      750 pages
      ISBN:9781605585062
      DOI:10.1145/1536414

      Copyright © 2009 ACM

      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      • Published: 31 May 2009

      Permissions

      Request permissions about this article.

      Request Permissions

      Check for updates

      Qualifiers

      • research-article

      Acceptance Rates

      Overall Acceptance Rate1,469of4,586submissions,32%

      Upcoming Conference

      STOC '24
      56th Annual ACM Symposium on Theory of Computing (STOC 2024)
      June 24 - 28, 2024
      Vancouver , BC , Canada

    PDF Format

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader