{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,15]],"date-time":"2025-10-15T10:30:29Z","timestamp":1760524229971,"version":"3.40.3"},"publisher-location":"Cham","reference-count":32,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030799861"},{"type":"electronic","value":"9783030799878"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-79987-8_36","type":"book-chapter","created":{"date-parts":[[2021,6,29]],"date-time":"2021-06-29T23:05:05Z","timestamp":1625007905000},"page":"516-530","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["New Approximations and Hardness Results for Submodular Partitioning Problems"],"prefix":"10.1007","author":[{"given":"Richard","family":"Santiago","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,6,30]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Bhaskara, A., Charikar, M., Chlamtac, E., Feige, U., Vijayaraghavan, A.: Detecting high log-densities: an $$o(n^{1\/4})$$ approximation for densest k-subgraph. In: Proceedings of the Forty-second ACM Symposium on Theory of Computing, pp. 201\u2013210. ACM (2010)","key":"36_CR1","DOI":"10.1145\/1806689.1806719"},{"doi-asserted-by":"crossref","unstructured":"Chandrasekaran, K., Chekuri, C.: Hypergraph $$ k $$-cut for fixed $$ k $$ in deterministic polynomial time. In: 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pp. 810\u2013821 (2020)","key":"36_CR2","DOI":"10.1109\/FOCS46700.2020.00080"},{"doi-asserted-by":"crossref","unstructured":"Chandrasekaran, K., Xu, C., Yu, X.: Hypergraph k-cut in randomized polynomial time. Math. Program. 1\u201329 (2019)","key":"36_CR3","DOI":"10.1007\/s10107-019-01443-7"},{"doi-asserted-by":"crossref","unstructured":"Chekuri, C., Ene, A.: Approximation algorithms for submodular multiway partition. In: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 807\u2013816. IEEE (2011)","key":"36_CR4","DOI":"10.1109\/FOCS.2011.34"},{"doi-asserted-by":"crossref","unstructured":"Chekuri, C., Ene, A.: Submodular cost allocation problem and applications. In: International Colloquium on Automata, Languages, and Programming, pp. 354\u2013366. Springer (2011). Extended version: arXiv preprint arXiv:1105.2040","key":"36_CR5","DOI":"10.1007\/978-3-642-22006-7_30"},{"issue":"1","key":"36_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4086\/toc.2020.v016a014","volume":"16","author":"C Chekuri","year":"2020","unstructured":"Chekuri, C., Li, S.: On the hardness of approximating the $$ k $$-way hypergraph cut problem. Theory Comput. 16(1), 1\u20138 (2020)","journal-title":"Theory Comput."},{"issue":"1\u20133","key":"36_CR7","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/S0166-218X(98)00087-0","volume":"90","author":"S Chopra","year":"1999","unstructured":"Chopra, S., Owen, J.H.: A note on formulations for the a-partition problem on hypergraphs. Discrete Appl. Math. 90(1\u20133), 115\u2013133 (1999)","journal-title":"Discrete Appl. Math."},{"unstructured":"Ene, A., Vondr\u00e1k, J.: Hardness of submodular cost allocation: lattice matching and a simplex coloring conjecture. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2014), vol. 28, pp. 144\u2013159 (2014)","key":"36_CR8"},{"doi-asserted-by":"crossref","unstructured":"Ene, A., Vondr\u00e1k, J., Wu, Y.: Local distribution and the symmetry gap: approximability of multiway partitioning problems. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 306\u2013325. SIAM (2013)","key":"36_CR9","DOI":"10.1137\/1.9781611973105.23"},{"issue":"4","key":"36_CR10","doi-asserted-by":"publisher","first-page":"1133","DOI":"10.1137\/090779346","volume":"40","author":"U Feige","year":"2011","unstructured":"Feige, U., Mirrokni, V.S., Vondrak, J.: Maximizing non-monotone submodular functions. SIAM J. Comput. 40(4), 1133\u20131153 (2011)","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Goel, G., Karande, C., Tripathi, P., Wang, L.: Approximability of combinatorial problems with multi-agent submodular cost functions. In: 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, pp. 755\u2013764. IEEE (2009)","key":"36_CR11","DOI":"10.1109\/FOCS.2009.81"},{"doi-asserted-by":"crossref","unstructured":"Goemans, M.X., Harvey, N.J., Iwata, S., Mirrokni, V.: Approximating submodular functions everywhere. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 535\u2013544. Society for Industrial and Applied Mathematics (2009)","key":"36_CR12","DOI":"10.1137\/1.9781611973068.59"},{"issue":"1","key":"36_CR13","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1287\/moor.19.1.24","volume":"19","author":"O Goldschmidt","year":"1994","unstructured":"Goldschmidt, O., Hochbaum, D.S.: A polynomial algorithm for the k-cut problem for fixed k. Math. Oper. Res. 19(1), 24\u201337 (1994)","journal-title":"Math. Oper. Res."},{"unstructured":"Guinez, F., Queyranne, M.: The size-constrained submodular k-partition problem (2012). https:\/\/docs.google.com\/viewer?a=v&pid=sites&srcid=ZGVmYXVsdGRvbWFpbnxmbGF2aW9ndWluZXpob21lcGFnZXxneDo0NDVlMThkMDg4ZWRlOGI1","key":"36_CR14"},{"unstructured":"Hayrapetyan, A., Swamy, C., Tardos, \u00c9.: Network design for information networks. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 933\u2013942. Society for Industrial and Applied Mathematics (2005)","key":"36_CR15"},{"doi-asserted-by":"crossref","unstructured":"Iwata, S., Nagano, K.: Submodular function minimization under covering constraints. In: 2009 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, pp. 671\u2013680. IEEE (2009)","key":"36_CR16","DOI":"10.1109\/FOCS.2009.31"},{"unstructured":"Iyer, R., Jegelka, S., Bilmes, J.: Monotone closure of relaxed constraints in submodular optimization: Connections between minimization and maximization: Extended version (2014)","key":"36_CR17"},{"issue":"4","key":"36_CR18","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1145\/234533.234534","volume":"43","author":"DR Karger","year":"1996","unstructured":"Karger, D.R., Stein, C.: A new approach to the minimum cut problem. J. ACM (JACM) 43(4), 601\u2013640 (1996)","journal-title":"J. ACM (JACM)"},{"issue":"1","key":"36_CR19","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/s00453-012-9629-3","volume":"66","author":"C Koufogiannakis","year":"2013","unstructured":"Koufogiannakis, C., Young, N.E.: Greedy $$\\delta $$-approximation algorithm for covering with arbitrary constraints and submodular cost. Algorithmica 66(1), 113\u2013152 (2013)","journal-title":"Algorithmica"},{"doi-asserted-by":"publisher","unstructured":"Lov\u00e1sz, L.: Submodular functions and convexity. In: Bachem, A., Korte, B., Grotschel, M. (eds.) Mathematical Programming The State of the Art, pp. 235\u2013257. Springer, Heidelberg (1983). https:\/\/doi.org\/10.1007\/978-3-642-68874-4_10","key":"36_CR20","DOI":"10.1007\/978-3-642-68874-4_10"},{"doi-asserted-by":"crossref","unstructured":"Manurangsi, P.: Almost-polynomial ratio eth-hardness of approximating densest k-subgraph. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 954\u2013961 (2017)","key":"36_CR21","DOI":"10.1145\/3055399.3055412"},{"issue":"1","key":"36_CR22","doi-asserted-by":"publisher","first-page":"10","DOI":"10.3390\/a11010010","volume":"11","author":"P Manurangsi","year":"2018","unstructured":"Manurangsi, P.: Inapproximability of maximum biclique problems, minimum k-cut and densest at-least-k-subgraph from the small set expansion hypothesis. Algorithms 11(1), 10 (2018)","journal-title":"Algorithms"},{"issue":"3\u20134","key":"36_CR23","doi-asserted-by":"publisher","first-page":"787","DOI":"10.1007\/s00453-010-9483-0","volume":"62","author":"K Okumoto","year":"2012","unstructured":"Okumoto, K., Fukunaga, T., Nagamochi, H.: Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems. Algorithmica 62(3\u20134), 787\u2013806 (2012)","journal-title":"Algorithmica"},{"unstructured":"Queyranne, M.: On optimum size-constrained set partitions. Presented at 3rd Combinatorial Optimization Workshop, AUSSOIS 1999, France (1999). http:\/\/www.iasi.cnr.it\/iasi\/aussois99\/queyranne.html","key":"36_CR24"},{"unstructured":"Santiago, R.: Multi-Agent submodular optimization: variations and generalizations. Ph.D. thesis, McGill University (2019)","key":"36_CR25"},{"unstructured":"Santiago, R., Shepherd, F.B.: Multi-agent submodular optimization. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2018), vol. 116, pp. 23:1\u201323:20 (2018)","key":"36_CR26"},{"unstructured":"Santiago, R., Shepherd, F.B.: Multivariate submodular optimization. In: Proceedings of the 36th International Conference on Machine Learning (ICML). pp. 5599\u20135609 (2019), http:\/\/proceedings.mlr.press\/v97\/santiago19a.html","key":"36_CR27"},{"issue":"1","key":"36_CR28","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1137\/S0097539792251730","volume":"24","author":"H Saran","year":"1995","unstructured":"Saran, H., Vazirani, V.V.: Finding k cuts within twice the optimal. SIAM J. Comput. 24(1), 101\u2013108 (1995)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"36_CR29","doi-asserted-by":"publisher","first-page":"1715","DOI":"10.1137\/100783352","volume":"40","author":"Z Svitkina","year":"2011","unstructured":"Svitkina, Z., Fleischer, L.: Submodular approximation: sampling-based algorithms and lower bounds. SIAM J. Comput. 40(6), 1715\u20131737 (2011)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"36_CR30","first-page":"37","volume":"6","author":"Z Svitkina","year":"2010","unstructured":"Svitkina, Z., Tardos, \u00c9.: Facility location with hierarchical facility costs. ACM Trans. Algorithms (TALG) 6(2), 37 (2010)","journal-title":"ACM Trans. Algorithms (TALG)"},{"unstructured":"Zhao, L.: Approximation algorithms for partition and design problems in networks. Ph.D. Thesis (2002)","key":"36_CR31"},{"issue":"1","key":"36_CR32","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/s10107-004-0510-2","volume":"102","author":"L Zhao","year":"2005","unstructured":"Zhao, L., Nagamochi, H., Ibaraki, T.: Greedy splitting algorithms for approximating multiway partition problems. Math. Program. 102(1), 167\u2013183 (2005)","journal-title":"Math. Program."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-79987-8_36","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,29]],"date-time":"2021-06-29T23:15:35Z","timestamp":1625008535000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-79987-8_36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030799861","9783030799878"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-79987-8_36","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"30 June 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IWOCA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Combinatorial Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Ottawa, ON","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Canada","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 July 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 July 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"32","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"iwoca2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/iwoca2021.eecs.uottawa.ca\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"107","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"38","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"36% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.1","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"9.1","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"The workshop was held virtually.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}