{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,7,29]],"date-time":"2022-07-29T18:51:37Z","timestamp":1659120697593},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2017,11,1]],"date-time":"2017-11-01T00:00:00Z","timestamp":1509494400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund (AT)","doi-asserted-by":"publisher","award":["FWF Grant P23499-N23","NFN RiSE S11407"],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council (BE)","doi-asserted-by":"publisher","award":["279307: Graph Games"],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Microsoft Faculty Fellows Award"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Real-Time Syst"],"published-print":{"date-parts":[[2018,1]]},"DOI":"10.1007\/s11241-017-9293-4","type":"journal-article","created":{"date-parts":[[2017,11,1]],"date-time":"2017-11-01T11:16:09Z","timestamp":1509534969000},"page":"166-207","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Automated competitive analysis of real-time scheduling with graph games"],"prefix":"10.1007","volume":"54","author":[{"given":"Krishnendu","family":"Chatterjee","sequence":"first","affiliation":[]},{"given":"Andreas","family":"Pavlogiannis","sequence":"additional","affiliation":[]},{"given":"Alexander","family":"K\u00f6\u00dfler","sequence":"additional","affiliation":[]},{"given":"Ulrich","family":"Schmid","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,11,1]]},"reference":[{"key":"9293_CR1","doi-asserted-by":"publisher","unstructured":"Abeni L, Buttazzo G (1998) Integrating multimedia applications in hard real-time systems. In: Proceedings of the 19th IEEE real-time systems symposium, RTSS \u201998, pp 4\u201313. https:\/\/doi.org\/10.1109\/REAL.1998.739726","DOI":"10.1109\/REAL.1998.739726"},{"issue":"1\u20132","key":"9293_CR2","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1023\/A:1015346419267","volume":"23","author":"K Altisen","year":"2002","unstructured":"Altisen K, G\u00f6\u00dfler G, Sifakis J (2002) Scheduler modeling based on the controller synthesis paradigm. Real-Time Syst. 23(1\u20132):55\u201384","journal-title":"Real-Time Syst."},{"issue":"5","key":"9293_CR3","doi-asserted-by":"publisher","first-page":"584","DOI":"10.1109\/TC.2004.1275298","volume":"53","author":"H Aydin","year":"2004","unstructured":"Aydin H, Melhem R, Moss\u00e9 D, Mej\u00eda-Alvarez P (2004) Power-aware scheduling for periodic real-time tasks. IEEE Trans Comput 53(5):584\u2013600. https:\/\/doi.org\/10.1109\/TC.2004.1275298","journal-title":"IEEE Trans Comput"},{"key":"9293_CR4","doi-asserted-by":"publisher","first-page":"1034","DOI":"10.1109\/12.620484","volume":"46","author":"SK Baruah","year":"1997","unstructured":"Baruah SK, Haritsa JR (1997) Scheduling for overload in real-time systems. IEEE Trans Comput 46:1034\u20131039. https:\/\/doi.org\/10.1109\/12.620484","journal-title":"IEEE Trans Comput"},{"issue":"9","key":"9293_CR5","doi-asserted-by":"crossref","first-page":"1027","DOI":"10.1109\/12.713322","volume":"47","author":"SK Baruah","year":"1998","unstructured":"Baruah SK, Hickey ME (1998) Competitive on-line scheduling of imprecise computations. IEEE Trans Comput 47(9):1027\u20131032","journal-title":"IEEE Trans Comput"},{"key":"9293_CR6","doi-asserted-by":"publisher","unstructured":"Baruah S, Koren G, Mishra B, Raghunathan A, Rosier L, Shasha D (1991) On-line scheduling in the presence of overload. In: Proceedings of the 32nd annual symposium on foundations of computer science, FOCS \u201991, pp 100\u2013110. https:\/\/doi.org\/10.1109\/SFCS.1991.185354","DOI":"10.1109\/SFCS.1991.185354"},{"issue":"2","key":"9293_CR7","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/BF00365406","volume":"4","author":"S Baruah","year":"1992","unstructured":"Baruah S, Koren G, Mao D, Mishra B, Raghunathan A, Rosier L, Shasha D, Wang F (1992) On the competitiveness of on-line real-time task scheduling. Real-Time Syst 4(2):125\u2013144","journal-title":"Real-Time Syst"},{"key":"9293_CR8","unstructured":"Berkelaar M, Eikland K, Notebaert P (2004) lpsolve: open source (mixed-integer) linear programming system. Version 5.0.0.0"},{"key":"9293_CR9","doi-asserted-by":"publisher","unstructured":"Bonifaci V, Marchetti-Spaccamela A (2012) Feasibility analysis of sporadic real-time multiprocessor task systems. Algorithmica 63(4):763\u2013780. https:\/\/doi.org\/10.1007\/s00453-011-9505-6","DOI":"10.1007\/s00453-011-9505-6"},{"key":"9293_CR10","volume-title":"Online computation and competitive analysis","author":"A Borodin","year":"1998","unstructured":"Borodin A, El-Yaniv R (1998) Online computation and competitive analysis. Cambridge University Press, Cambridge"},{"issue":"2","key":"9293_CR11","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/s10703-010-0105-x","volume":"38","author":"L Brim","year":"2011","unstructured":"Brim L, Chaloupka J, Doyen L, Gentilini R, Raskin JF (2011) Faster algorithms for mean-payoff games. Form Methods Syst Des 38(2):97\u2013118","journal-title":"Form Methods Syst Des"},{"key":"9293_CR12","doi-asserted-by":"crossref","unstructured":"Chatterjee K, K\u00f6\u00dfler A, Schmid U (2013) Automated analysis of real-time scheduling using graph games. In: Proceedings of the 16th ACM international conference on hybrid systems: computation and control, HSCC \u201913, pp 163\u2013172. ACM, New York","DOI":"10.1145\/2461328.2461356"},{"issue":"3","key":"9293_CR13","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1007\/s00453-013-9843-7","volume":"70","author":"K Chatterjee","year":"2014","unstructured":"Chatterjee K, Henzinger M, Krinninger S, Nanongkai D (2014) Polynomial-time algorithms for energy games with special weight structures. Algorithmica 70(3):457\u2013492","journal-title":"Algorithmica"},{"key":"9293_CR14","doi-asserted-by":"crossref","unstructured":"Chatterjee K, Pavlogiannis A, K\u00f6\u00dfler A, Schmid U (2014) A framework for automated competitive analysis of on-line scheduling of firm-deadline tasks. In: RTSS \u201914, pp 118\u2013127","DOI":"10.1109\/RTSS.2014.9"},{"key":"9293_CR15","doi-asserted-by":"crossref","unstructured":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A (2015) Faster algorithms for quantitative verification in constant treewidth graphs. In: CAV","DOI":"10.1007\/978-3-319-21690-4_9"},{"key":"9293_CR16","volume-title":"Model checking","author":"EM Clarke Jr","year":"1999","unstructured":"Clarke EM Jr, Grumberg O, Peled DA (1999) Model checking. MIT Press, Cambridge"},{"issue":"1","key":"9293_CR17","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1109\/18.61109","volume":"37","author":"RL Cruz","year":"1991","unstructured":"Cruz RL (1991) A calculus for network delay. I. Network elements in isolation. IEEE Trans Inf Theory 37(1):114\u2013131. https:\/\/doi.org\/10.1109\/18.61109","journal-title":"IEEE Trans Inf Theory"},{"key":"9293_CR18","unstructured":"Dertouzos ML (1974) Control robotics: The procedural control of physical processes. In: IFIP Congress, pp 807\u2013813"},{"issue":"1","key":"9293_CR19","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/s11241-010-9100-y","volume":"46","author":"V Devadas","year":"2010","unstructured":"Devadas V, Li F, Aydin H (2010) Competitive analysis of online real-time scheduling algorithms under hard energy constraint. Real-Time Syst 46(1):88\u2013120. https:\/\/doi.org\/10.1007\/s11241-010-9100-y","journal-title":"Real-Time Syst"},{"issue":"2","key":"9293_CR20","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/BF01768705","volume":"8","author":"A Ehrenfeucht","year":"1979","unstructured":"Ehrenfeucht A, Mycielski J (1979) Positional strategies for mean payoff games. Int J Game Theory 8(2):109\u2013113","journal-title":"Int J Game Theory"},{"key":"9293_CR21","unstructured":"Englert M, Westermann M (2007) Considering suppressed packets improves buffer management in qos switches. In: Proceedings of the eighteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2007, New Orlean, January 7\u20139, 2007, pp 209\u2013218. http:\/\/dl.acm.org\/citation.cfm?id=1283383.1283406"},{"issue":"3","key":"9293_CR22","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/S0019-9958(83)80004-7","volume":"56","author":"H Galperin","year":"1983","unstructured":"Galperin H, Wigderson A (1983) Succinct representations of graphs. Inf Control 56(3):183\u2013198","journal-title":"Inf Control"},{"issue":"7","key":"9293_CR23","doi-asserted-by":"publisher","first-page":"1064","DOI":"10.1109\/49.103553","volume":"9","author":"SJ Golestani","year":"1991","unstructured":"Golestani SJ (1991) A framing strategy for congestion management. IEEE J Sel Areas Commun 9(7):1064\u20131077. https:\/\/doi.org\/10.1109\/49.103553","journal-title":"IEEE J Sel Areas Commun"},{"issue":"6","key":"9293_CR24","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1002\/jos.85","volume":"4","author":"BD Gupta","year":"2001","unstructured":"Gupta BD, Palis MA (2001) Online real-time preemptive scheduling of jobs with deadlines on multiple machines. J Sched 4(6):297\u2013312. https:\/\/doi.org\/10.1002\/jos.85","journal-title":"J Sched"},{"key":"9293_CR25","doi-asserted-by":"publisher","unstructured":"Haritsa JR, Carey MJ, Livny M (1990) On being optimistic about real-time constraints. In: Proceedings of the 9th ACM SIGACT-SIGMOD-SIGART symposium on principles of database systems, PODS \u201990, pp 331\u2013343. ACM, New York. https:\/\/doi.org\/10.1145\/298514.298585","DOI":"10.1145\/298514.298585"},{"key":"9293_CR26","doi-asserted-by":"crossref","unstructured":"Karp RM (1972) Reducibility among combinatorial problems. In: Proceedings of the Complexity of computer computations. Springer US","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"3","key":"9293_CR27","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0012-365X(78)90011-0","volume":"23","author":"RM Karp","year":"1978","unstructured":"Karp RM (1978) A characterization of the minimum cycle mean in a digraph. Discret Math 23(3):309\u2013311","journal-title":"Discret Math"},{"key":"9293_CR28","first-page":"1093","volume":"244","author":"LG Khachiyan","year":"1979","unstructured":"Khachiyan LG (1979) ) A polynomial algorithm in linear programming. Dokl Akad Nauk SSSR 244:1093\u20131096","journal-title":"Dokl Akad Nauk SSSR"},{"issue":"2","key":"9293_CR29","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1137\/S0097539792236882","volume":"24","author":"G Koren","year":"1995","unstructured":"Koren G, Shasha D (1995) $$\\text{ D }^{{over}}$$ D o v e r : an optimal on-line scheduling algorithm for overloaded uniprocessor real-time systems. SIAM J Comput 24(2):318\u2013339. https:\/\/doi.org\/10.1137\/S0097539792236882","journal-title":"SIAM J Comput"},{"key":"9293_CR30","doi-asserted-by":"crossref","unstructured":"Koutsoupias E (2011) Scheduling without payments. In: Proceedings of the 4th international conference on algorithmic game theory, SAGT\u201911, pp 143\u2013153. Springer, Berlin, Heidelberg","DOI":"10.1007\/978-3-642-24829-0_14"},{"issue":"1\u20134","key":"9293_CR31","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/BF01553887","volume":"4","author":"JT Leung","year":"1989","unstructured":"Leung JT (1989) A new algorithm for scheduling periodic, real-time tasks. Algorithmica 4(1\u20134):209\u2013219. https:\/\/doi.org\/10.1007\/BF01553887","journal-title":"Algorithmica"},{"key":"9293_CR32","unstructured":"Locke CD (1986) Best-effort decision-making for real-time scheduling. Ph.D. thesis, CMU, Pittsburgh"},{"key":"9293_CR33","doi-asserted-by":"publisher","unstructured":"Lu Z, Jantsch A (2007) Admitting and ejecting flits in wormhole-switched networks on chip. IET Comput Digit Tech 1(5):546\u2013556. https:\/\/doi.org\/10.1049\/iet-cdt:20050068","DOI":"10.1049\/iet-cdt:20050068"},{"key":"9293_CR34","doi-asserted-by":"crossref","unstructured":"L\u00fcbbecke E, Maurer O, Megow N, Wiese A (2016) A new approach to online scheduling: approximating the optimal competitive ratio. ACM Trans Algorithms 13(1):15:1\u201315:34","DOI":"10.1145\/2996800"},{"key":"9293_CR35","unstructured":"Madani O (2002) Polynomial value iteration algorithms for deterministic MDPs. In: Proceedings of the 18th conference on uncertainty in artificial intelligence, UAI \u201902, pp 311\u2013318"},{"key":"9293_CR36","doi-asserted-by":"crossref","unstructured":"Martin DA (1975) Borel determinacy. Ann Math 102(2): 363\u2013371 . http:\/\/www.jstor.org\/stable\/1971035","DOI":"10.2307\/1971035"},{"key":"9293_CR37","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511800481","volume-title":"Algorithmic game theory","author":"N Nisan","year":"2007","unstructured":"Nisan N, Roughgarden T, Tardos E, Vazirani VV (2007) Algorithmic game theory. Cambridge University Press, New York"},{"key":"9293_CR38","doi-asserted-by":"crossref","unstructured":"Palis MA (2004) Competitive algorithms for fine-grain real-time scheduling. In: Proceedings of the 25th IEEE real-time systems symposium, RTSS \u201904, pp 129\u2013138. IEEE Computer Society. http:\/\/doi.ieeecomputersociety.org\/10.1109\/REAL.2004.14","DOI":"10.1109\/REAL.2004.14"},{"key":"9293_CR39","volume-title":"Computational complexity","author":"CH Papadimitriou","year":"1993","unstructured":"Papadimitriou CH (1993) Computational complexity. Addison-Wesley, Reading"},{"key":"9293_CR40","doi-asserted-by":"publisher","unstructured":"Porter R (2004) Mechanism design for online real-time scheduling. In: Proceedings of the 5th ACM conference on electronic commerce, EC \u201904, pp 61\u201370. ACM, New York. https:\/\/doi.org\/10.1145\/988772.988783","DOI":"10.1145\/988772.988783"},{"key":"9293_CR41","doi-asserted-by":"publisher","unstructured":"Rajkumar R, Lee C, Lehoczky J, Siewiorek D (1997) A resource allocation model for qos management. In: Proceedings of the 18th IEEE real-time systems symposium, RTSS \u201997, pp 298 \u2013307. https:\/\/doi.org\/10.1109\/REAL.1997.641291","DOI":"10.1109\/REAL.1997.641291"},{"key":"9293_CR42","doi-asserted-by":"crossref","unstructured":"Shapley LS (1953) Stochastic games. Proc Natl Acad Sci USA 39(10):1095\u20131100. http:\/\/www.pnas.org\/content\/39\/10\/1095.short","DOI":"10.1073\/pnas.39.10.1953"},{"key":"9293_CR43","doi-asserted-by":"publisher","unstructured":"Sheikh AA, Brun O, Hladik PE, Prabhu BJ (2011) A best-response algorithm for multiprocessor periodic scheduling. In: Proceedings of the 2011 23rd euromicro conference on real-time systems, ECRTS \u201911, pp 228\u2013237. IEEE Computer Society, Washington. https:\/\/doi.org\/10.1109\/ECRTS.2011.29","DOI":"10.1109\/ECRTS.2011.29"},{"issue":"2","key":"9293_CR44","doi-asserted-by":"crossref","first-page":"146160","DOI":"10.1137\/0201010","volume":"1","author":"R Tarjan","year":"1972","unstructured":"Tarjan R (1972) Depth-first search and linear graph algorithms. SIAM J Comput 1(2):146160","journal-title":"SIAM J Comput"},{"key":"9293_CR45","doi-asserted-by":"publisher","unstructured":"Velner Y, Chatterjee K, Doyen L, Henzinger TA, Rabinovich A, Raskin JF (2015) The complexity of multi-mean-payoff and multi-energy games. Inf Comput 241(Suppl C):177\u2013196. https:\/\/doi.org\/10.1016\/j.ic.2015.03.001","DOI":"10.1016\/j.ic.2015.03.001"},{"issue":"12","key":"9293_CR46","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/0304-3975(95)00188-3","volume":"158","author":"U Zwick","year":"1996","unstructured":"Zwick U, Paterson M (1996) The complexity of mean payoff games on graphs. Theoret Comput Sci 158(12):343\u2013359","journal-title":"Theoret Comput Sci"}],"container-title":["Real-Time Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11241-017-9293-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11241-017-9293-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11241-017-9293-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,5]],"date-time":"2019-10-05T12:35:44Z","timestamp":1570278944000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11241-017-9293-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,11,1]]},"references-count":46,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["9293"],"URL":"http:\/\/dx.doi.org\/10.1007\/s11241-017-9293-4","relation":{},"ISSN":["0922-6443","1573-1383"],"issn-type":[{"value":"0922-6443","type":"print"},{"value":"1573-1383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,11,1]]}}}
