{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T19:44:12Z","timestamp":1780343052937,"version":"3.54.1"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2018,6,16]],"date-time":"2018-06-16T00:00:00Z","timestamp":1529107200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"BSF","award":["2014414"],"award-info":[{"award-number":["2014414"]}]},{"name":"ERC","award":["335288-OptApprox"],"award-info":[{"award-number":["335288-OptApprox"]}]},{"name":"ISF","award":["1585\/15 and 1357\/16"],"award-info":[{"award-number":["1585\/15 and 1357\/16"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2018,7,31]]},"abstract":"<jats:p>Randomization is a fundamental tool used in many theoretical and practical areas of computer science. We study here the role of randomization in the area of submodular function maximization. In this area, most algorithms are randomized, and in almost all cases the approximation ratios obtained by current randomized algorithms are superior to the best results obtained by known deterministic algorithms. Derandomization of algorithms for general submodular function maximization seems hard since the access to the function is done via a value oracle. This makes it hard, for example, to apply standard derandomization techniques such as conditional expectations. Therefore, an interesting fundamental problem in this area is whether randomization is inherently necessary for obtaining good approximation ratios.<\/jats:p>\n          <jats:p>In this work, we give evidence that randomization is not necessary for obtaining good algorithms by presenting a new technique for derandomization of algorithms for submodular function maximization. Our high level idea is to maintain explicitly a (small) distribution over the states of the algorithm, and carefully update it using marginal values obtained from an extreme point solution of a suitable linear formulation. We demonstrate our technique on two recent algorithms for unconstrained submodular maximization and for maximizing a submodular function subject to a cardinality constraint. In particular, for unconstrained submodular maximization we obtain an optimal deterministic 1\/2-approximation showing that randomization is unnecessary for obtaining optimal results for this setting.<\/jats:p>","DOI":"10.1145\/3184990","type":"journal-article","created":{"date-parts":[[2018,6,18]],"date-time":"2018-06-18T12:28:11Z","timestamp":1529324891000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":42,"title":["Deterministic Algorithms for Submodular Maximization Problems"],"prefix":"10.1145","volume":"14","author":[{"given":"Niv","family":"Buchbinder","sequence":"first","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1535-2979","authenticated-orcid":false,"given":"Moran","family":"Feldman","sequence":"additional","affiliation":[{"name":"EPFL, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,6,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00103-1"},{"key":"e_1_2_1_2_1","volume-title":"Spencer","author":"Alon Noga","year":"2000","unstructured":"Noga Alon and Joel H . Spencer . 2000 . The Probabilistic Method (2nd ed.). John Wiley and Sons , Inc., New York. Noga Alon and Joel H. Spencer. 2000. The Probabilistic Method (2nd ed.). John Wiley and Sons, Inc., New York."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/2040572.2040609"},{"key":"e_1_2_1_4_1","volume-title":"Constrained submodular maximization via a non-symmetric technique. CoRR abs\/1611.03253","author":"Buchbinder Niv","year":"2016","unstructured":"Niv Buchbinder and Moran Feldman . 2016a. Constrained submodular maximization via a non-symmetric technique. CoRR abs\/1611.03253 ( 2016 ). Retrieved from http:\/\/arxiv.org\/abs\/1611.03253. Niv Buchbinder and Moran Feldman. 2016a. Constrained submodular maximization via a non-symmetric technique. CoRR abs\/1611.03253 (2016). Retrieved from http:\/\/arxiv.org\/abs\/1611.03253."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884464"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/130929205"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634180"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722206"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722209"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/080733991"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_26"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700382820"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.06.003"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.23.8.789"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70732-5"},{"key":"e_1_2_1_16_1","volume-title":"A deterministic algorithm for maximizing submodular functions. CoRR abs\/1507.07237","author":"Dobzinski Shahar","year":"2015","unstructured":"Shahar Dobzinski and Ami Mor . 2015. A deterministic algorithm for maximizing submodular functions. CoRR abs\/1507.07237 ( 2015 ). Retrieved from http:\/\/arxiv.org\/abs\/1507.07237. Shahar Dobzinski and Ami Mor. 2015. A deterministic algorithm for maximizing submodular functions. CoRR abs\/1507.07237 (2015). Retrieved from http:\/\/arxiv.org\/abs\/1507.07237."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109675"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the FOCS. IEEE Computer Society","author":"Ene Alina","unstructured":"Alina Ene and Huy L. Nguyen . 2016. Constrained submodular maximization: Beyond 1\/e . In Proceedings of the FOCS. IEEE Computer Society , New York, NY, 248--257. Alina Ene and Huy L. Nguyen. 2016. Constrained submodular maximization: Beyond 1\/e. In Proceedings of the FOCS. IEEE Computer Society, New York, NY, 248--257."},{"key":"e_1_2_1_19_1","volume-title":"Goemans","author":"Feige Uriel","year":"1995","unstructured":"Uriel Feige and Michel X . Goemans . 1995 . Aproximating the value of two prover proof systems, with applications to MAX 2SAT and MAX DICUT. In Proceedings of the ISTCS. IEEE Computer Society , Washington, DC, 182--189. Uriel Feige and Michel X. Goemans. 1995. Aproximating the value of two prover proof systems, with applications to MAX 2SAT and MAX DICUT. In Proceedings of the ISTCS. IEEE Computer Society, Washington, DC, 182--189."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/090779346"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.14"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/2027127.2027164"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.46"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/130920277"},{"key":"e_1_2_1_25_1","volume-title":"Polyhedral Combinatorics. Mathematical Programming Studies","volume":"8","author":"Fisher M. L.","unstructured":"M. L. Fisher , G. L. Nemhauser , and L. A. Wolsey . 1978. An analysis of approximations for maximizing submodular set functions -- II . In Polyhedral Combinatorics. Mathematical Programming Studies , Vol. 8 . Springer-Verlag, Berlin, 73--87. M. L. Fisher, G. L. Nemhauser, and L. A. Wolsey. 1978. An analysis of approximations for maximizing submodular set functions -- II. In Polyhedral Combinatorics. Mathematical Programming Studies, Vol. 8. Springer-Verlag, Berlin, 73--87."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1110.0499"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133119"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the SODA. SIAM","author":"Halperin Eran","year":"2001","unstructured":"Eran Halperin and Uri Zwick . 2001 . Combinatorial approximation algorithms for the maximum directed cut problem . In Proceedings of the SODA. SIAM , Philadelphia, PA, 1--7. Eran Halperin and Uri Zwick. 2001. Combinatorial approximation algorithms for the maximum directed cut problem. In Proceedings of the SODA. SIAM, Philadelphia, PA, 1--7."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the ISAAC. SIAM","author":"Huang Norman","year":"2014","unstructured":"Norman Huang and Allan Borodin . 2014 . Bounds on double-sided myopic algorithms for unconstrained non-monotone submodular maximization . In Proceedings of the ISAAC. SIAM , Philadelphia, PA, 528--539. Norman Huang and Allan Borodin. 2014. Bounds on double-sided myopic algorithms for unconstrained non-monotone submodular maximization. In Proceedings of the ISAAC. SIAM, Philadelphia, PA, 528--539."},{"key":"e_1_2_1_32_1","volume-title":"Complexity of Computer Computations","author":"Karp Richard M.","unstructured":"Richard M. Karp . 1972. Reducibility among combinatorial problems . In Complexity of Computer Computations , R. E. Miller and J. W. Thatcher (Eds.). Plenum Press , New York , 85--103. Richard M. Karp. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations, R. E. Miller and J. W. Thatcher (Eds.). Plenum Press, New York, 85--103."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447372"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2013.0592"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/090750020"},{"key":"e_1_2_1_36_1","volume-title":"Probability and Computing, Randomized Algorithms and Probabilistic Analysis","author":"Mitzenmacher Michael","unstructured":"Michael Mitzenmacher and Eli Upfal . 2005. Probability and Computing, Randomized Algorithms and Probabilistic Analysis . Cambridge University Press, New York , NY. Michael Mitzenmacher and Eli Upfal. 2005. Probability and Computing, Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, New York, NY."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797328847"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/110832318"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3184990","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3184990","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:11:25Z","timestamp":1750212685000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3184990"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,16]]},"references-count":38,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,7,31]]}},"alternative-id":["10.1145\/3184990"],"URL":"https:\/\/doi.org\/10.1145\/3184990","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,6,16]]},"assertion":[{"value":"2016-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-06-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}