{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,20]],"date-time":"2025-07-20T04:13:29Z","timestamp":1752984809191,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":63,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,16]],"date-time":"2023-06-16T00:00:00Z","timestamp":1686873600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,19]]},"DOI":"10.1145\/3583668.3594562","type":"proceedings-article","created":{"date-parts":[[2023,6,16]],"date-time":"2023-06-16T22:28:38Z","timestamp":1686954518000},"page":"32-43","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0109-2432","authenticated-orcid":false,"given":"Yi-Jun","family":"Chang","sequence":"first","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-8121-5149","authenticated-orcid":false,"given":"Zeyong","family":"Li","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}]}],"member":"320","published-online":{"date-parts":[[2023,6,16]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3326170"},{"volume-title":"Proceedings of the 30th IEEE Symposium on Foundations of Computer Science (FOCS). 364--369","author":"Awerbuch Baruch","key":"e_1_3_2_1_2_1","unstructured":"Baruch Awerbuch, Andrew V. Goldberg, Michael Luby, and Serge A. Plotkin. 1989. Network Decomposition and Locality in Distributed Computation. In Proceedings of the 30th IEEE Symposium on Foundations of Computer Science (FOCS). 364--369."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331597"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch100"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.OPODIS.2021.18"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087806"},{"volume-title":"Proceedings 35th Annual ACM Symposium on Principles of Distributed Computing (PODC). 3--8.","author":"Bar-Yehuda R.","key":"e_1_3_2_1_7_1","unstructured":"R. Bar-Yehuda, K. Censor-Hillel, and G. Schwartzman. 2016. A Distributed (2 + \u03f5)-Approximation for Vertex Cover in O(log \u0394\/\u03f5 log log \u0394) Rounds. In Proceedings 35th Annual ACM Symposium on Principles of Distributed Computing (PODC). 3--8."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331577"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933068"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.171"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382734.3405742"},{"volume-title":"Algorithms for Sensor Systems, Antonio Fern\u00e1ndez Anta, Tomasz Jurdzinski, Miguel A","author":"Censor-Hillel Keren","key":"e_1_3_2_1_12_1","unstructured":"Keren Censor-Hillel, Rina Levy, and Hadas Shachnai. 2017. Fast Distributed Approximation for Max-Cut. In Algorithms for Sensor Systems, Antonio Fern\u00e1ndez Anta, Tomasz Jurdzinski, Miguel A. Mosteiro, and Yanyong Zhang (Eds.). Springer International Publishing, Cham, 41--56."},{"key":"e_1_3_2_1_13_1","volume-title":"Proceedings of the 42th ACM Symposium on Principles of Distributed Computing (PODC). ACM.","author":"Chang Yi-Jun","year":"2023","unstructured":"Yi-Jun Chang. 2023. Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications. In Proceedings of the 42th ACM Symposium on Principles of Distributed Computing (PODC). ACM."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212774"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382734.3405713"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3465084.3467933"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Yi-Jun Chang and Zeyong Li. 2023. The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs. arXiv:2305.01324 [cs.DS]","DOI":"10.1145\/3583668.3594562"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331618"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00043"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519270.3538423"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087825"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_24"},{"volume-title":"Proceedings of the 13th Annual International Conference on Computing and Combinatorics (COCOON). Springer-Verlag","author":"Czygrinow A.","key":"e_1_3_2_1_23_1","unstructured":"A. Czygrinow and M. Ha\u0144\u0107kowiak. 2007. Distributed Approximation Algorithms for Weighted Problems in Minor-Closed Families. In Proceedings of the 13th Annual International Conference on Computing and Combinatorics (COCOON). Springer-Verlag, Berlin, Heidelberg, 515--525."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87779-0_6"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2019.12.027"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2005.07.006"},{"key":"e_1_3_2_1_27_1","volume-title":"How to Wake Up Your Neighbors: Safe and Nearly Optimal Generic Energy Conservation in Radio Networks. arXiv preprint arXiv:2205.12830","author":"Dani Varsha","year":"2022","unstructured":"Varsha Dani and Thomas P Hayes. 2022. How to Wake Up Your Neighbors: Safe and Nearly Optimal Generic Energy Conservation in Radio Networks. arXiv preprint arXiv:2205.12830 (2022)."},{"key":"e_1_3_2_1_28_1","volume-title":"Proceedings of the International Symposium on Distributed Computing (DISC). 15:1--15:16","author":"Eden Talya","year":"2019","unstructured":"Talya Eden, Nimrod Fiat, Orr Fischer, Fabian Kuhn, and Rotem Oshman. 2019. Sublinear-Time Distributed Algorithms for Detecting Small Cliques and Even Cycles. In Proceedings of the International Symposium on Distributed Computing (DISC). 15:1--15:16."},{"key":"e_1_3_2_1_29_1","volume-title":"Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and Parallel Applications. arXiv preprint arXiv:2204.08254","author":"Elkin Michael","year":"2022","unstructured":"Michael Elkin, Bernhard Haeupler, V\u00e1clav Rozho\u0148, and Christoph Grunau. 2022. Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and Parallel Applications. arXiv preprint arXiv:2204.08254 (2022)."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933094"},{"key":"e_1_3_2_1_31_1","first-page":"1","article-title":"Efficient algorithms for constructing very sparse spanners and emulators","volume":"15","author":"Elkin Michael","year":"2018","unstructured":"Michael Elkin and Ofer Neiman. 2018. Efficient algorithms for constructing very sparse spanners and emulators. ACM Transactions on Algorithms (TALG) 15, 1 (2018), 1--29.","journal-title":"ACM Transactions on Algorithms (TALG)"},{"key":"e_1_3_2_1_32_1","volume-title":"Proceedings 31st International Symposium on Distributed Computing (DISC) (Leibniz International Proceedings in Informatics (LIPIcs)","volume":"30","author":"Even Guy","year":"2017","unstructured":"Guy Even, Orr Fischer, Pierre Fraigniaud, Tzlil Gonen, Reut Levi, Moti Medina, Pedro Montealegre, Dennis Olivetti, Rotem Oshman, Ivan Rapaport, and Ioan Todinca. 2017. Three Notes on Distributed Property Testing. In Proceedings 31st International Symposium on Distributed Computing (DISC) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 91). 15:1--15:30."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.OPODIS.2021.17"},{"key":"e_1_3_2_1_34_1","volume-title":"24th International Conference on Principles of Distributed Systems (OPODIS","author":"Faour Salwa","year":"2021","unstructured":"Salwa Faour and Fabian Kuhn. 2021. Approximating bipartite minimum vertex cover in the CONGEST model. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik."},{"volume-title":"Proceedings 58th IEEE Symposium on Foundations of Computer Science (FOCS).","author":"Fischer M.","key":"e_1_3_2_1_35_1","unstructured":"M. Fischer, M. Ghaffari, and F. Kuhn. 2017. Deterministic Distributed Edge Coloring via Hypergraph Maximal Matching. In Proceedings 58th IEEE Symposium on Foundations of Computer Science (FOCS)."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520039"},{"key":"e_1_3_2_1_37_1","volume-title":"Maximum matchings in regular graphs of high girth. the electronic journal of combinatorics #N1","author":"Flaxman Abraham D","year":"2007","unstructured":"Abraham D Flaxman and Shlomo Hoory. 2007. Maximum matchings in regular graphs of high girth. the electronic journal of combinatorics #N1 (2007)."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.OPODIS.2021.16"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.50"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2209.11669"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.173"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055471"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188906"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.DISC.2019.18"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2528405"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-013-0194-z"},{"volume-title":"Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (PODC). ACM, 361--370","author":"Haeupler B.","key":"e_1_3_2_1_47_1","unstructured":"B. Haeupler and D. Wajc. 2016. A faster distributed radio broadcast primitive. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (PODC). ACM, 361--370."},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.STACS.2020.23"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2742012"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0929"},{"key":"e_1_3_2_1_51_1","volume-title":"Proceedings of the 32nd International Symposium on Algorithms and Computation (ISAAC).","author":"Gall Fran\u00e7ois Le","year":"2021","unstructured":"Fran\u00e7ois Le Gall and Masayuki Miyamoto. 2021. Lower Bounds for Induced Cycle Detection in Distributed Computing. In Proceedings of the 32nd International Symposium on Algorithms and Computation (ISAAC)."},{"key":"e_1_3_2_1_52_1","volume-title":"Distributed minimum dominating set approximations in restricted families of graphs. Distributed computing 26, 2","author":"Lenzen Christoph","year":"2013","unstructured":"Christoph Lenzen, Yvonne-Anne Pignolet, and Roger Wattenhofer. 2013. Distributed minimum dominating set approximations in restricted families of graphs. Distributed computing 26, 2 (2013), 119--137."},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-020-00382-3"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221015"},{"key":"e_1_3_2_1_55_1","volume-title":"Low diameter graph decompositions. Combinatorica 13, 4 (01","author":"Linial Nathan","year":"1993","unstructured":"Nathan Linial and Michael Saks. 1993. Low diameter graph decompositions. Combinatorica 13, 4 (01 Dec 1993), 441--454."},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786753"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1137\/080714403"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.DISC.2021.31"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/2486159.2486180"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129769"},{"volume-title":"Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, Michel Goemans, Klaus Jansen, Jos\u00e9 D","author":"Pemmaraju Sriram V.","key":"e_1_3_2_1_61_1","unstructured":"Sriram V. Pemmaraju. 2001. Equitable Coloring Extends Chernoff-Hoeffding Bounds. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, Michel Goemans, Klaus Jansen, Jos\u00e9 D. P. Rolim, and Luca Trevisan (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 285--296."},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384298"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.DISC.2020.15"}],"event":{"name":"PODC '23: 2023 ACM Symposium on Principles of Distributed Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGOPS ACM Special Interest Group on Operating Systems"],"location":"Orlando FL USA","acronym":"PODC '23"},"container-title":["Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3583668.3594562","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3583668.3594562","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:37:54Z","timestamp":1750178274000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3583668.3594562"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,16]]},"references-count":63,"alternative-id":["10.1145\/3583668.3594562","10.1145\/3583668"],"URL":"https:\/\/doi.org\/10.1145\/3583668.3594562","relation":{},"subject":[],"published":{"date-parts":[[2023,6,16]]},"assertion":[{"value":"2023-06-16","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}