{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,22]],"date-time":"2026-09-22T22:38:58Z","timestamp":1790116738518,"version":"4.0.1"},"reference-count":45,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2011,1]]},"abstract":"<jats:p>We introduce several generalizations of classical computer science problems obtained by replacing simpler objective functions with general submodular functions. The new problems include submodular load balancing, which generalizes load balancing or minimum-makespan scheduling, submodular sparsest cut and submodular balanced cut, which generalize their respective graph cut problems, as well as submodular function minimization with a cardinality lower bound. We establish upper and lower bounds for the approximability of these problems with a polynomial number of queries to a function-value oracle. The approximation guarantees that most of our algorithms achieve are of the order of $\\sqrt{{n}\/{\\ln n}}$. We show that this is the inherent difficulty of the problems by proving matching lower bounds. We also give an improved lower bound for the problem of approximating a monotone submodular function everywhere. In addition, we present an algorithm for approximating submodular functions with a special structure, whose guarantee is close to the lower bound. Although quite restrictive, the class of functions with this structure includes the ones that are used for lower bounds both by us and in previous work.<\/jats:p>","DOI":"10.1137\/100783352","type":"journal-article","created":{"date-parts":[[2011,12,20]],"date-time":"2011-12-20T18:59:53Z","timestamp":1324407593000},"page":"1715-1737","source":"Crossref","is-referenced-by-count":79,"title":["Submodular Approximation: Sampling-based Algorithms and Lower Bounds"],"prefix":"10.1137","volume":"40","author":[{"given":"Zoya","family":"Svitkina","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lisa","family":"Fleischer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2011,12,20]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"S. Arora, E. Hazan, and S. Kale,\n                      ${O}(\\sqrt{\\log n})$ approximation to sparsest cut in $\\tilde{O}(n^2)$ time\n                      , in Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, 2004, pp. 238\u2013247.","DOI":"10.1109\/FOCS.2004.1"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"S. Arora, S. Rao, and U. Vazirani,\n                      Expander flows, geometric embeddings and graph partitioning\n                      , in Proceedings of the 36th ACM Symposium on Theory of Computing, 2004.","DOI":"10.1145\/1007352.1007355"},{"key":"R3","unstructured":"G. Calinescu, C. Chekuri, M. Pal, and J. Vondrak,\n                      Maximizing a submodular set function subject to a matroid constraint\n                      , SIAM J. Comput., to appear."},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-005-1412-9"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"C. Chekuri and M. Pal,\n                      A recursive greedy algorithm for walks in directed graphs\n                      , in Proceedings of the 46th IEEE Symposium on Foundations of Computer Science, 2005, pp. 245\u2013253.","DOI":"10.1109\/SFCS.2005.9"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"C. Chekuri, J. Vondrak, and R. Zenklusen,\n                      Dependent randomized rounding via exchange properties of combinatorial structures\n                      , in Proceedings of the 51st IEEE Symposium on Foundations of Computer Science, 2010, pp. 575\u2013584.","DOI":"10.1109\/FOCS.2010.60"},{"key":"R7","unstructured":"T. Cormen, C. Leiserson, R. Rivest, and C. Stein,\n                      Introduction to Algorithms\n                      , 2nd ed., MIT Press, Cambridge, MA, 2001."},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230150206"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"U. Feige, V. Mirrokni, and J. Vondrak,\n                      Maximizing non-monotone submodular functions\n                      , in Proceedings of the 48th IEEE Symposium on Foundations of Computer Science, 2007.","DOI":"10.1109\/FOCS.2007.4389516"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(02)00458-4"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(78)91063-X"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"G.V. Gens and E.V. Levner,\n                      Computational complexity of approximation algorithms for combinatorial problems\n                      , in Proceedings of the 8th International Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Comput. Sci. 74, 1979, Springer-Verlag, Berlin.","DOI":"10.1007\/3-540-09526-8_26"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"G. Goel, C. Karande, P. Tripathi, and L. Wang,\n                      Approximability of combinatorial problems with multi-agent submodular cost functions\n                      , in Proceedings of the 50th IEEE Symposium on Foundations of Computer Science, 2009.","DOI":"10.1109\/FOCS.2009.81"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"M. Goemans, N. Harvey, S. Iwata, and V. Mirrokni,\n                      Approximating submodular functions everywhere\n                      , in Proceedings of the 20th ACM Symposium on Discrete Algorithms, 2009.","DOI":"10.1137\/1.9781611973068.59"},{"key":"R15","unstructured":"M. Goemans, N. Harvey, R. Kleinberg, and V. Mirrokni,\n                      On Learning Submodular Functions\n                      , unpublished manuscript, 2007."},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579273"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"M. Gr\u00f6tschel, L. Lov\u00e1sz, and A. Schrijver,\n                      Geometric Algorithms and Combinatorial Optimization\n                      , Springer-Verlag, Berlin, 1988.","DOI":"10.1007\/978-3-642-97881-4"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"A. Hayrapetyan, D. Kempe, M. Pal, and Z. Svitkina,\n                      Unbalanced graph cuts\n                      , in Proceedings of the 13th European Symposium on Algorithms, 2005.","DOI":"10.1007\/11561071_19"},{"key":"R19","unstructured":"A. Hayrapetyan, C. Swamy, and E. Tardos,\n                      Network design for information networks\n                      , in Proceedings of the 16th ACM Symposium on Discrete Algorithms, 2005, pp. 933\u2013942."},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1145\/7531.7535"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701397813"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-006-0084-2"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502096"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"S. Iwata and K. Nagano,\n                      Submodular function minimization under covering constraints\n                      , in Proceedings of the 50th IEEE Symposium on Foundations of Computer Science, 2009.","DOI":"10.1109\/FOCS.2009.31"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"S. Iwata and J.B. Orlin,\n                      A simple combinatorial algorithm for submodular function minimization\n                      , in Proceedings of the 20th ACM Symposium on Discrete Algorithms, 2009.","DOI":"10.1137\/1.9781611973068.133"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"A. Kulik, H. Shachnai, and T. Tamir,\n                      Maximizing submodular set functions subject to multiple linear constraints\n                      , in Proceedings of the 20th ACM Symposium on Discrete Algorithms, 2009.","DOI":"10.1137\/1.9781611973068.60"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"J. Lee, V. Mirrokni, V. Nagarajan, and M. Sviridenko,\n                      Non-monotone submodular maximization under matroid and knapsack constraints\n                      , in Proceedings of the 41st ACM Symposium on Theory of Computing, 2009.","DOI":"10.1145\/1536414.1536459"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"J. Lee, M. Sviridenko, and J. Vondrak,\n                      Submodular maximization over multiple matroids via generalized exchange properties\n                      , in Proceedings of the 12th APPROX, 2009.","DOI":"10.1007\/978-3-642-03685-9_19"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"F.T. Leighton and S. Rao,\n                      Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms\n                      , J. ACM, 46 (1999).","DOI":"10.1145\/331524.331526"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585745"},{"key":"R31","unstructured":"R. Motwani and P. Raghavan,\n                      Randomized Algorithms\n                      , Cambridge University Press, UK, 1990."},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-007-0189-2"},{"key":"R34","doi-asserted-by":"crossref","unstructured":"S. Oveis Gharan and J. Vondrak,\n                      Submodular maximization by simulated annealing\n                      , in Proceedings of the 22nd ACM Symposium on Discrete Algorithms, 2011.","DOI":"10.1137\/1.9781611973082.83"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585863"},{"key":"R36","doi-asserted-by":"crossref","unstructured":"H. R\u00e4cke,\n                      Optimal hierarchical decompositions for congestion minimization in networks\n                      , in Proceedings of the 40th ACM Symposium on Theory of Computing, 2008, pp. 255\u2013263.","DOI":"10.1145\/1374376.1374415"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2000.1989"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(03)00062-2"},{"key":"R39","doi-asserted-by":"crossref","unstructured":"Z. Svitkina and L. Fleischer,\n                      Submodular approximation: Sampling-based algorithms and lower bounds\n                      , in Proceedings of the 49th IEEE Symposium on Foundations of Computer Science, 2008.","DOI":"10.1109\/FOCS.2008.66"},{"key":"R40","doi-asserted-by":"crossref","unstructured":"Z. Svitkina and E. Tardos,\n                      Min-max multiway cut\n                      , in Proceedings of the 7th APPROX, 2004, pp. 207\u2013218.","DOI":"10.1007\/978-3-540-27821-4_19"},{"key":"R41","doi-asserted-by":"crossref","unstructured":"Z. Svitkina and E. Tardos,\n                      Facility location with hierarchical facility costs\n                      , ACM Trans. Algorithms, 6 (2010).","DOI":"10.1145\/1721837.1721853"},{"key":"R42","unstructured":"C. Swamy, Y. Sharma, and D. Williamson,\n                      Approximation algorithms for prize collecting steiner forest problems with submodular penalty functions\n                      , in Proceedings of the 18th ACM Symposium on Discrete Algorithms, 2007."},{"key":"R43","doi-asserted-by":"crossref","unstructured":"J. Vondrak,\n                      Symmetry and approximability of submodular maximization problems\n                      , in Proceedings of the 50th IEEE Symposium on Foundations of Computer Science, 2009.","DOI":"10.1109\/FOCS.2009.24"},{"key":"R44","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579435"},{"key":"R45","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-004-0510-2"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/100783352","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:33:10Z","timestamp":1787337190000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/100783352"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1]]},"references-count":45,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["10.1137\/100783352"],"URL":"https:\/\/doi.org\/10.1137\/100783352","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1]]}}}