{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,12]],"date-time":"2025-12-12T02:34:03Z","timestamp":1765506843171,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":47,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,17]],"date-time":"2023-06-17T00:00:00Z","timestamp":1686960000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,17]]},"DOI":"10.1145\/3558481.3591087","type":"proceedings-article","created":{"date-parts":[[2023,5,31]],"date-time":"2023-05-31T22:22:03Z","timestamp":1685571723000},"page":"415-425","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Partitioning Hypergraphs is Hard: Models, Inapproximability, and Applications"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-6667-802X","authenticated-orcid":false,"given":"P\u00e1l Andr\u00e1s","family":"Papp","sequence":"first","affiliation":[{"name":"Huawei Zurich Research Center, Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5730-5812","authenticated-orcid":false,"given":"Georg","family":"Anegg","sequence":"additional","affiliation":[{"name":"Huawei Zurich Research Center, Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8842-3689","authenticated-orcid":false,"given":"Albert-Jan N.","family":"Yzelman","sequence":"additional","affiliation":[{"name":"Huawei Zurich Research Center, Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,6,17]]},"reference":[{"key":"e_1_3_2_3_1_1","volume-title":"8th Innovations in Theoretical Computer Science Conference (ITCS).","author":"Alwen Jo\u00ebl","year":"2017","unstructured":"Jo\u00ebl Alwen, Susanna F De Rezende, Jakob Nordstr\u00f6m, and Marc Vinyals. 2017. Cumulative space in black-white pebbling and resolution. In 8th Innovations in Theoretical Computer Science Conference (ITCS)."},{"key":"e_1_3_2_3_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-006-1350-7"},{"key":"e_1_3_2_3_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806715"},{"key":"e_1_3_2_3_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1502793.1502794"},{"volume-title":"Parallel Scientific Computation: A Structured Approach Using BSP","author":"Bisseling Rob H","key":"e_1_3_2_3_5_1","unstructured":"Rob H Bisseling. 2020. Parallel Scientific Computation: A Structured Approach Using BSP. Oxford University Press."},{"key":"e_1_3_2_3_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3243734.3243773"},{"key":"e_1_3_2_3_7_1","volume-title":"Recent advances in graph partitioning. Algorithm Engineering","author":"Bulucc Aydin","year":"2016","unstructured":"Aydin Bulucc, Henning Meyerhenke, Ilya Safro, Peter Sanders, and Christian Schulz. 2016. Recent advances in graph partitioning. Algorithm Engineering (2016), 117--158."},{"key":"e_1_3_2_3_8_1","volume-title":"Comput. Surveys","volume":"55","author":"Cataly\u00fcrek \u00dcmit","year":"2023","unstructured":"\u00dcmit cCataly\u00fcrek, Karen Devine, Marcelo Faraj, Lars Gottesb\u00fcren, Tobias Heuer, Henning Meyerhenke, Peter Sanders, Sebastian Schlag, Christian Schulz, Daniel Seemaier, and Dorothea Wagner. 2023. More Recent Advances in (Hyper)Graph Partitioning. Comput. Surveys, Vol. 55, 12, Article 253 (2023)."},{"key":"e_1_3_2_3_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00080"},{"key":"e_1_3_2_3_10_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2020.v016a014"},{"key":"e_1_3_2_3_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.56"},{"key":"e_1_3_2_3_12_1","volume-title":"Optimal scheduling for two-processor systems. Acta informatica","author":"Coffman Edward G","year":"1972","unstructured":"Edward G Coffman and Ronald L Graham. 1972. Optimal scheduling for two-processor systems. Acta informatica, Vol. 1, 3 (1972), 200--213."},{"volume-title":"Proceedings of the 30th Symposium on Parallelism in Algorithms and Architectures (SPAA). ACM.","author":"Erik","key":"e_1_3_2_3_13_1","unstructured":"Erik D. Demaine and Quanquan C. Liu. 2018. Red-Blue Pebble Game: Complexity of Computing the Trade-Off between Cache Size and Memory Transfers. In Proceedings of the 30th Symposium on Parallelism in Algorithms and Architectures (SPAA). ACM."},{"key":"e_1_3_2_3_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(84)90039-7"},{"key":"e_1_3_2_3_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/0606066"},{"key":"e_1_3_2_3_16_1","volume-title":"Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC). ACM, 530--536","author":"Feige Uriel","year":"2000","unstructured":"Uriel Feige, Robert Krauthgamer, and Kobbi Nissim. 2000. Approximating the minimum bisection size. In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC). ACM, 530--536."},{"key":"e_1_3_2_3_17_1","volume-title":"Balanced Partitions of Trees and Applications. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS) (LIPIcs","volume":"111","author":"Feldmann Andreas Emil","year":"2012","unstructured":"Andreas Emil Feldmann and Luca Foschini. 2012. Balanced Partitions of Trees and Applications. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS) (LIPIcs, Vol. 14). 100--111."},{"volume-title":"Parameterized Complexity Theory","author":"Flom J\u00f6rg","key":"e_1_3_2_3_18_1","unstructured":"J\u00f6rg Flom and Martin Grohe. 2006. Parameterized Complexity Theory. Springer."},{"key":"e_1_3_2_3_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/322326.322335"},{"key":"e_1_3_2_3_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196275"},{"key":"e_1_3_2_3_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/0604011"},{"key":"e_1_3_2_3_22_1","unstructured":"M. R. Garey and D. S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman."},{"key":"e_1_3_2_3_23_1","volume-title":"Hochbaum","author":"Goldschmidt Olivier","year":"1994","unstructured":"Olivier Goldschmidt and Dorit S. Hochbaum. 1994. A polynomial algorithm for the k-cut problem for fixed k. Mathematics of operations research, Vol. 19 (1994), 24--37."},{"key":"e_1_3_2_3_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2612669.2612699"},{"key":"e_1_3_2_3_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0018541"},{"key":"e_1_3_2_3_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(00)00048-X"},{"key":"e_1_3_2_3_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/92.748202"},{"key":"e_1_3_2_3_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/509058.509086"},{"key":"e_1_3_2_3_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2020.102640"},{"key":"e_1_3_2_3_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/050640904"},{"key":"e_1_3_2_3_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973068.102"},{"key":"e_1_3_2_3_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331526"},{"key":"e_1_3_2_3_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055412"},{"key":"e_1_3_2_3_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPPS.1993.262865"},{"key":"e_1_3_2_3_35_1","volume-title":"Hypergraph Partitioning and Clustering. Handbook of Approximation Algorithms and Metaheuristics","author":"Papa David A","year":"2007","unstructured":"David A Papa and Igor L Markov. 2007. Hypergraph Partitioning and Clustering. Handbook of Approximation Algorithms and Metaheuristics (2007)."},{"key":"e_1_3_2_3_36_1","volume-title":"Hard: Models, Inapproximability, and Applications. arXiv preprint arXiv:2208.08257.","author":"Papp P\u00e1l Andr\u00e1s","year":"2023","unstructured":"P\u00e1l Andr\u00e1s Papp, Georg Anegg, and A. N. Yzelman. 2023. Partitioning Hypergraphs is Hard: Models, Inapproximability, and Applications. arXiv preprint arXiv:2208.08257."},{"volume-title":"Combinatorial Tiling for Sparse Neural Networks. In IEEE High Performance Extreme Computing Conference (HPEC). 1--7.","author":"Paw\u0140owski Filip","key":"e_1_3_2_3_37_1","unstructured":"Filip Paw\u0140owski, Rob H. Bisseling, Bora U\u00e7ar, and A. N. Yzelman. 2020. Combinatorial Tiling for Sparse Neural Networks. In IEEE High Performance Extreme Computing Conference (HPEC). 1--7."},{"key":"e_1_3_2_3_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2015.06.005"},{"key":"e_1_3_2_3_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976472.1"},{"key":"e_1_3_2_3_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374415"},{"key":"e_1_3_2_3_41_1","volume-title":"Hypergraph Cuts and Minimum Hypergraph Bisection. In 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). ACM, 23--32","author":"R\u00e4cke Harald","year":"2018","unstructured":"Harald R\u00e4cke, Roy Schwartz, and Richard Stotz. 2018. Trees for Vertex Cuts, Hypergraph Cuts and Minimum Hypergraph Bisection. In 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). ACM, 23--32."},{"key":"e_1_3_2_3_42_1","volume-title":"Improved Approximation Algorithms for Balanced Partitioning Problems. In 33rd International Symposium on Theoretical Aspects of Computer Science (STACS) (LIPIcs","volume":"14","author":"R\u00e4cke Harald","year":"2016","unstructured":"Harald R\u00e4cke and Richard Stotz. 2016. Improved Approximation Algorithms for Balanced Partitioning Problems. In 33rd International Symposium on Theoretical Aspects of Computer Science (STACS) (LIPIcs, Vol. 47). 58:1--58:14."},{"key":"e_1_3_2_3_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792251730"},{"key":"e_1_3_2_3_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974317.5"},{"key":"e_1_3_2_3_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/0205005"},{"key":"e_1_3_2_3_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2007.11.002"},{"key":"e_1_3_2_3_47_1","volume-title":"SIAM Workshop on Scientific Computation","author":"Yzelman Albert-Jan","year":"2016","unstructured":"Albert-Jan Yzelman. 2016. Sparse computations and Multi-BSP. SIAM Workshop on Scientific Computation (2016)."}],"event":{"name":"SPAA '23: 35th ACM Symposium on Parallelism in Algorithms and Architectures","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGARCH ACM Special Interest Group on Computer Architecture","EATCS European Association for Theoretical Computer Science"],"location":"Orlando FL USA","acronym":"SPAA '23"},"container-title":["Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3558481.3591087","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3558481.3591087","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:06Z","timestamp":1750178826000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3558481.3591087"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,17]]},"references-count":47,"alternative-id":["10.1145\/3558481.3591087","10.1145\/3558481"],"URL":"https:\/\/doi.org\/10.1145\/3558481.3591087","relation":{},"subject":[],"published":{"date-parts":[[2023,6,17]]},"assertion":[{"value":"2023-06-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}