{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T00:58:28Z","timestamp":1740099508920,"version":"3.37.3"},"publisher-location":"Cham","reference-count":26,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030307851"},{"type":"electronic","value":"9783030307868"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-30786-8_6","type":"book-chapter","created":{"date-parts":[[2019,9,11]],"date-time":"2019-09-11T21:22:57Z","timestamp":1568236977000},"page":"66-78","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Local Approximation of the Maximum Cut in Regular Graphs"],"prefix":"10.1007","author":[{"given":"\u00c9tienne","family":"Bamas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6200-0514","authenticated-orcid":false,"given":"Louis","family":"Esperet","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,9,12]]},"reference":[{"key":"6_CR1","unstructured":"\u00c5strand, M., Polishchuk, V., Rybicki, J., Suomela, J., Uitto, J.: Local algorithms in (weakly) coloured graphs. CoRR abs\/1002.0125 (2010)"},{"key":"6_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/978-3-319-72751-6_4","volume-title":"Algorithms for Sensor Systems","author":"K Censor-Hillel","year":"2017","unstructured":"Censor-Hillel, K., Levy, R., Shachnai, H.: Fast distributed approximation for max-cut. In: Fern\u00e1ndez Anta, A., Jurdzinski, T., Mosteiro, M.A., Zhang, Y. (eds.) ALGOSENSORS 2017. LNCS, vol. 10718, pp. 41\u201356. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-72751-6_4"},{"key":"6_CR3","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1002\/rsa.20547","volume":"47","author":"E Cs\u00f3ka","year":"2015","unstructured":"Cs\u00f3ka, E., Gerencs\u00e9r, B., Harangi, V., Vir\u00e1g, B.: Invariant gaussian processes and independent sets on regular graphs of large girth. Random Struct. Algorithms 47, 284\u2013303 (2015)","journal-title":"Random Struct. Algorithms"},{"key":"6_CR4","doi-asserted-by":"crossref","unstructured":"Chang, Y.-J., Kopelowitz, T., Pettie, S.: An exponential separation between randomized and deterministic complexity in the LOCAL model. In: IEEE 57th Annual Symposium on Foundations of Computer Science (2016)","DOI":"10.1109\/FOCS.2016.72"},{"key":"6_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1007\/978-3-540-87779-0_6","volume-title":"Distributed Computing","author":"A Czygrinow","year":"2008","unstructured":"Czygrinow, A., Ha\u0144\u0107kowiak, M., Wawrzyniak, W.: Fast distributed approximations in planar graphs. In: Taubenfeld, G. (ed.) DISC 2008. LNCS, vol. 5218, pp. 78\u201392. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-87779-0_6"},{"issue":"2","key":"6_CR6","doi-asserted-by":"publisher","first-page":"1190","DOI":"10.1214\/15-AOP1084","volume":"45","author":"A Dembo","year":"2017","unstructured":"Dembo, A., Montanari, A., Sen, S.: Extremal cuts of sparse random graphs. Ann. Probab. 45(2), 1190\u20131217 (2017)","journal-title":"Ann. Probab."},{"key":"6_CR7","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1112\/plms\/s3-2.1.417","volume":"3","author":"P Erd\u0151s","year":"1952","unstructured":"Erd\u0151s, P., Rado, R.: Combinatorial theorems on classifications of subsets of a given set. Proc. Lond. Math. Soc. 3, 417\u2013439 (1952)","journal-title":"Proc. Lond. Math. Soc."},{"key":"6_CR8","first-page":"463","volume":"2","author":"P Erd\u0151s","year":"1935","unstructured":"Erd\u0151s, P., Szekeres, G.: A combinatorial problem in geometry. Compos. Math. 2, 463\u2013470 (1935)","journal-title":"Compos. Math."},{"issue":"2","key":"6_CR9","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1002\/rsa.20738","volume":"52","author":"D Gamarnik","year":"2018","unstructured":"Gamarnik, D., Li, Q.: On the max-cut of sparse random graphs. Random Struct. Algorithms 52(2), 219\u2013262 (2018)","journal-title":"Random Struct. Algorithms"},{"key":"6_CR10","doi-asserted-by":"crossref","unstructured":"Gamarnik, D., Sudan, M.: Limits of local algorithms over sparse random graphs. In: Proceedings of Innovations in Theoretical Computer Science (ITCS), pp. 369\u2013376 (2014)","DOI":"10.1145\/2554797.2554831"},{"key":"6_CR11","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Harris, D.G., Kuhn, F.: On derandomizing local distributed algorithms. In: IEEE Symposium on Foundations of Computer Science (2018)","DOI":"10.1109\/FOCS.2018.00069"},{"key":"6_CR12","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Kuhn, F., Maus, Y.: On the complexity of local distributed graph problems. In: 49th Annual ACM Symposium on Theory of Computing, pp. 784\u2013797 (2017)","DOI":"10.1145\/3055399.3055471"},{"key":"6_CR13","doi-asserted-by":"publisher","first-page":"#39","DOI":"10.1145\/2528405","volume":"60","author":"M G\u00f6\u00f6s","year":"2013","unstructured":"G\u00f6\u00f6s, M., Hirvonen, J., Suomela, J.: Lower bounds for local approximation. J. ACM 60, #39 (2013)","journal-title":"J. ACM"},{"issue":"1","key":"6_CR14","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/s00039-014-0258-7","volume":"24","author":"H Hatami","year":"2014","unstructured":"Hatami, H., Lov\u00e1sz, L., Szegedy, B.: Limits of local-global convergent graph sequences. Geom. Funct. Anal. 24(1), 269\u2013296 (2014)","journal-title":"Geom. Funct. Anal."},{"key":"6_CR15","doi-asserted-by":"crossref","unstructured":"Hirvonen, J., Rybicki, J., Schmid, S., Suomela, J.: Large cuts with local algorithms on triangle-free graphs. Electron. J. Combin. 24(4), #P4.21 (2017)","DOI":"10.37236\/6862"},{"issue":"4","key":"6_CR16","doi-asserted-by":"publisher","first-page":"506","DOI":"10.1002\/rsa.20471","volume":"41","author":"F Kardo\u0161","year":"2012","unstructured":"Kardo\u0161, F., Kr\u00e1l\u2019, D., Volec, J.: Maximum edge-cuts in cubic graphs with large girth and in random cubic graphs. Random Struct. Algorithms 41(4), 506\u2013520 (2012)","journal-title":"Random Struct. Algorithms"},{"key":"6_CR17","unstructured":"Kawarabayashi, K.-I., Schwartzman, G.: Adapting local sequential algorithms to the distributed setting. In: 32nd International Symposium on Distributed Computing, pp. 35:1\u201335:17 (2018)"},{"issue":"1","key":"6_CR18","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1137\/0221015","volume":"21","author":"N Linial","year":"1992","unstructured":"Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput. 21(1), 193\u2013201 (1992)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"6_CR19","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1017\/S096354831600033X","volume":"26","author":"R Lyons","year":"2017","unstructured":"Lyons, R.: Factors of IID on trees. Combin. Probab. Comput. 26(2), 285\u2013300 (2017)","journal-title":"Combin. Probab. Comput."},{"key":"6_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1007\/978-3-642-13073-1_24","volume-title":"Algorithms and Complexity","author":"B Monien","year":"2010","unstructured":"Monien, B., Tscheuschner, T.: On the power of nodes of degree four in the local max-cut problem. In: Calamoneri, T., Diaz, J. (eds.) CIAC 2010. LNCS, vol. 6078, pp. 264\u2013275. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-13073-1_24"},{"key":"6_CR21","unstructured":"Mubayi, D., Suk, A.: A survey of hypergraph Ramsey problems. ArXiv e-prints (2017)"},{"key":"6_CR22","doi-asserted-by":"crossref","unstructured":"Naor, M., Stockmeyer, L.: What can be computed locally?. In: 25th Annual ACM Symposium on Theory of Computing, pp. 184\u2013193 (1993)","DOI":"10.1145\/167088.167149"},{"issue":"3","key":"6_CR23","first-page":"450","volume":"21","author":"S Poljak","year":"1995","unstructured":"Poljak, S.: Integer linear programs and local search for max-cut. SIAM J. Comput. 21(3), 450\u2013465 (1995)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"6_CR24","doi-asserted-by":"publisher","first-page":"1543","DOI":"10.1214\/16-AOP1094","volume":"45","author":"M Rahman","year":"2017","unstructured":"Rahman, M., Vir\u00e1g, B.: Local algorithms for independent sets are half-optimal. Ann. Probab. 45(3), 1543\u20131577 (2017)","journal-title":"Ann. Probab."},{"key":"6_CR25","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1112\/plms\/s2-30.1.264","volume":"30","author":"FP Ramsey","year":"1930","unstructured":"Ramsey, F.P.: On a problem of formal logic. Proc. Lond. Math. Soc. 30, 264\u2013286 (1930)","journal-title":"Proc. Lond. Math. Soc."},{"issue":"2","key":"6_CR26","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1002\/rsa.3240030211","volume":"3","author":"JB Shearer","year":"1992","unstructured":"Shearer, J.B.: A note on bipartite subgraphs of triangle-free graphs. Random Struct. Algorithms 3(2), 223\u2013226 (1992)","journal-title":"Random Struct. Algorithms"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-30786-8_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,20]],"date-time":"2021-01-20T04:01:28Z","timestamp":1611115288000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-30786-8_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030307851","9783030307868"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-30786-8_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"12 September 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WG","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Graph-Theoretic Concepts in Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Vall de N\u00faria","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Spain","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 June 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 June 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"45","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wg2019a","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/wg2019.sau.thilikos.info\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Open","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":"87","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":"29","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":"33% - 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.4","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":"1-2","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)"}}]}}