{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:39Z","timestamp":1740109299004,"version":"3.37.3"},"reference-count":54,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2021,4,5]],"date-time":"2021-04-05T00:00:00Z","timestamp":1617580800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,4,5]],"date-time":"2021-04-05T00:00:00Z","timestamp":1617580800000},"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":["Algorithmica"],"published-print":{"date-parts":[[2021,7]]},"DOI":"10.1007\/s00453-021-00826-7","type":"journal-article","created":{"date-parts":[[2021,4,6]],"date-time":"2021-04-06T00:02:39Z","timestamp":1617667359000},"page":"2303-2331","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Approximation in (Poly-) Logarithmic Space"],"prefix":"10.1007","volume":"83","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4721-7971","authenticated-orcid":false,"given":"Arindam","family":"Biswas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8123-0980","authenticated-orcid":false,"given":"Venkatesh","family":"Raman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7847-6402","authenticated-orcid":false,"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,4,5]]},"reference":[{"issue":"1","key":"826_CR1","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). https:\/\/doi.org\/10.1016\/j.ic.2003.09.002","journal-title":"Inf. Comput."},{"issue":"2","key":"826_CR2","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/1150334.1150336","volume":"2","author":"N Alon","year":"2006","unstructured":"Alon, N., Moshkovitz, D., Safra, S.: Algorithmic construction of sets for k-restrictions. ACM Trans. Algorithms 2(2), 153\u2013177 (2006). https:\/\/doi.org\/10.1145\/1150334.1150336","journal-title":"ACM Trans. Algorithms"},{"key":"826_CR3","doi-asserted-by":"publisher","DOI":"10.1002\/9780470277331","volume-title":"The Probabilistic Method","author":"N Alon","year":"2008","unstructured":"Alon, N., Spencer, J.H.: The Probabilistic Method, 3rd edn. Wiley, London (2008)","edition":"3"},{"key":"826_CR4","doi-asserted-by":"publisher","unstructured":"Asano, T., Izumi, T., Kiyomi, M., Konagaya, M., Ono, H., Otachi, Y., Schweitzer, P., Tarui, J., Uehara, R.: Depth-First Search Using O(n) Bits. In: 25th International Symposium on Algorithms and Computation, vol. 8889, pp. 553\u2013564. Springer. https:\/\/doi.org\/10.1007\/978-3-319-13075-0_44","DOI":"10.1007\/978-3-319-13075-0_44"},{"issue":"1","key":"826_CR5","doi-asserted-by":"publisher","first-page":"27","DOI":"10.4086\/toc.2011.v007a003","volume":"7","author":"P Austrin","year":"2011","unstructured":"Austrin, P., Khot, S., Safra, M.: Inapproximability of vertex cover and independent set in bounded degree graphs. Theory Comput 7(1), 27\u201343 (2011). https:\/\/doi.org\/10.4086\/toc.2011.v007a003","journal-title":"Theory Comput"},{"key":"826_CR6","doi-asserted-by":"publisher","unstructured":"Banerjee, N., Chakraborty, S., Raman, V., Roy, S., Saurabh, S.: Time-Space Tradeoffs for Dynamic Programming Algorithms in Trees and Bounded Treewidth Graphs. In: Computing and Combinatorics, vol. 9198, pp. 349\u2013360. Springer. https:\/\/doi.org\/10.1007\/978-3-319-21398-9_28","DOI":"10.1007\/978-3-319-21398-9_28"},{"issue":"2","key":"826_CR7","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1137\/0220017","volume":"20","author":"P Beame","year":"1991","unstructured":"Beame, P.: A general sequential time\u2013space tradeoff for finding unique elements. SIAM J. Comput. 20(2), 270\u2013277 (1991). https:\/\/doi.org\/10.1137\/0220017","journal-title":"SIAM J. Comput."},{"issue":"3","key":"826_CR8","doi-asserted-by":"publisher","first-page":"454","DOI":"10.1016\/S0022-0000(05)80068-6","volume":"49","author":"B Berger","year":"1994","unstructured":"Berger, B., Rompel, J., Shor, P.W.: Efficient NC algorithms for set cover with applications to learning and geometry. J. Comput. Syst. Sci. 49(3), 454\u2013477 (1994). https:\/\/doi.org\/10.1016\/S0022-0000(05)80068-6","journal-title":"J. Comput. Syst. Sci."},{"key":"826_CR9","doi-asserted-by":"publisher","unstructured":"Biswas, A., Raman, V., Saurabh, S.: Approximation in (Poly-) Logarithmic Space. In: 45th International Symposium on Mathematical Foundations of Computer Science, vol. 170, p.\u00a015. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik. https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2020.16","DOI":"10.4230\/LIPIcs.MFCS.2020.16"},{"issue":"2","key":"826_CR10","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1137\/0211022","volume":"11","author":"A Borodin","year":"1982","unstructured":"Borodin, A., Cook, S.A.: A time\u2013space tradeoff for sorting on a general sequential model of computation. SIAM J. Comput. 11(2), 287\u2013297 (1982). https:\/\/doi.org\/10.1137\/0211022","journal-title":"SIAM J. Comput."},{"issue":"3","key":"826_CR11","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1016\/0022-0000(81)90037-4","volume":"22","author":"A Borodin","year":"1981","unstructured":"Borodin, A., Fischer, M.J., Kirkpatrick, D.G., Lynch, N.A., Tompa, M.: A time\u2013space tradeoff for sorting on non-oblivious machines. J. Comput. Syst. Sci. 22(3), 351\u2013364 (1981). https:\/\/doi.org\/10.1016\/0022-0000(81)90037-4","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"826_CR12","doi-asserted-by":"publisher","first-page":"560","DOI":"10.1137\/0222038","volume":"22","author":"JF Buss","year":"1993","unstructured":"Buss, J.F., Goldsmith, J.: Nondeterminism within P. SIAM J. Comput. 22(3), 560\u2013572 (1993). https:\/\/doi.org\/10.1137\/0222038","journal-title":"SIAM J. Comput."},{"issue":"1","key":"826_CR13","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/S0168-0072(95)00020-8","volume":"84","author":"L Cai","year":"1997","unstructured":"Cai, L., Chen, J., Downey, R.G., Fellows, M.R.: Advice classes of parameterized tractability. Ann. Pure Appl. Logic 84(1), 119\u2013138 (1997). https:\/\/doi.org\/10.1016\/S0168-0072(95)00020-8","journal-title":"Ann. Pure Appl. Logic"},{"issue":"2","key":"826_CR14","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0022-0000(79)90044-8","volume":"18","author":"JL Carter","year":"1979","unstructured":"Carter, J.L., Wegman, M.N.: Universal classes of hash functions. J. Comput. Syst. Sci. 18(2), 143\u2013154 (1979). https:\/\/doi.org\/10.1016\/j.ic.2003.09.0020","journal-title":"J. Comput. Syst. Sci."},{"key":"826_CR15","doi-asserted-by":"publisher","unstructured":"Chakraborty, S., Mukherjee, A., Raman, V., Satti, S.R.: A Framework for In-place Graph Algorithms. In: 26th Annual European Symposium on Algorithms, vol. 112, pp. 13:1\u201313:16. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik. https:\/\/doi.org\/10.4230\/lipics.esa.2018.13","DOI":"10.4230\/lipics.esa.2018.13"},{"key":"826_CR16","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/j.jcss.2017.06.006","volume":"90","author":"S Chakraborty","year":"2017","unstructured":"Chakraborty, S., Raman, V., Satti, S.R.: Biconnectivity, st-numbering and other applications of DFS using O(n) bits. J. Comput. Syst. Sci. 90, 63\u201379 (2017). https:\/\/doi.org\/10.1016\/j.ic.2003.09.0021","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"826_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2873054","volume":"63","author":"SO Chan","year":"2016","unstructured":"Chan, S.O.: Approximation resistance from pairwise-independent subgroups. J. ACM 63(3), 1\u201332 (2016). https:\/\/doi.org\/10.1016\/j.ic.2003.09.0022","journal-title":"J. ACM"},{"key":"826_CR18","doi-asserted-by":"publisher","unstructured":"Chan, T.M., Munro, J.I., Raman, V.: Selection and Sorting in the \u201cRestore\u201d Model. ACM Transactions on Algorithms 14(2), 1\u201318 (2018). https:\/\/doi.org\/10.1145\/3168005","DOI":"10.1145\/3168005"},{"issue":"3","key":"826_CR19","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1016\/0196-6774(87)90018-6","volume":"8","author":"SA Cook","year":"1987","unstructured":"Cook, S.A., McKenzie, P.: Problems complete for deterministic logarithmic space. J. Algorithms 8(3), 385\u2013394 (1987). https:\/\/doi.org\/10.1016\/j.ic.2003.09.0023","journal-title":"J. Algorithms"},{"key":"826_CR20","doi-asserted-by":"publisher","unstructured":"Courcelle, b: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85(1), 12\u201375 (1990). https:\/\/doi.org\/10.1016\/0890-5401(90)90043-H","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"826_CR21","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F..V., Kowalik, L..u, Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized algorithms. Springer, Berlin (2015)","DOI":"10.1007\/978-3-319-21275-3"},{"key":"826_CR22","doi-asserted-by":"publisher","unstructured":"Dinur, I., Steurer, D.: Analytical approach to parallel repetition. In: Proceedings of the 46th Annual Symposium on Theory of Computing, pp. 624\u2013633. ACM Press. https:\/\/doi.org\/10.1145\/2591796.2591884","DOI":"10.1145\/2591796.2591884"},{"key":"826_CR23","doi-asserted-by":"publisher","unstructured":"Elberfeld, M., Jakoby, A., Tantau, T.: Logspace versions of the theorems of Bodlaender and Courcelle. In: Proceedings of the 51st Annual Symposium on Foundations of Computer Science, pp. 143\u2013152. IEEE Computer Society Press. https:\/\/doi.org\/10.1109\/FOCS.2010.21","DOI":"10.1109\/FOCS.2010.21"},{"key":"826_CR24","doi-asserted-by":"publisher","unstructured":"Elberfeld, M., Kawarabayashi, K.i.: Embedding and canonizing graphs of bounded genus in logspace. In: Proceedings of the 46th Annual Symposium on Theory of Computing, pp. 383\u2013392. ACM Press. https:\/\/doi.org\/10.1145\/2591796.2591865","DOI":"10.1145\/2591796.2591865"},{"key":"826_CR25","doi-asserted-by":"publisher","unstructured":"Elmasry, A., Hagerup, T., Kammer, F.: Space-efficient Basic Graph Algorithms. In: Proceedings of the 32nd Annual Symposium on Theoretical Aspects of Computer Science, vol.\u00a030, pp. 288\u2013301. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik. https:\/\/doi.org\/10.4230\/lipics.stacs.2015.288","DOI":"10.4230\/lipics.stacs.2015.288"},{"key":"826_CR26","doi-asserted-by":"publisher","unstructured":"Fafianie, S., Kratsch, S.: A Shortcut to (Sun)Flowers: Kernels in Logarithmic Space or Linear Time. In: Mathematical Foundations of Computer Science, vol. 9235, pp. 299\u2013310. Springer. https:\/\/doi.org\/10.1007\/978-3-662-48054-0_25","DOI":"10.1007\/978-3-662-48054-0_25"},{"issue":"1","key":"826_CR27","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\u2013space trade-offs in sorting and selection. J. Comput. Syst. Sci. 34(1), 19\u201326 (1987). https:\/\/doi.org\/10.1016\/j.ic.2003.09.0024","journal-title":"J. Comput. Syst. Sci."},{"key":"826_CR28","doi-asserted-by":"publisher","unstructured":"H\u00e5\u00a0stad, J.: Clique is hard to approximate within $${\\hat{n}}(1 - {\\epsilon })$$. Acta Math. 182(1), 105\u2013142 (1999). https:\/\/doi.org\/10.1007\/BF02392825","DOI":"10.1007\/BF02392825"},{"issue":"4","key":"826_CR29","doi-asserted-by":"publisher","first-page":"1033","DOI":"10.1007\/s00453-019-00629-x","volume":"82","author":"T Hagerup","year":"2020","unstructured":"Hagerup, T.: Space-efficient DFS and applications to connectivity problems: simpler, leaner, faster. Algorithmica 82(4), 1033\u20131056 (2020). https:\/\/doi.org\/10.1016\/j.ic.2003.09.0025","journal-title":"Algorithmica"},{"issue":"3","key":"826_CR30","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3326171","volume":"15","author":"DG Harris","year":"2019","unstructured":"Harris, D.G.: Derandomized concentration bounds for polynomials, and hypergraph maximal independent set. ACM Trans. Algorithms 15(3), 1\u201329 (2019). https:\/\/doi.org\/10.1016\/j.ic.2003.09.0026","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"826_CR31","doi-asserted-by":"publisher","first-page":"1294","DOI":"10.1137\/15M103618X","volume":"31","author":"M Jones","year":"2017","unstructured":"Jones, M., Lokshtanov, D., Ramanujan, M.S., Saurabh, S., Such\u00fd, O.: Parameterized complexity of directed Steiner tree on sparse graphs. SIAM J. Discrete Math. 31(2), 1294\u20131327 (2017). https:\/\/doi.org\/10.1016\/j.ic.2003.09.0027","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"826_CR32","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","volume":"74","author":"S Khot","year":"2008","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within $$2-\\epsilon$$. J. Comput. Syst. Sci. 74(3), 335\u2013349 (2008). https:\/\/doi.org\/10.1016\/j.ic.2003.09.0028","journal-title":"J. Comput. Syst. Sci."},{"key":"826_CR33","doi-asserted-by":"publisher","unstructured":"Li, J., O\u2019Donnell, R.: Bounding laconic proof systems by solving CSPs in parallel. In: Proceedings of the 29th Annual Symposium on Parallelism in Algorithms and Architectures, pp. 95\u2013100. ACM Press. https:\/\/doi.org\/10.1145\/3087556.3087557","DOI":"10.1145\/3087556.3087557"},{"issue":"4","key":"826_CR34","doi-asserted-by":"publisher","first-page":"1036","DOI":"10.1137\/0215074","volume":"15","author":"M Luby","year":"1986","unstructured":"Luby, M.: A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput. 15(4), 1036\u20131053 (1986). https:\/\/doi.org\/10.1016\/j.ic.2003.09.0029","journal-title":"SIAM J. Comput."},{"key":"826_CR35","doi-asserted-by":"publisher","unstructured":"Luby, M., Nisan, N.: A parallel approximation algorithm for positive linear programming. In: Proceedings of the 25th Annual Symposium on Theory of Computing, pp. 448\u2013457. ACM Press. https:\/\/doi.org\/10.1145\/167088.167211","DOI":"10.1145\/167088.167211"},{"issue":"1","key":"826_CR36","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1145\/2627692.2627694","volume":"43","author":"A McGregor","year":"2014","unstructured":"McGregor, A.: Graph stream algorithms: a survey. ACM SIGMOD Rec. 43(1), 9\u201320 (2014). https:\/\/doi.org\/10.1145\/1150334.11503360","journal-title":"ACM SIGMOD Rec."},{"issue":"3","key":"826_CR37","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). https:\/\/doi.org\/10.1145\/1150334.11503361","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"826_CR38","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). https:\/\/doi.org\/10.1145\/1150334.11503362","journal-title":"Theor. Comput. Sci."},{"key":"826_CR39","doi-asserted-by":"publisher","unstructured":"Pagh, R., Pagter, J.: Optimal time\u2013space trade-offs for non-comparison-based sorting. In: Proceedings of the 13th Annual Symposium on Discrete Algorithms, pp. 9\u201318. SIAM. https:\/\/doi.org\/10.5555\/545381.545383","DOI":"10.5555\/545381.545383"},{"key":"826_CR40","doi-asserted-by":"publisher","unstructured":"Pagter, J., Rauhe, T.: Optimal time-space trade-offs for sorting. In: Proceedings of the 39th Annual Symposium on Foundations of Computer Science, pp. 264\u2013268. IEEE Computer Society Press. https:\/\/doi.org\/10.1109\/SFCS.1998.743455","DOI":"10.1109\/SFCS.1998.743455"},{"key":"826_CR41","volume-title":"Computational Complexity","author":"CH Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, New York (1994)"},{"issue":"1","key":"826_CR42","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2390176.2390187","volume":"9","author":"G Philip","year":"2012","unstructured":"Philip, G., Raman, V., Sikdar, S.: Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond. ACM Trans. Algorithms 9(1), 1\u201323 (2012). https:\/\/doi.org\/10.1145\/1150334.11503363","journal-title":"ACM Trans. Algorithms"},{"issue":"12","key":"826_CR43","doi-asserted-by":"publisher","first-page":"642","DOI":"10.1016\/j.ipl.2009.02.017","volume":"109","author":"V Polishchuk","year":"2009","unstructured":"Polishchuk, V., Suomela, J.: A simple local 3-approximation algorithm for vertex cover. Inf. Process. Lett. 109(12), 642\u2013645 (2009). https:\/\/doi.org\/10.1145\/1150334.11503364","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"826_CR44","doi-asserted-by":"publisher","first-page":"162","DOI":"10.5555\/762350.762354","volume":"6","author":"V Raman","year":"1999","unstructured":"Raman, V., Ramnath, S.: Improved upper bounds for time\u2013space trade-offs for selection. Nordic J. Comput. 6(2), 162\u2013180 (1999). https:\/\/doi.org\/10.1145\/1150334.11503365","journal-title":"Nordic J. Comput."},{"issue":"2","key":"826_CR45","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/s00453-007-9148-9","volume":"52","author":"V Raman","year":"2008","unstructured":"Raman, V., Saurabh, S.: Short cycles make W-hard problems hard: FPT algorithms for W-hard problems in graphs with no short cycles. Algorithmica 52(2), 203\u2013225 (2008). https:\/\/doi.org\/10.1145\/1150334.11503366","journal-title":"Algorithmica"},{"issue":"2","key":"826_CR46","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). https:\/\/doi.org\/10.1145\/1150334.11503367","journal-title":"J. ACM"},{"issue":"4","key":"826_CR47","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). https:\/\/doi.org\/10.1145\/1150334.11503368","journal-title":"J. ACM"},{"issue":"2","key":"826_CR48","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). https:\/\/doi.org\/10.1145\/1150334.11503369","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"826_CR49","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). https:\/\/doi.org\/10.4086\/toc.2011.v007a0030","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"826_CR50","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/s00224-007-2011-1","volume":"41","author":"T Tantau","year":"2007","unstructured":"Tantau, T.: Log space optimization problems and their approximability properties. Theory Comput. Syst. 41(2), 327\u2013350 (2007). https:\/\/doi.org\/10.4086\/toc.2011.v007a0031","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"826_CR51","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1007\/PL00009209","volume":"21","author":"L Trevisan","year":"1998","unstructured":"Trevisan, L.: Parallel approximation algorithms by positive linear programming. Algorithmica 21(1), 72\u201388 (1998). https:\/\/doi.org\/10.4086\/toc.2011.v007a0032","journal-title":"Algorithmica"},{"issue":"04","key":"826_CR52","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1142\/S0129626498000511","volume":"08","author":"L Trevisan","year":"1998","unstructured":"Trevisan, L., Xhafa, F.: The parallel complexity of positive linear programming. Parallel Process. Lett. 08(04), 527\u2013533 (1998). https:\/\/doi.org\/10.4086\/toc.2011.v007a0033","journal-title":"Parallel Process. Lett."},{"key":"826_CR53","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03927-4","volume-title":"Introduction to Circuit Complexity","author":"H Vollmer","year":"1999","unstructured":"Vollmer, H.: Introduction to Circuit Complexity. Springer, Berlin (1999)"},{"key":"826_CR54","doi-asserted-by":"publisher","unstructured":"Yamakami, T.: Uniform-circuit and logarithmic-space approximations of refined combinatorial optimization problems. In: Combinatorial Optimization and Applications, vol. 8287, pp. 318\u2013329. Springer. https:\/\/doi.org\/10.1007\/978-3-319-03780-6_28","DOI":"10.1007\/978-3-319-03780-6_28"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00826-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00826-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00826-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,22]],"date-time":"2021-06-22T09:08:40Z","timestamp":1624352920000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00826-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,5]]},"references-count":54,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["826"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00826-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2021,4,5]]},"assertion":[{"value":"29 January 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 March 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 April 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}