IDEAS home Printed from https://ideas.repec.org/a/inm/ormoor/v42y2017i2p308-329.html
   My bibliography  Save this article

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

Author

Listed:
  • Niv Buchbinder

    (Statistics and Operations Research Department, Tel Aviv University, Tel Aviv 6997801, Israel)

  • Moran Feldman

    (Department of Mathematics and Computer Science, The Open University of Israel, Raanana 4353701, Israel)

  • Roy Schwartz

    (Department of Computer Science, Technion, Haifa 3200003, Israel)

Abstract

Fast algorithms for submodular maximization problems have a vast potential use in applicative settings, such as machine learning, social networks, and economics. Though fast algorithms were known for some special cases, only recently such algorithms were considered in the general case of maximizing a monotone submodular function subject to a matroid independence constraint. The known fast algorithm matches the best possible approximation guarantee, while trying to reduce the number of value oracle queries the algorithm performs. Our main result is a new algorithm for this general case that establishes a surprising trade-off between two seemingly unrelated quantities: the number of value oracle queries and the number of matroid independence queries performed by the algorithm. Specifically, one can decrease the former by increasing the latter, and vice versa, while maintaining the best possible approximation guarantee. Such a trade-off is very useful since various applications might incur significantly different costs in querying the value and matroid independence oracles. Furthermore, in case the rank of the matroid is O ( n c ), where n is the size of the ground set and c is an absolute constant smaller than 1, the total number of oracle queries our algorithm uses can be made to have a smaller magnitude compared to that needed by the current best known algorithm. We also provide even faster algorithms for the well-studied special cases of a cardinality constraint and a partition matroid independence constraint, both of which capture many real-world applications and have been widely studied both theoretically and in practice.

