---
_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. Journal
of Computer and System Sciences. 2022;129:1-21. doi:10.1016/j.jcss.2022.04.003
apa: Chatterjee, K., & Doyen, L. (2022). Graph planning with expected finite
horizon. Journal of Computer and System Sciences. Elsevier. https://doi.org/10.1016/j.jcss.2022.04.003
chicago: Chatterjee, Krishnendu, and Laurent Doyen. “Graph Planning with Expected
Finite Horizon.” Journal of Computer and System Sciences. Elsevier, 2022.
https://doi.org/10.1016/j.jcss.2022.04.003.
ieee: K. Chatterjee and L. Doyen, “Graph planning with expected finite horizon,”
Journal of Computer and System Sciences, 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.” Journal of Computer and System Sciences, vol. 129, Elsevier,
2022, pp. 1–21, doi:10.1016/j.jcss.2022.04.003.
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. Journal
of Computer and System Sciences. 2021;119(8):133-144. doi:10.1016/j.jcss.2021.02.008
apa: Avni, G., Henzinger, T. A., & Žikelić, Đ. (2021). Bidding mechanisms in
graph games. Journal of Computer and System Sciences. Elsevier. https://doi.org/10.1016/j.jcss.2021.02.008
chicago: Avni, Guy, Thomas A Henzinger, and Đorđe Žikelić. “Bidding Mechanisms in
Graph Games.” Journal of Computer and System Sciences. Elsevier, 2021.
https://doi.org/10.1016/j.jcss.2021.02.008.
ieee: G. Avni, T. A. Henzinger, and Đ. Žikelić, “Bidding mechanisms in graph games,”
Journal of Computer and System Sciences, 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.” Journal of Computer
and System Sciences, vol. 119, no. 8, Elsevier, 2021, pp. 133–44, doi:10.1016/j.jcss.2021.02.008.
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: '11766'
abstract:
- lang: eng
text: 'This paper studies the multicast routing and admission control problem on
unit-capacity tree and mesh topologies in the throughput model. The problem is
a generalization of the edge-disjoint paths problem and is NP-hard both on trees
and meshes. We study both the offline and the online version of the problem: In
the offline setting, we give the first constant-factor approximation algorithm
for trees, and an -factor approximation algorithm for meshes. In the online setting,
we give the first polylogarithmic competitive online algorithm for tree and mesh
topologies. No polylogarithmic-competitive algorithm is possible on general network
topologies (Lower bounds for on-line graph problems with application to on-line
circuits and optical routing, in: Proceedings of the 28th ACM Symposium on Theory
of Computing, 1996, pp. 531–540) and there exists a polylogarithmic lower bound
on the competitive ratio of any online algorithm on tree topologies (Making commitments
in the face of uncertainity: how to pick a winner almost every time, in: Proceedings
of the 28th Annual ACM Symposium on Theory of Computing, 1996, pp. 519–530). We
prove the same lower bound for meshes.'
article_processing_charge: No
article_type: original
author:
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Stefano
full_name: Leonardi, Stefano
last_name: Leonardi
citation:
ama: Henzinger MH, Leonardi S. Scheduling multicasts on unit-capacity trees and
meshes. Journal of Computer and System Sciences. 2003;66(3):567-611. doi:10.1016/s0022-0000(03)00043-6
apa: Henzinger, M. H., & Leonardi, S. (2003). Scheduling multicasts on unit-capacity
trees and meshes. Journal of Computer and System Sciences. Elsevier. https://doi.org/10.1016/s0022-0000(03)00043-6
chicago: Henzinger, Monika H, and Stefano Leonardi. “Scheduling Multicasts on Unit-Capacity
Trees and Meshes.” Journal of Computer and System Sciences. Elsevier, 2003.
https://doi.org/10.1016/s0022-0000(03)00043-6.
ieee: M. H. Henzinger and S. Leonardi, “Scheduling multicasts on unit-capacity trees
and meshes,” Journal of Computer and System Sciences, vol. 66, no. 3. Elsevier,
pp. 567–611, 2003.
ista: Henzinger MH, Leonardi S. 2003. Scheduling multicasts on unit-capacity trees
and meshes. Journal of Computer and System Sciences. 66(3), 567–611.
mla: Henzinger, Monika H., and Stefano Leonardi. “Scheduling Multicasts on Unit-Capacity
Trees and Meshes.” Journal of Computer and System Sciences, vol. 66, no.
3, Elsevier, 2003, pp. 567–611, doi:10.1016/s0022-0000(03)00043-6.
short: M.H. Henzinger, S. Leonardi, Journal of Computer and System Sciences 66 (2003)
567–611.
date_created: 2022-08-08T12:24:35Z
date_published: 2003-05-01T00:00:00Z
date_updated: 2023-02-10T08:03:31Z
day: '01'
doi: 10.1016/s0022-0000(03)00043-6
extern: '1'
intvolume: ' 66'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1016/S0022-0000(03)00043-6
month: '05'
oa: 1
oa_version: Published Version
page: 567-611
publication: Journal of Computer and System Sciences
publication_identifier:
issn:
- 0022-0000
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Scheduling multicasts on unit-capacity trees and meshes
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 66
year: '2003'
...
---
_id: '11767'
abstract:
- lang: eng
text: We give a linear-time algorithm for single-source shortest paths in planar
graphs with nonnegative edge-lengths. Our algorithm also yields a linear-time
algorithm for maximum flow in a planar graph with the source and sink on the same
face. For the case where negative edge-lengths are allowed, we give an algorithm
requiringO(n4/3 log(nL)) time, whereLis the absolute value of the most negative
length. This algorithm can be used to obtain similar bounds for computing a feasible
flow in a planar network, for finding a perfect matching in a planar bipartite
graph, and for finding a maximum flow in a planar graph when the source and sink
are not on the same face. We also give parallel and dynamic versions of these
algorithms.
article_processing_charge: No
article_type: original
author:
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Philip
full_name: Klein, Philip
last_name: Klein
- first_name: Satish
full_name: Rao, Satish
last_name: Rao
- first_name: Sairam
full_name: Subramanian, Sairam
last_name: Subramanian
citation:
ama: Henzinger MH, Klein P, Rao S, Subramanian S. Faster shortest-path algorithms
for planar graphs. Journal of Computer and System Sciences. 1997;55(1):3-23.
doi:10.1006/jcss.1997.1493
apa: Henzinger, M. H., Klein, P., Rao, S., & Subramanian, S. (1997). Faster
shortest-path algorithms for planar graphs. Journal of Computer and System
Sciences. Elsevier. https://doi.org/10.1006/jcss.1997.1493
chicago: Henzinger, Monika H, Philip Klein, Satish Rao, and Sairam Subramanian.
“Faster Shortest-Path Algorithms for Planar Graphs.” Journal of Computer and
System Sciences. Elsevier, 1997. https://doi.org/10.1006/jcss.1997.1493.
ieee: M. H. Henzinger, P. Klein, S. Rao, and S. Subramanian, “Faster shortest-path
algorithms for planar graphs,” Journal of Computer and System Sciences,
vol. 55, no. 1. Elsevier, pp. 3–23, 1997.
ista: Henzinger MH, Klein P, Rao S, Subramanian S. 1997. Faster shortest-path algorithms
for planar graphs. Journal of Computer and System Sciences. 55(1), 3–23.
mla: Henzinger, Monika H., et al. “Faster Shortest-Path Algorithms for Planar Graphs.”
Journal of Computer and System Sciences, vol. 55, no. 1, Elsevier, 1997,
pp. 3–23, doi:10.1006/jcss.1997.1493.
short: M.H. Henzinger, P. Klein, S. Rao, S. Subramanian, Journal of Computer and
System Sciences 55 (1997) 3–23.
date_created: 2022-08-08T12:28:45Z
date_published: 1997-08-01T00:00:00Z
date_updated: 2022-09-12T10:46:21Z
day: '01'
doi: 10.1006/jcss.1997.1493
extern: '1'
intvolume: ' 55'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1006/jcss.1997.1493
month: '08'
oa: 1
oa_version: Published Version
page: 3-23
publication: Journal of Computer and System Sciences
publication_identifier:
issn:
- 0022-0000
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Faster shortest-path algorithms for planar graphs
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 55
year: '1997'
...
---
_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. Journal of Computer and System Sciences.
1991;42(2):249-251. doi:10.1016/0022-0000(91)90013-U
apa: Edelsbrunner, H. (1991). Corrigendum. Journal of Computer and System Sciences.
Elsevier. https://doi.org/10.1016/0022-0000(91)90013-U
chicago: Edelsbrunner, Herbert. “Corrigendum.” Journal of Computer and System
Sciences. Elsevier, 1991. https://doi.org/10.1016/0022-0000(91)90013-U.
ieee: H. Edelsbrunner, “Corrigendum,” Journal of Computer and System Sciences,
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.” Journal of Computer and System Sciences,
vol. 42, no. 2, Elsevier, 1991, pp. 249–51, doi:10.1016/0022-0000(91)90013-U.
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. Journal
of Computer and System Sciences. 1989;38(1):165-194. doi:10.1016/0022-0000(89)90038-X
apa: Edelsbrunner, H., & Guibas, L. (1989). Topologically sweeping an arrangement.
Journal of Computer and System Sciences. Elsevier. https://doi.org/10.1016/0022-0000(89)90038-X
chicago: Edelsbrunner, Herbert, and Leonidas Guibas. “Topologically Sweeping an
Arrangement.” Journal of Computer and System Sciences. Elsevier, 1989.
https://doi.org/10.1016/0022-0000(89)90038-X.
ieee: H. Edelsbrunner and L. Guibas, “Topologically sweeping an arrangement,” Journal
of Computer and System Sciences, 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.”
Journal of Computer and System Sciences, vol. 38, no. 1, Elsevier, 1989,
pp. 165–94, doi:10.1016/0022-0000(89)90038-X.
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'
...