{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:36:50Z","timestamp":1759639010445,"version":"3.41.0"},"reference-count":33,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2017,11,1]],"date-time":"2017-11-01T00:00:00Z","timestamp":1509494400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2021,11,7]],"date-time":"2021-11-07T00:00:00Z","timestamp":1636243200000},"content-version":"vor","delay-in-days":1467,"URL":"http:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"funder":[{"DOI":"10.13039\/501100001691","name":"JSPS","doi-asserted-by":"publisher","award":["15J03840","15K15938","25700002","15H02666"],"award-info":[{"award-number":["15J03840","15K15938","25700002","15H02666"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2017,11]]},"DOI":"10.1016\/j.tcs.2016.11.017","type":"journal-article","created":{"date-parts":[[2016,11,24]],"date-time":"2016-11-24T22:32:05Z","timestamp":1480026725000},"page":"63-74","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":5,"special_numbering":"C","title":["Total variation discrepancy of deterministic random walks for ergodic Markov chains"],"prefix":"10.1016","volume":"699","author":[{"given":"Takeharu","family":"Shiraga","sequence":"first","affiliation":[]},{"given":"Yukiko","family":"Yamauchi","sequence":"additional","affiliation":[]},{"given":"Shuji","family":"Kijima","sequence":"additional","affiliation":[]},{"given":"Masafumi","family":"Yamashita","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/j.tcs.2016.11.017_br0010","doi-asserted-by":"crossref","unstructured":"H. Akbari, P. Berenbrink, Parallel rotor walks on finite graphs and applications in discrete load balancing, in: Proc. SPAA 2013, pp. 186\u2013195.","DOI":"10.1145\/2486159.2486178"},{"issue":"4","key":"10.1016\/j.tcs.2016.11.017_br0020","doi-asserted-by":"crossref","first-page":"1245","DOI":"10.1007\/s00453-015-0096-5","article-title":"An FPTAS for the volume computation of 0-1 knapsack polytopes based on approximate convolution integral","volume":"76","author":"Ando","year":"2016","journal-title":"Algorithmica"},{"author":"Angel","key":"10.1016\/j.tcs.2016.11.017_br0030"},{"key":"10.1016\/j.tcs.2016.11.017_br0040","doi-asserted-by":"crossref","unstructured":"E. Bampas, L. Gasieniec, N. Hanusse, D. Ilcinkas, R. Klasing, A. Kosowski, Euler tour lock-in problem in the rotor-router model, in: Proc. DISC 2009, pp. 423\u2013435.","DOI":"10.1007\/978-3-642-04355-0_44"},{"key":"10.1016\/j.tcs.2016.11.017_br0050","doi-asserted-by":"crossref","first-page":"452","DOI":"10.1002\/rsa.20236","article-title":"Counting without sampling: asymptotics of the log-partition function for certain statistical physics models","volume":"33","author":"Bandyopadhyay","year":"2008","journal-title":"Random Structures Algorithms"},{"key":"10.1016\/j.tcs.2016.11.017_br0060","doi-asserted-by":"crossref","unstructured":"P. Berenbrink, R. Klasing, A. Kosowski, F. Mallmann-Trenn, P. Uznanski, Improved analysis of deterministic load-balancing schemes, in: Proc. PODC 2015, pp. 301\u2013310.","DOI":"10.1145\/2767386.2767413"},{"key":"10.1016\/j.tcs.2016.11.017_br0070","doi-asserted-by":"crossref","unstructured":"J. Chalopin, S. Das, P. Gawrychowski, A. Kosowski, A. Labourel, P. Uznanski, Limit behavior of the multi-agent rotor-router system, in: Proc. DISC 2015, pp. 123\u2013139.","DOI":"10.1007\/978-3-662-48653-5_9"},{"key":"10.1016\/j.tcs.2016.11.017_br0080","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1002\/rsa.20314","article-title":"Deterministic random walks on regular trees","volume":"37","author":"Cooper","year":"2010","journal-title":"Random Structures Algorithms"},{"key":"10.1016\/j.tcs.2016.11.017_br0090","doi-asserted-by":"crossref","first-page":"2072","DOI":"10.1016\/j.ejc.2007.04.018","article-title":"Deterministic random walks on the integers","volume":"28","author":"Cooper","year":"2007","journal-title":"European J. Combin."},{"key":"10.1016\/j.tcs.2016.11.017_br0100","doi-asserted-by":"crossref","first-page":"815","DOI":"10.1017\/S0963548306007565","article-title":"Simulating a random walk with constant error","volume":"15","author":"Cooper","year":"2006","journal-title":"Combin. Probab. Comput."},{"key":"10.1016\/j.tcs.2016.11.017_br0110","doi-asserted-by":"crossref","unstructured":"B. Cousins, S. Vempala, Bypassing KLS: Gaussian cooling and an O\u204e(n3) volume algorithm, in: Proc. STOC 2015, pp. 539\u2013548.","DOI":"10.1145\/2746539.2746563"},{"key":"10.1016\/j.tcs.2016.11.017_br0120","series-title":"STACS","first-page":"263","article-title":"Bounds on the cover time of parallel rotor walks","volume":"vol. 25","author":"Dereniowski","year":"2014"},{"key":"10.1016\/j.tcs.2016.11.017_br0130","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1017\/S0963548308009589","article-title":"Deterministic random walks on the two-dimensional grid","volume":"18","author":"Doerr","year":"2009","journal-title":"Combin. Probab. Comput."},{"key":"10.1016\/j.tcs.2016.11.017_br0140","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/102782.102783","article-title":"A random polynomial-time algorithm for approximating the volume of convex bodies","volume":"38","author":"Dyer","year":"1991","journal-title":"J. ACM"},{"key":"10.1016\/j.tcs.2016.11.017_br0150","doi-asserted-by":"crossref","first-page":"747","DOI":"10.1137\/100799216","article-title":"Quasirandom load balancing","volume":"41","author":"Friedrich","year":"2012","journal-title":"SIAM J. Comput."},{"author":"Gopalan","key":"10.1016\/j.tcs.2016.11.017_br0160"},{"key":"10.1016\/j.tcs.2016.11.017_br0170","series-title":"Proc. of FOCS 2011","first-page":"817","article-title":"An FPTAS for #knapsack and related counting problems","author":"Gopalan","year":"2011"},{"key":"10.1016\/j.tcs.2016.11.017_br0180","series-title":"Algorithmic Probability and Combinatorics","first-page":"105","article-title":"Rotor walks and Markov chains","author":"Holroyd","year":"2010"},{"key":"10.1016\/j.tcs.2016.11.017_br0190","doi-asserted-by":"crossref","first-page":"1087","DOI":"10.1137\/0222066","article-title":"Polynomial-time approximation algorithms for the Ising model","volume":"22","author":"Jerrum","year":"1993","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.tcs.2016.11.017_br0200","series-title":"The Markov Chain Monte Carlo Method: An Approach to Approximate Counting and Integration","article-title":"Approximation algorithms for NP-hard problems","author":"Jerrum","year":"1996"},{"key":"10.1016\/j.tcs.2016.11.017_br0210","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0304-3975(86)90174-X","article-title":"Random generation of combinatorial structures from a uniform distribution","volume":"32","author":"Jerrum","year":"1986","journal-title":"Theoret. Comput. Sci."},{"year":"2014","series-title":"Discrepancy analysis of deterministic random walks on finite irreducible digraphs","author":"Kajino","key":"10.1016\/j.tcs.2016.11.017_br0220"},{"key":"10.1016\/j.tcs.2016.11.017_br0230","doi-asserted-by":"crossref","first-page":"739","DOI":"10.1002\/rsa.20533","article-title":"Deterministic random walks on finite graphs","volume":"46","author":"Kijima","year":"2015","journal-title":"Random Structures Algorithms"},{"year":"2008","series-title":"Markov Chain and Mixing Times","author":"Levine","key":"10.1016\/j.tcs.2016.11.017_br0240"},{"key":"10.1016\/j.tcs.2016.11.017_br0250","doi-asserted-by":"crossref","unstructured":"L. Lovasz, S. Vempala, Fast algorithms for logconcave functions: sampling, rounding, integration and optimization, in: Proc. FOCS 2006, pp. 57\u201368.","DOI":"10.1109\/FOCS.2006.28"},{"key":"10.1016\/j.tcs.2016.11.017_br0260","doi-asserted-by":"crossref","unstructured":"Y. Rabani, A. Sinclair, R. Wanka, Local divergence of Markov chains and analysis of iterative load balancing schemes, in: Proc. FOCS 1998, pp. 694\u2013705.","DOI":"10.1109\/SFCS.1998.743520"},{"author":"Shiraga","key":"10.1016\/j.tcs.2016.11.017_br0270"},{"key":"10.1016\/j.tcs.2016.11.017_br0280","series-title":"COCOON 2014","first-page":"25","article-title":"L\u221e-discrepancy analysis of polynomial-time deterministic samplers emulating rapidly mixing chains","volume":"vol. 8591","author":"Shiraga","year":"2014"},{"key":"10.1016\/j.tcs.2016.11.017_br0290","doi-asserted-by":"crossref","unstructured":"T. Shiraga, Y. Yamauchi, S. Kijima, M. Yamashita, Total variation discrepancy of deterministic random walks for ergodic Markov chains, in: Proc. ANALCO 2016, pp. 138\u2013148.","DOI":"10.1016\/j.tcs.2016.11.017"},{"key":"10.1016\/j.tcs.2016.11.017_br0300","doi-asserted-by":"crossref","first-page":"356","DOI":"10.1137\/11083976X","article-title":"A deterministic polynomial-time approximation scheme for counting knapsack solutions","volume":"41","author":"Stefankovic","year":"2012","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.tcs.2016.11.017_br0310","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1016\/0012-365X(80)90269-1","article-title":"The chairman assignment problem","volume":"32","author":"Tijdeman","year":"1980","journal-title":"Discrete Math."},{"key":"10.1016\/j.tcs.2016.11.017_br0320","doi-asserted-by":"crossref","unstructured":"D. Weitz, Counting independent sets up to the tree threshold, in: Proc. STOC 2006, pp. 140\u2013149.","DOI":"10.1145\/1132516.1132538"},{"key":"10.1016\/j.tcs.2016.11.017_br0330","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1007\/s00453-003-1030-9","article-title":"A distributed ant algorithm for efficiently patrolling a network","volume":"37","author":"Yanovski","year":"2003","journal-title":"Algorithmica"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397516306120?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397516306120?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,6,12]],"date-time":"2025-06-12T21:19:27Z","timestamp":1749763167000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397516306120"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,11]]},"references-count":33,"alternative-id":["S0304397516306120"],"URL":"https:\/\/doi.org\/10.1016\/j.tcs.2016.11.017","relation":{},"ISSN":["0304-3975"],"issn-type":[{"type":"print","value":"0304-3975"}],"subject":[],"published":{"date-parts":[[2017,11]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Total variation discrepancy of deterministic random walks for ergodic Markov chains","name":"articletitle","label":"Article Title"},{"value":"Theoretical Computer Science","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.tcs.2016.11.017","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2017 Elsevier B.V.","name":"copyright","label":"Copyright"}]}}