---
_id: '11402'
abstract:
- lang: eng
  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.
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).
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Laurent
  full_name: Doyen, Laurent
  last_name: Doyen
citation:
  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>
  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>.
  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.
  ista: Chatterjee K, Doyen L. 2022. Graph planning with expected finite horizon.
    Journal of Computer and System Sciences. 129, 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>.
  short: K. Chatterjee, L. Doyen, Journal of Computer and System Sciences 129 (2022)
    1–21.
date_created: 2022-05-22T22:01:40Z
date_published: 2022-11-01T00:00:00Z
date_updated: 2025-07-14T09:09:54Z
day: '01'
department:
- _id: KrCh
doi: 10.1016/j.jcss.2022.04.003
ec_funded: 1
external_id:
  arxiv:
  - '1802.03642'
  isi:
  - '000805002800001'
intvolume: '       129'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: ' https://doi.org/10.48550/arXiv.1802.03642'
month: '11'
oa: 1
oa_version: Preprint
page: 1-21
project:
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S11407
  name: Game Theory
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
  call_identifier: H2020
  grant_number: '863818'
  name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: Journal of Computer and System Sciences
publication_identifier:
  eissn:
  - 1090-2724
  issn:
  - 0022-0000
publication_status: published
publisher: Elsevier
quality_controlled: '1'
related_material:
  record:
  - id: '7402'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: Graph planning with expected finite horizon
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 129
year: '2022'
...
---
_id: '9239'
abstract:
- lang: eng
  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.'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Guy
  full_name: Avni, Guy
  id: 463C8BC2-F248-11E8-B48F-1D18A9856A87
  last_name: Avni
  orcid: 0000-0001-5588-8287
- first_name: Thomas A
  full_name: Henzinger, Thomas A
  id: 40876CD8-F248-11E8-B48F-1D18A9856A87
  last_name: Henzinger
  orcid: 0000-0002-2985-7724
- first_name: Đorđe
  full_name: Žikelić, Đorđe
  last_name: Žikelić
citation:
  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>
  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>
  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>.
  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.
  ista: Avni G, Henzinger TA, Žikelić Đ. 2021. Bidding mechanisms in graph games.
    Journal of Computer and System Sciences. 119(8), 133–144.
  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.
date_created: 2021-03-14T23:01:32Z
date_published: 2021-03-03T00:00:00Z
date_updated: 2023-08-07T14:08:34Z
day: '03'
department:
- _id: ToHe
doi: 10.1016/j.jcss.2021.02.008
external_id:
  arxiv:
  - '1905.03835'
  isi:
  - '000634149800009'
intvolume: '       119'
isi: 1
issue: '8'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.1905.03835
month: '03'
oa: 1
oa_version: Preprint
page: 133-144
publication: Journal of Computer and System Sciences
publication_identifier:
  eissn:
  - 1090-2724
  issn:
  - 0022-0000
publication_status: published
publisher: Elsevier
quality_controlled: '1'
related_material:
  record:
  - id: '6884'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: Bidding mechanisms in graph games
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 119
year: '2021'
...
---
_id: '4057'
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
citation:
  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>
  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>.
  ieee: H. Edelsbrunner, “Corrigendum,” <i>Journal of Computer and System Sciences</i>,
    vol. 42, no. 2. Elsevier, pp. 249–251, 1991.
  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.
date_created: 2018-12-11T12:06:41Z
date_published: 1991-04-01T00:00:00Z
date_updated: 2022-03-02T10:06:55Z
day: '01'
doi: 10.1016/0022-0000(91)90013-U
extern: '1'
intvolume: '        42'
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://www.sciencedirect.com/science/article/pii/002200009190013U?via%3Dihub
month: '04'
oa: 1
oa_version: Published Version
page: 249 - 251
publication: Journal of Computer and System Sciences
publication_identifier:
  eissn:
  - 1090-2724
  issn:
  - 0022-0000
publication_status: published
publisher: Elsevier
publist_id: '2071'
quality_controlled: '1'
status: public
title: Corrigendum
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 42
year: '1991'
...
---
_id: '4082'
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.
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.
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Leonidas
  full_name: Guibas, Leonidas
  last_name: Guibas
citation:
  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>
  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>
  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>.
  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.
  ista: Edelsbrunner H, Guibas L. 1989. Topologically sweeping an arrangement. Journal
    of Computer and System Sciences. 38(1), 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>.
  short: H. Edelsbrunner, L. Guibas, Journal of Computer and System Sciences 38 (1989)
    165–194.
date_created: 2018-12-11T12:06:50Z
date_published: 1989-02-01T00:00:00Z
date_updated: 2022-02-10T16:06:05Z
day: '01'
doi: 10.1016/0022-0000(89)90038-X
extern: '1'
intvolume: '        38'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://www.sciencedirect.com/science/article/pii/002200008990038X?via%3Dihub
month: '02'
oa: 1
oa_version: Published Version
page: 165 - 194
publication: Journal of Computer and System Sciences
publication_identifier:
  eissn:
  - 1090-2724
  issn:
  - 0022-0000
publication_status: published
publisher: Elsevier
publist_id: '2039'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Topologically sweeping an arrangement
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 38
year: '1989'
...