{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T07:42:41Z","timestamp":1742974961591,"version":"3.40.3"},"publisher-location":"Cham","reference-count":20,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031491924"},{"type":"electronic","value":"9783031491931"}],"license":[{"start":{"date-parts":[[2023,12,9]],"date-time":"2023-12-09T00:00:00Z","timestamp":1702080000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,12,9]],"date-time":"2023-12-09T00:00:00Z","timestamp":1702080000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-3-031-49193-1_9","type":"book-chapter","created":{"date-parts":[[2023,12,8]],"date-time":"2023-12-08T09:02:36Z","timestamp":1702026156000},"page":"106-117","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["The Hardness of\u00a0Optimization Problems on\u00a0the\u00a0Weighted Massively Parallel Computation Model"],"prefix":"10.1007","author":[{"given":"Hengzhao","family":"Ma","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianzhong","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,12,9]]},"reference":[{"key":"9_CR1","unstructured":"Afrati, F.N., Joglekar, M.R., Re, C.M., Salihoglu, S., Ullman, J.D.: GYM: a multiround distributed join algorithm. In: Leibniz International Proceedings in Informatics, LIPIcs, vol. 68, pp. 4:1\u20134:18 (2017)"},{"key":"9_CR2","doi-asserted-by":"crossref","unstructured":"Afrati, F.N., Ullman, J.D.: Optimizing joins in a map-reduce environment. In: Advances in Database Technology - EDBT 2010\u201313th International Conference on Extending Database Technology, Proceedings, pp. 99\u2013110. ACM Press, New York (2010)","DOI":"10.1145\/1739041.1739056"},{"key":"9_CR3","doi-asserted-by":"crossref","unstructured":"Andoni, A., Nikolov, A., Onak, K., Yaroslavtsev, G.: Parallel algorithms for geometric graph problems. In: Shmoys, D.B. (ed) Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pp. 574\u2013583. ACM, (2014)","DOI":"10.1145\/2591796.2591805"},{"key":"9_CR4","doi-asserted-by":"crossref","unstructured":"Beame, P., Koutris, P., Suciu, D.: Communication steps for parallel query processing. In: Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, vol. 64, pp. 273\u2013284. ACM Press, New York, USA (2013)","DOI":"10.1145\/2463664.2465224"},{"key":"9_CR5","doi-asserted-by":"crossref","unstructured":"Beame, P., Koutris, P., Suciu, D.: Skew in parallel query processing. In: Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 212\u2013223. Association for Computing Machinery (2014)","DOI":"10.1145\/2594538.2594558"},{"key":"9_CR6","unstructured":"Blanas, S.: Topology-aware parallel data processing : models, algorithms and systems at scale. In: 10th Annual Conference on Innovative Data Systems Research (CIDR 2020) (2020)"},{"key":"9_CR7","doi-asserted-by":"crossref","unstructured":"Chang, Y.-J., Fischer, M., Ghaffari, M., Uitto, J., Zheng, Y.: The complexity of ($$\\delta $$+ 1) coloring in congested clique, massively parallel computation, and centralized local computation. In: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pp. 471\u2013480 (2019)","DOI":"10.1145\/3293611.3331607"},{"issue":"11","key":"9_CR8","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1145\/240455.240477","volume":"39","author":"DE Culler","year":"1996","unstructured":"Culler, D.E., et al.: LogP: a practical model of parallel computation. Commun. ACM 39(11), 78\u201385 (1996)","journal-title":"Commun. ACM"},{"issue":"1","key":"9_CR9","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1145\/1327452.1327492","volume":"51","author":"J Dean","year":"2008","unstructured":"Dean, J., Ghemawat, S.: MapReduce: simplified data processing on large clusters. Commun. ACM 51(1), 107\u2013113 (2008)","journal-title":"Commun. ACM"},{"key":"9_CR10","doi-asserted-by":"crossref","unstructured":"Dory, M., Fischer, O., Khoury, S., Leitersdorf, D.: Constant-round spanners and shortest paths in congested clique and MPC. In: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, pp. 223\u2013233 (2021)","DOI":"10.1145\/3465084.3467928"},{"key":"9_CR11","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Gouleakis, T., Konrad, C., Mitrovi\u0107, S., Rubinfeld, R.: Improved massively parallel computation algorithms for MIS, matching, and vertex cover. In: Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, pp. 129\u2013138. ACM, New York, NY, USA (2018)","DOI":"10.1145\/3212734.3212743"},{"key":"9_CR12","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Kuhn, F.: Distributed minimum cut approximation. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), volume 8205 LNCS, pp. 1\u201315 (2013)","DOI":"10.1007\/978-3-642-41527-2_1"},{"key":"9_CR13","doi-asserted-by":"crossref","unstructured":"Hu, X., Koutris, P., Blanas, S.: Algorithms for a topology-aware massively parallel computation model. In: Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 199\u2013214. Association for Computing Machinery (2021)","DOI":"10.1145\/3452021.3458318"},{"key":"9_CR14","doi-asserted-by":"crossref","unstructured":"Karloff, H., Suri, S., Vassilvitskii, S.: A model of computation for MapReduce. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 938\u2013948. Society for Industrial and Applied Mathematics, Philadelphia, PA (2010)","DOI":"10.1137\/1.9781611973075.76"},{"key":"9_CR15","unstructured":"Karp, R.M.: A Survey of Parallel Algorithms for Shared-memory Machines (1988)"},{"key":"9_CR16","doi-asserted-by":"crossref","unstructured":"Koutris, P., Suciu, D.: Parallel evaluation of conjunctive queries. In: Lenzerini, M., Schwentick, T. (eds) Proceedings of the 30th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2011, June 12\u201316, 2011, Athens, Greece, pp. 223\u2013234. ACM (2011)","DOI":"10.1145\/1989284.1989310"},{"key":"9_CR17","doi-asserted-by":"crossref","unstructured":"Ma, H., Li, J., Gao, X.: Optimization problems on the weighted massively parallel computation model: hardness and algorithms. arXiv preprint arXiv:2302.12953 (2023)","DOI":"10.1007\/978-3-031-49193-1_9"},{"key":"9_CR18","unstructured":"O\u2019malley, O.: Terabyte sort on apache hadoop, pp. 1\u20133 (2008). https:\/\/sortbenchmark.org\/Yahoo-Hadoop. pdf"},{"key":"9_CR19","doi-asserted-by":"crossref","unstructured":"Tao, Y., Lin, W., Xiao, X.: Minimal MapReduce algorithms. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, number June, pp. 529\u2013540. ACM Press, New York, New York, USA (2013)","DOI":"10.1145\/2463676.2463719"},{"issue":"8","key":"9_CR20","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1145\/79173.79181","volume":"33","author":"LG Valiant","year":"1990","unstructured":"Valiant, L.G.: A bridging model for parallel computation. Commun. ACM 33(8), 103\u2013111 (1990)","journal-title":"Commun. ACM"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-49193-1_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,27]],"date-time":"2023-12-27T17:34:32Z","timestamp":1703698472000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-49193-1_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,9]]},"ISBN":["9783031491924","9783031491931"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-49193-1_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023,12,9]]},"assertion":[{"value":"9 December 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOON","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computing and Combinatorics Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Hawaii, HI","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 December 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 December 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/theory.utdallas.edu\/COCOON2023\/org.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Springer EquinOCS","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"146","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":"60","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":"41% - 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","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":"6","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":"No","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}