{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T23:12:11Z","timestamp":1743117131887,"version":"3.40.3"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030895426"},{"type":"electronic","value":"9783030895433"}],"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-89543-3_11","type":"book-chapter","created":{"date-parts":[[2021,10,21]],"date-time":"2021-10-21T02:03:25Z","timestamp":1634781805000},"page":"124-136","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Sublinear-Space Approximation Algorithms for Max r-SAT"],"prefix":"10.1007","author":[{"given":"Arindam","family":"Biswas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Venkatesh","family":"Raman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,10,20]]},"reference":[{"key":"11_CR1","doi-asserted-by":"publisher","unstructured":"Asano, T., Kirkpatrick, D., Nakagawa, K., Watanabe, O.: $$\\widetilde{O}(\\sqrt{n})$$-space and polynomial-time algorithm for planar directed graph reachability. In: Csuhaj-Varj\u00fa, E., Dietzfelbinger, M., \u00c9sik, Z. (eds.) MFCS 2014. LNCS, vol. 8635, pp. 45\u201356. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-662-44465-8_5","DOI":"10.1007\/978-3-662-44465-8_5"},{"issue":"1","key":"11_CR2","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/j.ic.2003.09.002","volume":"189","author":"E Allender","year":"2004","unstructured":"Allender, E., Mahajan, M.: The complexity of planarity testing. Inf. Comput. 189(1), 117\u2013134 (2004). ISSN 08905401","journal-title":"Inf. Comput."},{"issue":"1","key":"11_CR3","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"BS Baker","year":"1994","unstructured":"Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. J. ACM 41(1), 153\u2013180 (1994). ISSN 0004-5411, 1557-735X","journal-title":"J. ACM"},{"issue":"5","key":"11_CR4","doi-asserted-by":"publisher","first-page":"1273","DOI":"10.1137\/S0097539793283151","volume":"27","author":"G Barnes","year":"1998","unstructured":"Barnes, G., Buss, J.F., Ruzzo, W.L., Schieber, B.: A sublinear space, polynomial time algorithm for directed s-t connectivity. SIAM J. Comput. 27(5), 1273\u20131282 (1998). ISSN 0097-5397, 1095-7111","journal-title":"SIAM J. Comput."},{"key":"11_CR5","doi-asserted-by":"crossref","unstructured":"Biswas, A., Raman, V., Saurabh, S.: Approximation in (poly-) logarithmic space. Algorithmica 83(7), 2303\u20132331 (2021). ISSN 0178-4617, 1432-0541","DOI":"10.1007\/s00453-021-00826-7"},{"key":"11_CR6","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209(1\u20132), 1\u201345 (1998). ISSN 03043975","DOI":"10.1016\/S0304-3975(97)00228-4"},{"issue":"3","key":"11_CR7","doi-asserted-by":"publisher","first-page":"622","DOI":"10.1006\/jcss.1998.1612","volume":"58","author":"J Chen","year":"1999","unstructured":"Chen, J., Friesen, D.K., Zheng, H.: Tight bound on Johnson\u2019s algorithm for maximum satisfiability. J. Comput. Syst. Sci. 58(3), 622\u2013640 (1999). ISSN 00220000","journal-title":"J. Comput. Syst. Sci."},{"key":"11_CR8","doi-asserted-by":"crossref","unstructured":"Chou, C.N., Golovnev, A., Velusamy, S.: Optimal streaming approximations for all Boolean max-2CSPs and max-kSAT. In: 61st Annual Symposium on Foundations of Computer Science, pp. 330\u2013341 (2020). ISBN 978-1-72819-621-3","DOI":"10.1109\/FOCS46700.2020.00039"},{"key":"11_CR9","unstructured":"Chakraborty, D., Tewari, R.: Simultaneous Time-Space Upper Bounds for Certain Problems in Planar Graphs. arXiv Preprint arXiv: 1502.02135v1 (2015)"},{"key":"11_CR10","doi-asserted-by":"crossref","unstructured":"Crescenzi, P., Trevisan, L.: Max NP-completeness made easy. Theor. Comput. Sci. 225(1\u20132), 65\u201379 (1999). ISSN 03043975","DOI":"10.1016\/S0304-3975(98)00200-X"},{"key":"11_CR11","doi-asserted-by":"crossref","unstructured":"Elberfeld, M., Jakoby, A., Tantau, T.: Logspace versions of the theorems of bodlaender and courcelle. In: 51st Annual Symposium on Foundations of Computer Science, pp. 143\u2013152 (2010). ISBN 978-1-4244-8525-3","DOI":"10.1109\/FOCS.2010.21"},{"key":"11_CR12","doi-asserted-by":"crossref","unstructured":"Elberfeld, M., Kawarabayashi, K.i.: Embedding and canonizing graphs of bounded genus in logspace. In: 46th Annual Symposium on Theory of Computing, pp. 383\u2013392 (2014). ISBN 978-1-4503-2710-7","DOI":"10.1145\/2591796.2591865"},{"issue":"3","key":"11_CR13","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1145\/828.1884","volume":"31","author":"ML Fredman","year":"1984","unstructured":"Fredman, M.L., Koml\u00f3s, J., Szemer\u00e9di, E.: Storing a sparse table with O(1) worst case access time. J. ACM 31(3), 538\u2013544 (1984). ISSN 00045411","journal-title":"J. ACM"},{"issue":"1","key":"11_CR14","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0022-0000(87)90002-X","volume":"34","author":"GN Frederickson","year":"1987","unstructured":"Frederickson, G.N.: Upper bounds for time-space trade-offs in sorting and selection. J. Comput. Syst. Sci. 34(1), 19\u201326 (1987). ISSN 00220000","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"11_CR15","doi-asserted-by":"publisher","first-page":"656","DOI":"10.1137\/S0895480192243516","volume":"7","author":"MX Goemans","year":"1994","unstructured":"Goemans, M.X., Williamson, D.P.: New (3\/4)-approximation algorithms for the maximum satisfiability problem. SIAM J. Discret. Math. 7(4), 656\u2013666 (1994). ISSN 0895-4801, 1095-7146","journal-title":"SIAM J. Discret. Math."},{"key":"11_CR16","unstructured":"Izumi, T., Otachi, Y.: Sublinear-space lexicographic depth-first search for bounded treewidth graphs and planar graphs. In: 47th International Colloquium on Automata, Languages, and Programming, pp. 67:1\u201367:17 (2020). ISBN 978-3-95977-138-2"},{"issue":"3","key":"11_CR17","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"DS Johnson","year":"1974","unstructured":"Johnson, D.S.: Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9(3), 256\u2013278 (1974). ISSN 00220000","journal-title":"J. Comput. Syst. Sci."},{"key":"11_CR18","doi-asserted-by":"crossref","unstructured":"Khanna, S., Motwani, R.: Towards a syntactic characterization of PTAS. In: 28th Annual Symposium on Theory of Computing, pp. 329\u2013337 (1996). ISBN 978-0-89791-785-8","DOI":"10.1145\/237814.237979"},{"key":"11_CR19","doi-asserted-by":"crossref","unstructured":"Lieberherr, K.J., Specker, E.: Complexity of Partial Satisfaction. J. ACM 28(2), 411\u2013421 (1981). ISSN 00045411","DOI":"10.1145\/322248.322260"},{"key":"11_CR20","doi-asserted-by":"crossref","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms (1995). ISBN 978-0-511-81407-5","DOI":"10.1017\/CBO9780511814075"},{"issue":"3","key":"11_CR21","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/0304-3975(80)90061-4","volume":"12","author":"JI Munro","year":"1980","unstructured":"Munro, J.I., Paterson, M.S.: Selection and sorting with limited storage. Theor. Comput. Sci. 12(3), 315\u2013323 (1980). ISSN 03043975","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"11_CR22","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/0304-3975(95)00225-1","volume":"165","author":"JI Munro","year":"1996","unstructured":"Munro, J.I., Raman, V.: Selection from read-only memory and sorting with minimum data movement. Theor. Comput. Sci. 165(2), 311\u2013323 (1996). ISSN 03043975","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"11_CR23","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1145\/62.322436","volume":"31","author":"JH Reif","year":"1984","unstructured":"Reif, J.H.: Symmetric complementation. J. ACM 31(2), 401\u2013421 (1984). ISSN 0004-5411, 1557-735X","journal-title":"J. ACM"},{"issue":"4","key":"11_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1391289.1391291","volume":"55","author":"O Reingold","year":"2008","unstructured":"Reingold, O.: Undirected connectivity in log-space. J. ACM 55(4), 1\u201324 (2008). ISSN 00045411","journal-title":"J. ACM"},{"issue":"1","key":"11_CR25","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0095-8956(84)90013-3","volume":"36","author":"N Robertson","year":"1984","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. III. Planar tree-width. J. Combin. Theory Ser. B 36(1), 49\u201364 (1984). ISSN 00958956","journal-title":"J. Combin. Theory Ser. B"},{"issue":"2","key":"11_CR26","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"WJ Savitch","year":"1970","unstructured":"Savitch, W.J.: Relationships between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci. 4(2), 177\u2013192 (1970). ISSN 00220000","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"11_CR27","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/0020-0190(91)90194-M","volume":"37","author":"M Serna","year":"1991","unstructured":"Serna, M.: Approximating linear programming is log-space complete for P. Inf. Process. Lett. 37(4), 233\u2013236 (1991). ISSN 00200190","journal-title":"Inf. Process. Lett."},{"key":"11_CR28","doi-asserted-by":"crossref","unstructured":"Trevisan, L., Xhafa, F.: The parallel complexity of positive linear programming. Parallel Process. Lett. 08(04), 527\u2013533 (1998). ISSN 0129-6264, 1793-642X","DOI":"10.1142\/S0129626498000511"},{"key":"11_CR29","doi-asserted-by":"crossref","unstructured":"Wegman, M.N., Carter, J.L.: New hash functions and their use in authentication and set equality. J. Comput. Syst. Sci. 22(3), 265\u2013279 (1981). ISSN 00220000","DOI":"10.1016\/0022-0000(81)90033-7"},{"key":"11_CR30","doi-asserted-by":"crossref","unstructured":"Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms (2011). ISBN 978-0-511-92173-5","DOI":"10.1017\/CBO9780511921735"},{"key":"11_CR31","doi-asserted-by":"crossref","unstructured":"Yannakakis, M.: On the approximation of maximum satisfiability. J. Algorithms 17(3), 475\u2013502 (1994). ISSN 01966774","DOI":"10.1006\/jagm.1994.1045"}],"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-030-89543-3_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,10]],"date-time":"2024-09-10T09:57:29Z","timestamp":1725962249000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-89543-3_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030895426","9783030895433"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-89543-3_11","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":"20 October 2021","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":"Tainan","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Taiwan","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":"24 October 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26 October 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/cocoon-conference.org\/2021\/","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":"131","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":"56","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":"43% - 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":"2.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":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}