[{"language":[{"iso":"eng"}],"oa_version":"Preprint","project":[{"grant_number":"S11407","name":"Game Theory","_id":"25863FF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818","call_identifier":"H2020","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E"}],"month":"11","publication":"Journal of Computer and System Sciences","main_file_link":[{"open_access":"1","url":" https://doi.org/10.48550/arXiv.1802.03642"}],"related_material":{"record":[{"relation":"earlier_version","id":"7402","status":"public"}]},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","status":"public","publication_identifier":{"eissn":["1090-2724"],"issn":["0022-0000"]},"oa":1,"date_published":"2022-11-01T00:00:00Z","type":"journal_article","publisher":"Elsevier","article_type":"original","page":"1-21","quality_controlled":"1","ec_funded":1,"publication_status":"published","article_processing_charge":"No","department":[{"_id":"KrCh"}],"date_created":"2022-05-22T22:01:40Z","title":"Graph planning with expected finite horizon","intvolume":"       129","_id":"11402","scopus_import":"1","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu"},{"full_name":"Doyen, Laurent","last_name":"Doyen","first_name":"Laurent"}],"acknowledgement":"This work was partially supported by Austrian Science Fund (FWF) NFN Grant No RiSE/SHiNE S11407 and by the grant ERC CoG 863818 (ForM-SMArt).","volume":129,"doi":"10.1016/j.jcss.2022.04.003","arxiv":1,"day":"01","abstract":[{"text":"Fixed-horizon planning considers a weighted graph and asks to construct a path that maximizes the sum of weights for a given time horizon T. However, in many scenarios, the time horizon is not fixed, but the stopping time is chosen according to some distribution such that the expected stopping time is T. If the stopping-time distribution is not known, then to ensure robustness, the distribution is chosen by an adversary as the worst-case scenario. A stationary plan for every vertex always chooses the same outgoing edge. For fixed horizon or fixed stopping-time distribution, stationary plans are not sufficient for optimality. Quite surprisingly we show that when an adversary chooses the stopping-time distribution with expected stopping-time T, then stationary plans are sufficient. While computing optimal stationary plans for fixed horizon is NP-complete, we show that computing optimal stationary plans under adversarial stopping-time distribution can be achieved in polynomial time.","lang":"eng"}],"date_updated":"2025-07-14T09:09:54Z","citation":{"ista":"Chatterjee K, Doyen L. 2022. Graph planning with expected finite horizon. Journal of Computer and System Sciences. 129, 1–21.","short":"K. Chatterjee, L. Doyen, Journal of Computer and System Sciences 129 (2022) 1–21.","mla":"Chatterjee, Krishnendu, and Laurent Doyen. “Graph Planning with Expected Finite Horizon.” <i>Journal of Computer and System Sciences</i>, vol. 129, Elsevier, 2022, pp. 1–21, doi:<a href=\"https://doi.org/10.1016/j.jcss.2022.04.003\">10.1016/j.jcss.2022.04.003</a>.","ieee":"K. Chatterjee and L. Doyen, “Graph planning with expected finite horizon,” <i>Journal of Computer and System Sciences</i>, vol. 129. Elsevier, pp. 1–21, 2022.","chicago":"Chatterjee, Krishnendu, and Laurent Doyen. “Graph Planning with Expected Finite Horizon.” <i>Journal of Computer and System Sciences</i>. Elsevier, 2022. <a href=\"https://doi.org/10.1016/j.jcss.2022.04.003\">https://doi.org/10.1016/j.jcss.2022.04.003</a>.","ama":"Chatterjee K, Doyen L. Graph planning with expected finite horizon. <i>Journal of Computer and System Sciences</i>. 2022;129:1-21. doi:<a href=\"https://doi.org/10.1016/j.jcss.2022.04.003\">10.1016/j.jcss.2022.04.003</a>","apa":"Chatterjee, K., &#38; Doyen, L. (2022). Graph planning with expected finite horizon. <i>Journal of Computer and System Sciences</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.jcss.2022.04.003\">https://doi.org/10.1016/j.jcss.2022.04.003</a>"},"year":"2022","isi":1,"external_id":{"isi":["000805002800001"],"arxiv":["1802.03642"]}},{"volume":119,"abstract":[{"text":"A graph game proceeds as follows: two players move a token through a graph to produce a finite or infinite path, which determines the payoff of the game. We study bidding games in which in each turn, an auction determines which player moves the token. Bidding games were largely studied in combination with two variants of first-price auctions called “Richman” and “poorman” bidding. We study taxman bidding, which span the spectrum between the two. The game is parameterized by a constant : portion τ of the winning bid is paid to the other player, and portion  to the bank. While finite-duration (reachability) taxman games have been studied before, we present, for the first time, results on infinite-duration taxman games: we unify, generalize, and simplify previous equivalences between bidding games and a class of stochastic games called random-turn games.","lang":"eng"}],"day":"03","doi":"10.1016/j.jcss.2021.02.008","arxiv":1,"external_id":{"arxiv":["1905.03835"],"isi":["000634149800009"]},"isi":1,"citation":{"apa":"Avni, G., Henzinger, T. A., &#38; Žikelić, Đ. (2021). Bidding mechanisms in graph games. <i>Journal of Computer and System Sciences</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.jcss.2021.02.008\">https://doi.org/10.1016/j.jcss.2021.02.008</a>","ama":"Avni G, Henzinger TA, Žikelić Đ. Bidding mechanisms in graph games. <i>Journal of Computer and System Sciences</i>. 2021;119(8):133-144. doi:<a href=\"https://doi.org/10.1016/j.jcss.2021.02.008\">10.1016/j.jcss.2021.02.008</a>","ieee":"G. Avni, T. A. Henzinger, and Đ. Žikelić, “Bidding mechanisms in graph games,” <i>Journal of Computer and System Sciences</i>, vol. 119, no. 8. Elsevier, pp. 133–144, 2021.","chicago":"Avni, Guy, Thomas A Henzinger, and Đorđe Žikelić. “Bidding Mechanisms in Graph Games.” <i>Journal of Computer and System Sciences</i>. Elsevier, 2021. <a href=\"https://doi.org/10.1016/j.jcss.2021.02.008\">https://doi.org/10.1016/j.jcss.2021.02.008</a>.","mla":"Avni, Guy, et al. “Bidding Mechanisms in Graph Games.” <i>Journal of Computer and System Sciences</i>, vol. 119, no. 8, Elsevier, 2021, pp. 133–44, doi:<a href=\"https://doi.org/10.1016/j.jcss.2021.02.008\">10.1016/j.jcss.2021.02.008</a>.","short":"G. Avni, T.A. Henzinger, Đ. Žikelić, Journal of Computer and System Sciences 119 (2021) 133–144.","ista":"Avni G, Henzinger TA, Žikelić Đ. 2021. Bidding mechanisms in graph games. Journal of Computer and System Sciences. 119(8), 133–144."},"year":"2021","date_updated":"2023-08-07T14:08:34Z","article_type":"original","publisher":"Elsevier","quality_controlled":"1","page":"133-144","intvolume":"       119","title":"Bidding mechanisms in graph games","article_processing_charge":"No","department":[{"_id":"ToHe"}],"date_created":"2021-03-14T23:01:32Z","publication_status":"published","issue":"8","author":[{"id":"463C8BC2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-5588-8287","full_name":"Avni, Guy","first_name":"Guy","last_name":"Avni"},{"full_name":"Henzinger, Thomas A","orcid":"0000-0002-2985-7724","last_name":"Henzinger","first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Žikelić, Đorđe","last_name":"Žikelić","first_name":"Đorđe"}],"scopus_import":"1","_id":"9239","status":"public","related_material":{"record":[{"status":"public","relation":"earlier_version","id":"6884"}]},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.1905.03835"}],"oa":1,"publication_identifier":{"eissn":["1090-2724"],"issn":["0022-0000"]},"type":"journal_article","date_published":"2021-03-03T00:00:00Z","language":[{"iso":"eng"}],"month":"03","oa_version":"Preprint","publication":"Journal of Computer and System Sciences"},{"language":[{"iso":"eng"}],"month":"04","oa_version":"Published Version","publication":"Journal of Computer and System Sciences","status":"public","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","main_file_link":[{"url":"https://www.sciencedirect.com/science/article/pii/002200009190013U?via%3Dihub","open_access":"1"}],"publist_id":"2071","oa":1,"publication_identifier":{"issn":["0022-0000"],"eissn":["1090-2724"]},"type":"journal_article","date_published":"1991-04-01T00:00:00Z","article_type":"original","publisher":"Elsevier","quality_controlled":"1","page":"249 - 251","intvolume":"        42","title":"Corrigendum","date_created":"2018-12-11T12:06:41Z","article_processing_charge":"No","publication_status":"published","issue":"2","author":[{"full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"}],"_id":"4057","extern":"1","volume":42,"day":"01","doi":"10.1016/0022-0000(91)90013-U","citation":{"ieee":"H. Edelsbrunner, “Corrigendum,” <i>Journal of Computer and System Sciences</i>, vol. 42, no. 2. Elsevier, pp. 249–251, 1991.","chicago":"Edelsbrunner, Herbert. “Corrigendum.” <i>Journal of Computer and System Sciences</i>. Elsevier, 1991. <a href=\"https://doi.org/10.1016/0022-0000(91)90013-U\">https://doi.org/10.1016/0022-0000(91)90013-U</a>.","ama":"Edelsbrunner H. Corrigendum. <i>Journal of Computer and System Sciences</i>. 1991;42(2):249-251. doi:<a href=\"https://doi.org/10.1016/0022-0000(91)90013-U\">10.1016/0022-0000(91)90013-U</a>","apa":"Edelsbrunner, H. (1991). Corrigendum. <i>Journal of Computer and System Sciences</i>. Elsevier. <a href=\"https://doi.org/10.1016/0022-0000(91)90013-U\">https://doi.org/10.1016/0022-0000(91)90013-U</a>","ista":"Edelsbrunner H. 1991. Corrigendum. Journal of Computer and System Sciences. 42(2), 249–251.","mla":"Edelsbrunner, Herbert. “Corrigendum.” <i>Journal of Computer and System Sciences</i>, vol. 42, no. 2, Elsevier, 1991, pp. 249–51, doi:<a href=\"https://doi.org/10.1016/0022-0000(91)90013-U\">10.1016/0022-0000(91)90013-U</a>.","short":"H. Edelsbrunner, Journal of Computer and System Sciences 42 (1991) 249–251."},"year":"1991","date_updated":"2022-03-02T10:06:55Z"},{"abstract":[{"lang":"eng","text":"Sweeping a collection of figures in the Euclidean plane with a straight line is one of the novel algorithmic paradigms that have emerged in the field of computational geometry. In this paper we demonstrate the advantages of sweeping with a topological line that is not necessarily straight. We show how an arrangement of n lines in the plane can be swept over in O(n2) time and O(n) space by a such a line. In the process each element, i.e., vertex, edge, or region, is visited once in a consistent ordering. Our technique makes use of novel data structures which exhibit interesting amortized complexity behavior; the result is an algorithm that improves upon all its predecessors either in the space or the time bounds, as well as being eminently practical. Numerous applications of the technique to problems in computational geometry are given—many through the use of duality transforms. Examples include solving visibility problems, detecting degeneracies in configurations, computing the extremal shadows of convex polytopes, and others. Even though our basic technique solves a planar problem, its applications include several problems in higher dimensions."}],"day":"01","doi":"10.1016/0022-0000(89)90038-X","citation":{"short":"H. Edelsbrunner, L. Guibas, Journal of Computer and System Sciences 38 (1989) 165–194.","mla":"Edelsbrunner, Herbert, and Leonidas Guibas. “Topologically Sweeping an Arrangement.” <i>Journal of Computer and System Sciences</i>, vol. 38, no. 1, Elsevier, 1989, pp. 165–94, doi:<a href=\"https://doi.org/10.1016/0022-0000(89)90038-X\">10.1016/0022-0000(89)90038-X</a>.","ista":"Edelsbrunner H, Guibas L. 1989. Topologically sweeping an arrangement. Journal of Computer and System Sciences. 38(1), 165–194.","apa":"Edelsbrunner, H., &#38; Guibas, L. (1989). Topologically sweeping an arrangement. <i>Journal of Computer and System Sciences</i>. Elsevier. <a href=\"https://doi.org/10.1016/0022-0000(89)90038-X\">https://doi.org/10.1016/0022-0000(89)90038-X</a>","ama":"Edelsbrunner H, Guibas L. Topologically sweeping an arrangement. <i>Journal of Computer and System Sciences</i>. 1989;38(1):165-194. doi:<a href=\"https://doi.org/10.1016/0022-0000(89)90038-X\">10.1016/0022-0000(89)90038-X</a>","ieee":"H. Edelsbrunner and L. Guibas, “Topologically sweeping an arrangement,” <i>Journal of Computer and System Sciences</i>, vol. 38, no. 1. Elsevier, pp. 165–194, 1989.","chicago":"Edelsbrunner, Herbert, and Leonidas Guibas. “Topologically Sweeping an Arrangement.” <i>Journal of Computer and System Sciences</i>. Elsevier, 1989. <a href=\"https://doi.org/10.1016/0022-0000(89)90038-X\">https://doi.org/10.1016/0022-0000(89)90038-X</a>."},"year":"1989","date_updated":"2022-02-10T16:06:05Z","extern":"1","acknowledgement":"he authors wish to thank Raimund Seidel for suggesting the argument that we used to prove Theorem 3.1, Harald Rosenberger who implemented the topological sweep and compared it with a straight line sweep, the students who took the Stanford 1985 analysis of algorithms qualifying examination and suffered through a version of this problem, and finally Lyle Ramshaw and Cynthia Hibbard for their detailed reading and comments on the manuscript. The constructive criticism of an anonymous referee is also appreciated.","volume":38,"intvolume":"        38","title":"Topologically sweeping an arrangement","date_created":"2018-12-11T12:06:50Z","article_processing_charge":"No","publication_status":"published","issue":"1","author":[{"full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Guibas, Leonidas","last_name":"Guibas","first_name":"Leonidas"}],"scopus_import":"1","_id":"4082","article_type":"original","publisher":"Elsevier","quality_controlled":"1","page":"165 - 194","oa":1,"publist_id":"2039","publication_identifier":{"issn":["0022-0000"],"eissn":["1090-2724"]},"type":"journal_article","date_published":"1989-02-01T00:00:00Z","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","status":"public","main_file_link":[{"open_access":"1","url":"https://www.sciencedirect.com/science/article/pii/002200008990038X?via%3Dihub"}],"month":"02","oa_version":"Published Version","publication":"Journal of Computer and System Sciences","language":[{"iso":"eng"}]}]