{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T08:23:34Z","timestamp":1775031814041,"version":"3.50.1"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2023,6,1]],"date-time":"2023-06-01T00:00:00Z","timestamp":1685577600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,6,1]],"date-time":"2023-06-01T00:00:00Z","timestamp":1685577600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"crossref","award":["ANR-19-CE23-0015"],"award-info":[{"award-number":["ANR-19-CE23-0015"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math Meth Oper Res"],"published-print":{"date-parts":[[2023,6]]},"DOI":"10.1007\/s00186-023-00821-4","type":"journal-article","created":{"date-parts":[[2023,6,13]],"date-time":"2023-06-13T09:01:51Z","timestamp":1686646911000},"page":"391-436","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Testing indexability and computing Whittle and Gittins index in subcubic time"],"prefix":"10.1007","volume":"97","author":[{"given":"Nicolas","family":"Gast","sequence":"first","affiliation":[]},{"given":"Bruno","family":"Gaujal","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1939-4332","authenticated-orcid":false,"given":"Kimang","family":"Khun","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,6,13]]},"reference":[{"issue":"1\u20134","key":"821_CR1","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1007\/s11134-009-9141-x","volume":"63","author":"S Aalto","year":"2009","unstructured":"Aalto S, Ayesta U, Righter R (2009) On the Gittins index in the M\/G\/1 queue. Queueing Syst 63(1\u20134):437","journal-title":"Queueing Syst"},{"issue":"3","key":"821_CR2","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1017\/S0269964811000015","volume":"25","author":"S Aalto","year":"2011","unstructured":"Aalto S, Ayesta U, Righter R (2011) Properties of the Gittins index with application to optimal scheduling. Probab Eng Inf Sci 25(3):269\u2013288","journal-title":"Probab Eng Inf Sci"},{"key":"821_CR3","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2019.102052","volume":"136","author":"S Aalto","year":"2019","unstructured":"Aalto S, Lassila P, Taboada I (2019) Whittle index approach to opportunistic scheduling with partial channel information. Perform Eval 136:102052","journal-title":"Perform Eval"},{"key":"821_CR4","doi-asserted-by":"crossref","unstructured":"Akbarzadeh N, Mahajan A (2019) Restless bandits with controlled restarts: indexability and computation of Whittle index. In: 2019 IEEE 58th conference on decision and control (CDC), pp 7294\u20137300. IEEE","DOI":"10.1109\/CDC40024.2019.9029182"},{"key":"821_CR5","unstructured":"Akbarzadeh N, Mahajan A (2020) Conditions for indexability of restless bandits and an $$O(K^3)$$ algorithm to compute Whittle index. arXiv"},{"key":"821_CR6","unstructured":"Akbarzadeh N, Mahajan A (2021) Maintenance of a collection of machines under partial observability: indexability and computation of Whittle index. arXiv preprint arXiv:2104.05151"},{"issue":"1","key":"821_CR7","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/s001860200257","volume":"57","author":"P Ansell","year":"2003","unstructured":"Ansell P, Glazebrook KD, Nino-Mora J, O\u2019Keeffe M (2003) Whittle\u2019s index policy for a multi-class queueing system with convex holding costs. Math Methods Oper Res 57(1):21\u201339","journal-title":"Math Methods Oper Res"},{"issue":"2","key":"821_CR8","doi-asserted-by":"publisher","first-page":"314","DOI":"10.1287\/opre.1070.0505","volume":"57","author":"TW Archibald","year":"2009","unstructured":"Archibald TW, Black D, Glazebrook KD (2009) Indexability and index heuristics for a simple class of inventory routing problems. Oper Res 57(2):314\u2013326","journal-title":"Oper Res"},{"key":"821_CR9","doi-asserted-by":"publisher","DOI":"10.1016\/j.automatica.2022.110186","volume":"139","author":"KE Avrachenkov","year":"2022","unstructured":"Avrachenkov KE, Borkar VS (2022) Whittle index based Q-learning for restless bandits with average reward. Automatica 139:110186","journal-title":"Automatica"},{"issue":"17","key":"821_CR10","doi-asserted-by":"publisher","first-page":"3463","DOI":"10.1016\/j.comnet.2013.08.001","volume":"57","author":"K Avrachenkov","year":"2013","unstructured":"Avrachenkov K, Ayesta U, Doncel J, Jacko P (2013) Congestion control of TCP flows in internet routers by means of index policy. Comput Netw 57(17):3463\u20133478","journal-title":"Comput Netw"},{"key":"821_CR11","doi-asserted-by":"crossref","unstructured":"Avrachenkov K, Piunovskiy A, Zhang Y (2018) Impulsive control for G-AIMD dynamics with relaxed and hard constraints. In: 2018 IEEE conference on decision and control (CDC), pp 880\u2013887. IEEE","DOI":"10.1109\/CDC.2018.8619537"},{"issue":"1","key":"821_CR12","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/s00186-020-00731-9","volume":"93","author":"U Ayesta","year":"2021","unstructured":"Ayesta U, Gupta MK, Verloop IM (2021) On the computation of Whittle\u2019s index for Markovian restless bandits. Math Methods Oper Res 93(1):179\u2013208","journal-title":"Math Methods Oper Res"},{"key":"821_CR13","doi-asserted-by":"crossref","unstructured":"Borkar VS, Pattathil S (2017) Whittle indexability in egalitarian processor sharing systems. Ann Oper Res 1\u201321","DOI":"10.1007\/s10479-017-2622-0"},{"issue":"416\u2013435","key":"821_CR14","first-page":"455","volume":"2","author":"J Chakravorty","year":"2014","unstructured":"Chakravorty J, Mahajan A (2014) Multi-armed bandits, Gittins index, and its calculation. Methods Appl Stat Clin Trials Plan Anal Inferent Methods 2(416\u2013435):455","journal-title":"Methods Appl Stat Clin Trials Plan Anal Inferent Methods"},{"issue":"1","key":"821_CR15","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1287\/moor.11.1.180","volume":"11","author":"YR Chen","year":"1986","unstructured":"Chen YR, Katehakis MN (1986) Linear programming for finite state multi-armed bandit problems. Math Oper Res 11(1):180\u2013183","journal-title":"Math Oper Res"},{"key":"821_CR16","doi-asserted-by":"crossref","unstructured":"Fu J, Nazarathy Y, Moka S, Taylor PG (2019) Towards Q-learning the Whittle index for restless bandits. In: 2019 Australian & New Zealand control conference (ANZCC), pp 249\u2013254. IEEE","DOI":"10.1109\/ANZCC47194.2019.8945748"},{"key":"821_CR17","doi-asserted-by":"crossref","unstructured":"Gall FL, Urrutia F (2018) Improved rectangular matrix multiplication using powers of the Coppersmith\u2013Winograd tensor. In: Proceedings of the twenty-ninth annual ACM-SIAM symposium on discrete algorithms, pp 1029\u20131046. SIAM","DOI":"10.1137\/1.9781611975031.67"},{"key":"821_CR18","unstructured":"Gast N, Gaujal B, Yan C (2020) Exponential convergence rate for the asymptotic optimality of Whittle index policy. arXiv preprint arXiv:2012.09064"},{"key":"821_CR19","doi-asserted-by":"crossref","unstructured":"Gibson LJ, Jacko P, Nazarathy Y (2021) A novel implementation of Q-learning for the Whittle index. In: EAI international conference on performance evaluation methodologies and tools, pp 154\u2013170. Springer","DOI":"10.1007\/978-3-030-92511-6_10"},{"issue":"2","key":"821_CR20","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1111\/j.2517-6161.1979.tb01068.x","volume":"41","author":"JC Gittins","year":"1979","unstructured":"Gittins JC (1979) Bandit processes and dynamic allocation indices. J R Stat Soc Ser B (Methodol) 41(2):148\u2013164","journal-title":"J R Stat Soc Ser B (Methodol)"},{"issue":"7","key":"821_CR21","doi-asserted-by":"publisher","first-page":"706","DOI":"10.1002\/nav.10036","volume":"49","author":"K Glazebrook","year":"2002","unstructured":"Glazebrook K, Mitchell H (2002) An index policy for a stochastic scheduling model with improving\/deteriorating jobs. Nav Res Logist (NRL) 49(7):706\u2013721","journal-title":"Nav Res Logist (NRL)"},{"issue":"3","key":"821_CR22","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1239\/aap\/1158684996","volume":"38","author":"KD Glazebrook","year":"2006","unstructured":"Glazebrook KD, Ruiz-Hernandez D, Kirkbride C (2006) Some indexable families of restless bandit problems. Adv Appl Probab 38(3):643\u2013672","journal-title":"Adv Appl Probab"},{"issue":"4","key":"821_CR23","doi-asserted-by":"publisher","first-page":"975","DOI":"10.1287\/opre.1080.0632","volume":"57","author":"KD Glazebrook","year":"2009","unstructured":"Glazebrook KD, Kirkbride C, Ouenniche J (2009) Index policies for the admission control and routing of impatient customers to heterogeneous service stations. Oper Res 57(4):975\u2013989","journal-title":"Oper Res"},{"key":"821_CR24","doi-asserted-by":"crossref","unstructured":"Huang J et al (2018) Practical fast matrix multiplication algorithms. Ph.D. thesis","DOI":"10.1109\/IPDPS.2017.56"},{"key":"821_CR25","doi-asserted-by":"crossref","unstructured":"Huang J, Smith TM, Henry GM, Van De\u00a0Geijn RA (2016) Strassen\u2019s algorithm reloaded. In: SC\u201916: Proceedings of the international conference for high performance computing, networking, storage and analysis, pp 690\u2013701. IEEE","DOI":"10.1109\/SC.2016.58"},{"issue":"2","key":"821_CR26","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1287\/moor.12.2.262","volume":"12","author":"MN Katehakis","year":"1987","unstructured":"Katehakis MN, Veinott AF Jr (1987) The multi-armed bandit problem: decomposition and computation. Math Oper Res 12(2):262\u2013268","journal-title":"Math Oper Res"},{"issue":"2","key":"821_CR27","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/s11134-015-9445-y","volume":"81","author":"M Larra\u00f1aga","year":"2015","unstructured":"Larra\u00f1aga M, Ayesta U, Verloop IM (2015) Asymptotically optimal index policies for an abandonment queue with convex holding cost. Queueing Syst 81(2):99\u2013169","journal-title":"Queueing Syst"},{"issue":"11","key":"821_CR28","doi-asserted-by":"publisher","first-page":"5547","DOI":"10.1109\/TIT.2010.2068950","volume":"56","author":"K Liu","year":"2010","unstructured":"Liu K, Zhao Q (2010) Indexability of restless bandit problems and optimality of whittle index for dynamic multichannel access. IEEE Trans Inf Theory 56(11):5547\u20135567","journal-title":"IEEE Trans Inf Theory"},{"issue":"3","key":"821_CR29","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1017\/S0269964800143013","volume":"14","author":"C Lott","year":"2000","unstructured":"Lott C, Teneketzis D (2000) On the optimality of an index rule in multichannel allocation for single-hop mobile networks with multiple service classes. Probab Eng Inf Sci 14(3):259\u2013297","journal-title":"Probab Eng Inf Sci"},{"key":"821_CR30","unstructured":"Nakhleh K, Ganji S, Hsieh P-C, Hou I, Shakkottai S et al (2021) NeurWIN: neural Whittle index network for restless bandits via deep RL. Adv Neural Inf Process Syst 34"},{"key":"821_CR31","doi-asserted-by":"crossref","unstructured":"Ni\u00f1o-Mora J (2014) A dynamic page-refresh index policy for web crawlers. In: International conference on analytical and stochastic modeling techniques and applications, pp 46\u201360. Springer","DOI":"10.1007\/978-3-319-08219-6_4"},{"issue":"4","key":"821_CR32","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1287\/ijoc.1060.0206","volume":"19","author":"J Ni\u00f1o-Mora","year":"2007","unstructured":"Ni\u00f1o-Mora J (2007) A $$(2\/3)n^3$$ fast-pivoting algorithm for the Gittins index and optimal stopping of a Markov chain. INFORMS J Comput 19(4):596\u2013606","journal-title":"INFORMS J Comput"},{"issue":"2","key":"821_CR33","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/s11750-007-0025-0","volume":"15","author":"J Ni\u00f1o-Mora","year":"2007","unstructured":"Ni\u00f1o-Mora J (2007) Dynamic priority allocation via restless bandit marginal productivity indices. TOP 15(2):161\u2013198","journal-title":"TOP"},{"issue":"12","key":"821_CR34","doi-asserted-by":"publisher","first-page":"2226","DOI":"10.3390\/math8122226","volume":"8","author":"J Ni\u00f1o-Mora","year":"2020","unstructured":"Ni\u00f1o-Mora J (2020) A fast-pivoting algorithm for Whittle\u2019s restless bandit index. Mathematics 8(12):2226","journal-title":"Mathematics"},{"key":"821_CR35","unstructured":"Papadimitriou CH, Tsitsiklis JN (1994) The complexity of optimal queueing network control. In: Proceedings of IEEE 9th annual conference on structure in complexity Theory, pp 318\u2013322. IEEE"},{"key":"821_CR36","doi-asserted-by":"publisher","DOI":"10.1002\/9780470316887","volume-title":"Markov decision processes: discrete stochastic dynamic programming","author":"ML Puterman","year":"1994","unstructured":"Puterman ML (1994) Markov decision processes: discrete stochastic dynamic programming, 1st edn. John Wiley & Sons Inc, Hoboken","edition":"1"},{"issue":"4","key":"821_CR37","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1287\/moor.3.4.308","volume":"3","author":"PJ Schweitzer","year":"1978","unstructured":"Schweitzer PJ, Federgruen A (1978) The functional equations of undiscounted Markov renewal programming. Math Oper Res 3(4):308\u2013321","journal-title":"Math Oper Res"},{"issue":"1","key":"821_CR38","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3179419","volume":"2","author":"Z Scully","year":"2018","unstructured":"Scully Z, Harchol-Balter M, Scheller-Wolf A (2018) SOAP: one clean analysis of all age-based scheduling policies. Proc ACM Meas Anal Comput Syst 2(1):1\u201330","journal-title":"Proc ACM Meas Anal Comput Syst"},{"issue":"12","key":"821_CR39","doi-asserted-by":"publisher","first-page":"1526","DOI":"10.1016\/j.spl.2008.01.049","volume":"78","author":"IM Sonin","year":"2008","unstructured":"Sonin IM (2008) A generalized Gittins index for a Markov chain and its recursive calculation. Stat Probab Lett 78(12):1526\u20131533","journal-title":"Stat Probab Lett"},{"issue":"4","key":"821_CR40","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1007\/BF02165411","volume":"13","author":"V Strassen","year":"1969","unstructured":"Strassen V (1969) Gaussian elimination is not optimal. Numer Math 13(4):354\u2013356","journal-title":"Numer Math"},{"issue":"4","key":"821_CR41","doi-asserted-by":"publisher","first-page":"1947","DOI":"10.1214\/15-AAP1137","volume":"26","author":"IM Verloop","year":"2016","unstructured":"Verloop IM (2016) Asymptotically optimal priority policies for indexable and nonindexable restless bandits. Ann Appl Probab 26(4):1947\u20131995","journal-title":"Ann Appl Probab"},{"issue":"2","key":"821_CR42","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1214\/14-STS504","volume":"30","author":"SS Villar","year":"2015","unstructured":"Villar SS, Bowden J, Wason J (2015) Multi-armed bandit models for the optimal design of clinical trials: benefits and challenges. Stat Sci 30(2):199","journal-title":"Stat Sci"},{"key":"821_CR43","doi-asserted-by":"crossref","unstructured":"Weber RR, Weiss G (1990) On an index policy for restless bandits. J Appl Probab 637\u2013648","DOI":"10.1017\/S0021900200039176"},{"issue":"A","key":"821_CR44","doi-asserted-by":"publisher","first-page":"287","DOI":"10.2307\/3214163","volume":"25","author":"P Whittle","year":"1988","unstructured":"Whittle P (1988) Restless bandits: activity allocation in a changing world. J Appl Probab 25(A):287\u2013298","journal-title":"J Appl Probab"},{"key":"821_CR45","unstructured":"Woodbury MA (1950) Inverting modified matrices. Statistical Research Group"}],"container-title":["Mathematical Methods of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00186-023-00821-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00186-023-00821-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00186-023-00821-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,22]],"date-time":"2024-10-22T05:27:35Z","timestamp":1729574855000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00186-023-00821-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6]]},"references-count":45,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["821"],"URL":"https:\/\/doi.org\/10.1007\/s00186-023-00821-4","relation":{},"ISSN":["1432-2994","1432-5217"],"issn-type":[{"value":"1432-2994","type":"print"},{"value":"1432-5217","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6]]},"assertion":[{"value":"29 April 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 April 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 May 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 June 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}