Suggested Citation

  • Niv Buchbinder & Moran Feldman & Roy Schwartz, 2017. "Comparing Apples and Oranges: Query Trade-off in Submodular Maximization," Mathematics of Operations Research, INFORMS, vol. 42(2), pages 308-329, May.
    • Handle: RePEc:inm:ormoor:v:42:y:2017:i:2:p:308-329
    DOI: 10.1287/moor.2016.0809
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/moor.2016.0809
    Download Restriction: no
    File URL: https://libkey.io/10.1287/moor.2016.0809?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Fisher, M.L. & Nemhauser, G.L. & Wolsey, L.A., 1978. "An analysis of approximations for maximizing submodular set functions - 1," LIDAM Reprints CORE 334, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    2. G. L. Nemhauser & L. A. Wolsey, 1978. "Best Algorithms for Approximating the Maximum of a Submodular Set Function," Mathematics of Operations Research, INFORMS, vol. 3(3), pages 177-188, August.
    3. Nemhauser, G.L. & Wolsey, L.A., 1978. "Best algorithms for approximating the maximum of a submodular set function," LIDAM Reprints CORE 343, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    4. Gerard Cornuejols & Marshall L. Fisher & George L. Nemhauser, 1977. "Exceptional Paper--Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms," Management Science, INFORMS, vol. 23(8), pages 789-810, April.
    5. Fisher, M.L. & Nemhauser, G.L. & Wolsey, L.A., 1978. "An analysis of approximations for maximizing submodular set functions," LIDAM Reprints CORE 341, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    6. CORNUEJOLS, Gérard & FISHER, Marshall L. & NEMHAUSER, George L., 1977. "Location of bank accounts to optimize float: An analytic study of exact and approximate algorithms," LIDAM Reprints CORE 292, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Awi Federgruen & Nan Yang, 2008. "Selecting a Portfolio of Suppliers Under Demand and Supply Risks," Operations Research, INFORMS, vol. 56(4), pages 916-936, August.
    2. Kung, Ling-Chieh & Liao, Wei-Hung, 2018. "An approximation algorithm for a competitive facility location problem with network effects," European Journal of Operational Research, Elsevier, vol. 267(1), pages 176-186.
    3. Niv Buchbinder & Moran Feldman, 2019. "Constrained Submodular Maximization via a Nonsymmetric Technique," Mathematics of Operations Research, INFORMS, vol. 44(3), pages 988-1005, August.
    4. Jon Lee & Maxim Sviridenko & Jan Vondrák, 2010. "Submodular Maximization over Multiple Matroids via Generalized Exchange Properties," Mathematics of Operations Research, INFORMS, vol. 35(4), pages 795-806, November.
    5. Ortiz-Astorquiza, Camilo & Contreras, Ivan & Laporte, Gilbert, 2018. "Multi-level facility location problems," European Journal of Operational Research, Elsevier, vol. 267(3), pages 791-805.
    6. Suning Gong & Qingqin Nong & Shuyu Bao & Qizhi Fang & Ding-Zhu Du, 2023. "A fast and deterministic algorithm for Knapsack-constrained monotone DR-submodular maximization over an integer lattice," Journal of Global Optimization, Springer, vol. 85(1), pages 15-38, January.
    7. Bin Liu & Miaomiao Hu, 2022. "Fast algorithms for maximizing monotone nonsubmodular functions," Journal of Combinatorial Optimization, Springer, vol. 43(5), pages 1655-1670, July.
    8. Klages-Mundt, Ariah & Minca, Andreea, 2022. "Optimal intervention in economic networks using influence maximization methods," European Journal of Operational Research, Elsevier, vol. 300(3), pages 1136-1148.
    9. Xin Sun & Gaidi Li & Yapu Zhang & Zhenning Zhang, 2022. "Private non-monotone submodular maximization," Journal of Combinatorial Optimization, Springer, vol. 44(5), pages 3212-3232, December.
    10. Camilo Ortiz-Astorquiza & Ivan Contreras & Gilbert Laporte, 2017. "Formulations and Approximation Algorithms for Multilevel Uncapacitated Facility Location," INFORMS Journal on Computing, INFORMS, vol. 29(4), pages 767-779, November.
    11. Zhenning Zhang & Donglei Du & Yanjun Jiang & Chenchen Wu, 2021. "Maximizing DR-submodular+supermodular functions on the integer lattice subject to a cardinality constraint," Journal of Global Optimization, Springer, vol. 80(3), pages 595-616, July.
    12. Hao-Hsiang Wu & Simge Küçükyavuz, 2018. "A two-stage stochastic programming approach for influence maximization in social networks," Computational Optimization and Applications, Springer, vol. 69(3), pages 563-595, April.
    13. Simon Bruggmann & Rico Zenklusen, 2019. "Submodular Maximization Through the Lens of Linear Programming," Management Science, INFORMS, vol. 44(4), pages 1221-1244, November.
    14. Zhigang Li & Mingchuan Zhang & Junlong Zhu & Ruijuan Zheng & Qikun Zhang & Qingtao Wu, 2018. "Stochastic Block-Coordinate Gradient Projection Algorithms for Submodular Maximization," Complexity, Hindawi, vol. 2018, pages 1-11, December.
    15. Hao Shen & Yong Liang & Zuo-Jun Max Shen, 2021. "Reliable Hub Location Model for Air Transportation Networks Under Random Disruptions," Manufacturing & Service Operations Management, INFORMS, vol. 23(2), pages 388-406, March.
    16. Arash Asadpour & Hamid Nazerzadeh, 2016. "Maximizing Stochastic Monotone Submodular Functions," Management Science, INFORMS, vol. 62(8), pages 2374-2391, August.
    17. Min Cui & Dachuan Xu & Longkun Guo & Dan Wu, 2022. "Approximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraint," Journal of Combinatorial Optimization, Springer, vol. 43(5), pages 1671-1690, July.
    18. Manuel A. Nunez & Robert S. Garfinkel & Ram D. Gopal, 2007. "Stochastic Protection of Confidential Information in Databases: A Hybrid of Data Perturbation and Query Restriction," Operations Research, INFORMS, vol. 55(5), pages 890-908, October.
    19. Awi Federgruen & Upmanu Lall & A. Serdar Şimşek, 2019. "Supply Chain Analysis of Contract Farming," Manufacturing & Service Operations Management, INFORMS, vol. 21(2), pages 361-378, April.
    20. Marek Adamczyk & Maxim Sviridenko & Justin Ward, 2016. "Submodular Stochastic Probing on Matroids," Mathematics of Operations Research, INFORMS, vol. 41(3), pages 1022-1038, August.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormoor:v:42:y:2017:i:2:p:308-329. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.