{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T15:22:24Z","timestamp":1778685744564,"version":"3.51.4"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2017,5,26]],"date-time":"2017-05-26T00:00:00Z","timestamp":1495756800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Research Council under the ERC Starting","award":["335288-OptApprox"],"award-info":[{"award-number":["335288-OptApprox"]}]},{"name":"Isreal Science Foundation","award":["1357\/16"],"award-info":[{"award-number":["1357\/16"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2017,7,31]]},"abstract":"<jats:p>Symmetric submodular functions are an important family of submodular functions capturing many interesting cases, including cut functions of graphs and hypergraphs. Maximization of such functions subject to various constraints receives little attention by current research, unlike similar minimization problems that have been widely studied. In this work, we identify a few submodular maximization problems for which one can get a better approximation for symmetric objectives than the state-of-the-art approximation for general submodular functions.<\/jats:p>\n          <jats:p>\n            We first consider the problem of maximizing a non-negative symmetric submodular function\n            <jats:italic>f<\/jats:italic>\n            :2\n            <jats:sup>\n              <jats:italic>N<\/jats:italic>\n            <\/jats:sup>\n            \u2192 R\n            <jats:sup>+<\/jats:sup>\n            subject to a down-monotone solvable polytope\n            <jats:italic>P<\/jats:italic>\n            \u2286 [0, 1]\n            <jats:sup>\n              <jats:italic>N<\/jats:italic>\n            <\/jats:sup>\n            . For this problem, we describe an algorithm producing a fractional solution of value at least 0.432 \u010b\n            <jats:italic>f<\/jats:italic>\n            (\n            <jats:italic>OPT<\/jats:italic>\n            ), where\n            <jats:italic>OPT<\/jats:italic>\n            is the optimal\n            <jats:italic>integral<\/jats:italic>\n            solution. Our second result considers the problem max{\n            <jats:italic>f<\/jats:italic>\n            (\n            <jats:italic>S<\/jats:italic>\n            ): |\n            <jats:italic>S<\/jats:italic>\n            | =\n            <jats:italic>k<\/jats:italic>\n            } for a non-negative symmetric submodular function\n            <jats:italic>f<\/jats:italic>\n            :2\n            <jats:sup>\n              <jats:italic>N<\/jats:italic>\n            <\/jats:sup>\n            \u2192 R\n            <jats:sup>+<\/jats:sup>\n            . For this problem, we give an approximation ratio that depends on the value\n            <jats:italic>k<\/jats:italic>\n            \/|\n            <jats:italic>N<\/jats:italic>\n            | and is always at least 0.432. Our method can also be applied to non-negative\n            <jats:italic>non-symmetric<\/jats:italic>\n            submodular functions, in which case it produces 1\/e \u2212\n            <jats:italic>o<\/jats:italic>\n            (1) approximation, improving over the best-known result for this problem. For unconstrained maximization of a non-negative symmetric submodular function, we describe a\n            <jats:italic>deterministic linear-time<\/jats:italic>\n            1\/2-approximation algorithm. Finally, we give a [1 \u2212 (1 \u2212 1\/\n            <jats:italic>k<\/jats:italic>\n            )\n            <jats:sup>\n              <jats:italic>k<\/jats:italic>\n              \u2212 1\n            <\/jats:sup>\n            ]-approximation algorithm for Submodular Welfare with\n            <jats:italic>k<\/jats:italic>\n            players having identical non-negative submodular utility functions and show that this is the best possible approximation ratio for the problem.\n          <\/jats:p>","DOI":"10.1145\/3070685","type":"journal-article","created":{"date-parts":[[2017,5,31]],"date-time":"2017-05-31T19:32:40Z","timestamp":1496259160000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Maximizing Symmetric Submodular Functions"],"prefix":"10.1145","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1535-2979","authenticated-orcid":false,"given":"Moran","family":"Feldman","sequence":"first","affiliation":[{"name":"EPFL"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,5,26]]},"reference":[{"key":"e_1_2_1_1_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 ). 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). http:\/\/arxiv.org\/abs\/1611.03253"},{"key":"e_1_2_1_2_1","volume-title":"Deterministic algorithms for submodular maximization problems","author":"Buchbinder Niv","unstructured":"Niv Buchbinder and Moran Feldman . 2016b. Deterministic algorithms for submodular maximization problems . In SODA. SIAM , Philadelphia, PA , 392--403. Niv Buchbinder and Moran Feldman. 2016b. Deterministic algorithms for submodular maximization problems. In SODA. SIAM, Philadelphia, PA, 392--403."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/130929205"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634180"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/080733991"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.34"},{"key":"e_1_2_1_7_1","volume-title":"Submodular cost allocation problem and applications","author":"Chekuri Chandra","unstructured":"Chandra Chekuri and Alina Ene . 2011b. Submodular cost allocation problem and applications . In ICALP. Springer-Verlag , Berlin , 354--366. Chandra Chekuri and Alina Ene. 2011b. Submodular cost allocation problem and applications. In ICALP. Springer-Verlag, Berlin, 354--366."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133118"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/110839655"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(79)90084-0"},{"key":"e_1_2_1_11_1","volume-title":"On the approximation of submodular functions. CoRR abs\/1304.4948","author":"Devanur Nikhil R.","year":"2013","unstructured":"Nikhil R. Devanur , Shaddin Dughmi , Roy Schwartz , Ankit Sharma , and Mohit Singh . 2013. On the approximation of submodular functions. CoRR abs\/1304.4948 ( 2013 ). Nikhil R. Devanur, Shaddin Dughmi, Roy Schwartz, Ankit Sharma, and Mohit Singh. 2013. On the approximation of submodular functions. CoRR abs\/1304.4948 (2013)."},{"key":"e_1_2_1_12_1","volume-title":"An improved approximation algorithm for combinatorial auctions with submodular bidders","author":"Dobzinski Shahar","unstructured":"Shahar Dobzinski and Michael Schapira . 2006. An improved approximation algorithm for combinatorial auctions with submodular bidders . In SODA. SIAM , Philadelphia, PA , 1064--1073. Shahar Dobzinski and Michael Schapira. 2006. An improved approximation algorithm for combinatorial auctions with submodular bidders. In SODA. SIAM, Philadelphia, PA, 1064--1073."},{"key":"e_1_2_1_13_1","volume-title":"Submodular functions: Extensions, distributions, and algorithms. A survey. CoRR abs\/0912.0322","author":"Dughmi Shaddin","year":"2009","unstructured":"Shaddin Dughmi . 2009. Submodular functions: Extensions, distributions, and algorithms. A survey. CoRR abs\/0912.0322 ( 2009 ). Shaddin Dughmi. 2009. Submodular functions: Extensions, distributions, and algorithms. A survey. CoRR abs\/0912.0322 (2009)."},{"key":"e_1_2_1_14_1","volume-title":"Nguy\u1ec5n","author":"Ene Alina","year":"2016","unstructured":"Alina Ene and Huy L . Nguy\u1ec5n . 2016 . Constrained submodular maximization: Beyond 1\/e. In FOCS. IEEE Computer Society , New York, NY, 248--257. Alina Ene and Huy L. Nguy\u1ec5n. 2016. Constrained submodular maximization: Beyond 1\/e. In FOCS. IEEE Computer Society, New York, NY, 248--257."},{"key":"e_1_2_1_15_1","volume-title":"Local distribution and the symmetry gap: Approximability of multiway partitioning problems","author":"Ene Alina","unstructured":"Alina Ene , Jan Vondr\u00e1k , and Yi Wu. 2013. Local distribution and the symmetry gap: Approximability of multiway partitioning problems . In SODA. SIAM , Philadelphia, PA , 306--325. Alina Ene, Jan Vondr\u00e1k, and Yi Wu. 2013. Local distribution and the symmetry gap: Approximability of multiway partitioning problems. In SODA. SIAM, Philadelphia, PA, 306--325."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/090779346"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/2027127.2027164"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.46"},{"key":"e_1_2_1_20_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, 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, Berlin, 73--87."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133119"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/120891502"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"e_1_2_1_24_1","volume-title":"Improved approximation algorithms for k-Submodular Function Maximization","author":"Iwata Satoru","unstructured":"Satoru Iwata , Shin-ichi Tanigawa, and Yuichi Yoshida . 2016. Improved approximation algorithms for k-Submodular Function Maximization . In SODA. SIAM , Philadelphia, PA , 404--413. Satoru Iwata, Shin-ichi Tanigawa, and Yuichi Yoshida. 2016. Improved approximation algorithms for k-Submodular Function Maximization. In SODA. SIAM, Philadelphia, PA, 404--413."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118759.3119047"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/090750020"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1100.0463"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1386790.1386805"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118242.3118588"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585863"},{"key":"e_1_2_1_31_1","volume-title":"Hypergeometric tail inequalities: Ending the insanity. CoRR abs\/1311.5939","author":"Skala Matthew","year":"2013","unstructured":"Matthew Skala . 2013. Hypergeometric tail inequalities: Ending the insanity. CoRR abs\/1311.5939 ( 2013 ). Matthew Skala. 2013. Hypergeometric tail inequalities: Ending the insanity. CoRR abs\/1311.5939 (2013)."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/110832318"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-004-0510-2"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3070685","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3070685","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:27Z","timestamp":1750217427000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3070685"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,26]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,7,31]]}},"alternative-id":["10.1145\/3070685"],"URL":"https:\/\/doi.org\/10.1145\/3070685","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,5,26]]},"assertion":[{"value":"2016-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-05-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}