{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,18]],"date-time":"2026-04-18T13:38:37Z","timestamp":1776519517653,"version":"3.51.2"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2026,4,18]],"date-time":"2026-04-18T00:00:00Z","timestamp":1776470400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0"},{"start":{"date-parts":[[2026,4,18]],"date-time":"2026-04-18T00:00:00Z","timestamp":1776470400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0"}],"funder":[{"DOI":"10.13039\/501100001352","name":"National University of Singapore","doi-asserted-by":"crossref","award":["A-0000178-02-00"],"award-info":[{"award-number":["A-0000178-02-00"]}],"id":[{"id":"10.13039\/501100001352","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2026,5]]},"DOI":"10.1007\/s10878-026-01417-4","type":"journal-article","created":{"date-parts":[[2026,4,18]],"date-time":"2026-04-18T12:44:32Z","timestamp":1776516272000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Information-theoretic coordinate subset and partition selection of multivariate Markov chains via submodular optimization"],"prefix":"10.1007","volume":"51","author":[{"given":"Zheyuan","family":"Lai","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0309-3217","authenticated-orcid":false,"given":"Michael C. H.","family":"Choi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,4,18]]},"reference":[{"key":"1417_CR1","doi-asserted-by":"crossref","unstructured":"Bovier A, Den Hollander F (2016) Metastability: a potential-theoretic approach, volume 351. Springer","DOI":"10.1007\/978-3-319-24777-9"},{"key":"1417_CR2","unstructured":"Choi MCH, Wang Y, Wolfer G (2024) Geometry and factorization of multivariate Markov chains with applications to MCMC acceleration. arXiv:2404.12589"},{"issue":"12","key":"1417_CR3","doi-asserted-by":"publisher","first-page":"2793","DOI":"10.1109\/TAC.2011.2141350","volume":"56","author":"K Deng","year":"2011","unstructured":"Deng K, Mehta PG, Meyn SP (2011) Optimal Kullback-Leibler aggregation via spectral theory of Markov chains. IEEE Trans Automat Control 56(12):2793\u20132808","journal-title":"IEEE Trans Automat Control"},{"key":"1417_CR4","unstructured":"Ene A, Nguyen H (2022) Streaming algorithm for monotone $$k$$-submodular maximization with cardinality constraints. In International Conference on Machine Learning, pages 5944\u20135967. PMLR"},{"key":"1417_CR5","doi-asserted-by":"crossref","unstructured":"Faulkner MF, Livingstone S (2024) Sampling algorithms in statistical physics: a guide for statistics and machine learning. Stat Sci 39(1):137\u2013164","DOI":"10.1214\/23-STS893"},{"key":"1417_CR6","doi-asserted-by":"crossref","unstructured":"Feige U, Mirrokni VS, Vondr\u00e1k J (2011) Maximizing non-monotone submodular functions. SIAM J Comput 40(4):1133\u20131153","DOI":"10.1137\/090779346"},{"issue":"1","key":"1417_CR7","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/S0019-9958(78)91063-X","volume":"39","author":"S Fujishige","year":"1978","unstructured":"Fujishige S (1978) Polymatroidal dependence structure of a set of random variables. Inform and Control 39(1):55\u201372","journal-title":"Inform and Control"},{"issue":"4","key":"1417_CR8","doi-asserted-by":"publisher","first-page":"1114","DOI":"10.1239\/jap\/1421763331","volume":"51","author":"BC Geiger","year":"2014","unstructured":"Geiger BC, Temmel C (2014) Lumpings of Markov chains, entropy rate preservation, and higher-order lumpability. J Appl Probab 51(4):1114\u20131132","journal-title":"J Appl Probab"},{"key":"1417_CR9","unstructured":"Harshaw C, Feldman M, Ward J, Karbasi A (2019) Submodular maximization beyond non-negativity: Guarantees, fast algorithms, and applications. In Proceedings of the 36th International Conference on Machine Learning, volume\u00a097 of Proceedings of Machine Learning Research, pages 2634\u20132643. PMLR, 09\u201315"},{"issue":"252","key":"1417_CR10","first-page":"1","volume":"22","author":"J Jagalur-Mohan","year":"2021","unstructured":"Jagalur-Mohan J, Marzouk Y (2021) Batch greedy maximization of non-submodular functions: Guarantees and applications to experimental design. J Mach Learn Res 22(252):1\u201362","journal-title":"J Mach Learn Res"},{"issue":"2","key":"1417_CR11","doi-asserted-by":"publisher","first-page":"737","DOI":"10.1214\/08-AAP562","volume":"19","author":"K Khare","year":"2009","unstructured":"Khare K, Zhou H (2009) Rates of convergence of some multivariate Markov chains with polynomial eigenfunctions. Ann Appl Probab 19(2):737\u2013777","journal-title":"Ann Appl Probab"},{"key":"1417_CR12","doi-asserted-by":"crossref","unstructured":"Korte BH, Vygen J, Korte B, Vygen J (2011) Combinatorial optimization, volume\u00a01. Springer","DOI":"10.1007\/978-3-642-24488-9_1"},{"issue":"4","key":"1417_CR13","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1287\/moor.1100.0463","volume":"35","author":"J Lee","year":"2010","unstructured":"Lee J, Sviridenko M, Vondr\u00e1k J (2010) Submodular maximization over multiple matroids via generalized exchange properties. Math Oper Res 35(4):795\u2013806","journal-title":"Math Oper Res"},{"key":"1417_CR14","doi-asserted-by":"crossref","unstructured":"Levin DA, Peres Y (2017) Markov chains and mixing times, volume 107. American Mathematical Soc.,","DOI":"10.1090\/mbk\/107"},{"issue":"3","key":"1417_CR15","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"GL Nemhauser","year":"1978","unstructured":"Nemhauser GL, Wolsey LA, Fisher ML (1978) An analysis of approximations for maximizing submodular set functions. I Math Programming 14(3):265\u2013294","journal-title":"I Math Programming"},{"key":"1417_CR16","unstructured":"Ohsaka N, Yoshida Y (2015) Monotone k-submodular function maximization with size constraints. In C.\u00a0Cortes, N.\u00a0Lawrence, D.\u00a0Lee, M.\u00a0Sugiyama, and R.\u00a0Garnett, editors, Advances in Neural Information Processing Systems, volume\u00a028. Curran Associates, Inc.,"},{"key":"1417_CR17","doi-asserted-by":"crossref","unstructured":"Polyanskiy Y, Wu Y (2025) Information Theory: From Coding to Learning. Cambridge University Press","DOI":"10.1017\/9781108966351"},{"issue":"4","key":"1417_CR18","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1145\/2850419","volume":"12","author":"J Ward","year":"2016","unstructured":"Ward J, \u017divn\u00fd S (2016) Maximizing $$k$$-submodular functions and beyond. ACM Trans Algorithms 12(4):47 (26)","journal-title":"ACM Trans Algorithms"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-026-01417-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-026-01417-4","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-026-01417-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,18]],"date-time":"2026-04-18T12:44:35Z","timestamp":1776516275000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-026-01417-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,18]]},"references-count":18,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2026,5]]}},"alternative-id":["1417"],"URL":"https:\/\/doi.org\/10.1007\/s10878-026-01417-4","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,18]]},"assertion":[{"value":"30 March 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 March 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 April 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of Interest"}}],"article-number":"40"}}