---
_id: '14820'
abstract:
- lang: eng
text: "We consider a natural problem dealing with weighted packet selection across
a rechargeable link, which e.g., finds applications in cryptocurrency networks.
The capacity of a link (u, v) is determined by how many nodes u and v allocate
for this link. Specifically, the input is a finite ordered sequence of packets
that arrive in both directions along a link. Given (u, v) and a packet of weight
x going from u to v, node u can either accept or reject the packet. If u accepts
the packet, the capacity on link (u, v) decreases by x. Correspondingly, v's capacity
on \r\n increases by x. If a node rejects the packet, this will entail a cost
affinely linear in the weight of the packet. A link is “rechargeable” in the sense
that the total capacity of the link has to remain constant, but the allocation
of capacity at the ends of the link can depend arbitrarily on the nodes' decisions.
The goal is to minimise the sum of the capacity injected into the link and the
cost of rejecting packets. We show that the problem is NP-hard, but can be approximated
efficiently with a ratio of (1+E) . (1+3) for some arbitrary E>0."
acknowledgement: We thank Mahsa Bastankhah and Mohammad Ali Maddah-Ali for fruitful
discussions about different variants of the problem. This work is supported by the
European Research Council (ERC) Consolidator Project 864228 (AdjustNet), 2020-2025,
the ERC CoG 863818 (ForM-SMArt), and the German Research Foundation (DFG) grant
470029389 (FlexNets), 2021-2024.
article_number: '114353'
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- first_name: Stefan
full_name: Schmid, Stefan
last_name: Schmid
- first_name: Jakub
full_name: Svoboda, Jakub
id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
last_name: Svoboda
orcid: 0000-0002-1419-3267
- first_name: Michelle X
full_name: Yeo, Michelle X
id: 2D82B818-F248-11E8-B48F-1D18A9856A87
last_name: Yeo
orcid: 0009-0001-3676-4809
citation:
ama: 'Schmid S, Svoboda J, Yeo MX. Weighted packet selection for rechargeable links
in cryptocurrency networks: Complexity and approximation. Theoretical Computer
Science. 2024;989. doi:10.1016/j.tcs.2023.114353'
apa: 'Schmid, S., Svoboda, J., & Yeo, M. X. (2024). Weighted packet selection
for rechargeable links in cryptocurrency networks: Complexity and approximation.
Theoretical Computer Science. Elsevier. https://doi.org/10.1016/j.tcs.2023.114353'
chicago: 'Schmid, Stefan, Jakub Svoboda, and Michelle X Yeo. “Weighted Packet Selection
for Rechargeable Links in Cryptocurrency Networks: Complexity and Approximation.”
Theoretical Computer Science. Elsevier, 2024. https://doi.org/10.1016/j.tcs.2023.114353.'
ieee: 'S. Schmid, J. Svoboda, and M. X. Yeo, “Weighted packet selection for rechargeable
links in cryptocurrency networks: Complexity and approximation,” Theoretical
Computer Science, vol. 989. Elsevier, 2024.'
ista: 'Schmid S, Svoboda J, Yeo MX. 2024. Weighted packet selection for rechargeable
links in cryptocurrency networks: Complexity and approximation. Theoretical Computer
Science. 989, 114353.'
mla: 'Schmid, Stefan, et al. “Weighted Packet Selection for Rechargeable Links in
Cryptocurrency Networks: Complexity and Approximation.” Theoretical Computer
Science, vol. 989, 114353, Elsevier, 2024, doi:10.1016/j.tcs.2023.114353.'
short: S. Schmid, J. Svoboda, M.X. Yeo, Theoretical Computer Science 989 (2024).
corr_author: '1'
date_created: 2024-01-16T13:40:41Z
date_published: 2024-03-21T00:00:00Z
date_updated: 2025-12-02T14:02:37Z
day: '21'
ddc:
- '000'
department:
- _id: KrCh
- _id: KrPi
doi: 10.1016/j.tcs.2023.114353
ec_funded: 1
external_id:
isi:
- '001168211400001'
file:
- access_level: open_access
checksum: efd5b7e738bf845312ba53889a3e13e4
content_type: application/pdf
creator: dernst
date_created: 2024-07-16T12:02:25Z
date_updated: 2024-07-16T12:02:25Z
file_id: '17263'
file_name: 2024_TheorComputerScience_Schmid.pdf
file_size: 603570
relation: main_file
success: 1
file_date_updated: 2024-07-16T12:02:25Z
has_accepted_license: '1'
intvolume: ' 989'
isi: 1
keyword:
- General Computer Science
- Theoretical Computer Science
language:
- iso: eng
month: '03'
oa: 1
oa_version: Published Version
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: Theoretical Computer Science
publication_identifier:
issn:
- 0304-3975
publication_status: published
publisher: Elsevier
quality_controlled: '1'
related_material:
record:
- id: '19985'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: 'Weighted packet selection for rechargeable links in cryptocurrency networks:
Complexity and approximation'
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 989
year: '2024'
...
---
_id: '14362'
abstract:
- lang: eng
text: "Motivated by recent applications to entropy theory in dynamical systems,
we generalise notions introduced by Matthews and define weakly weighted and componentwise
weakly weighted (generalised) quasi-metrics. We then systematise and extend to
full generality the correspondences between these objects and other structures
arising in theoretical computer science and dynamics. In particular, we study
the correspondences with weak partial metrics and, if the underlying space is
a semilattice, with invariant (generalised) quasi-metrics satisfying the descending
path condition, and with strictly monotone semi(-co-)valuations.\r\nWe conclude
discussing, for endomorphisms of generalised quasi-metric semilattices, a generalisation
of both the known intrinsic semilattice entropy and the semigroup entropy."
article_number: '114129'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Ilaria
full_name: Castellano, Ilaria
last_name: Castellano
- first_name: Anna
full_name: Giordano Bruno, Anna
last_name: Giordano Bruno
- first_name: Nicolò
full_name: Zava, Nicolò
id: c8b3499c-7a77-11eb-b046-aa368cbbf2ad
last_name: Zava
orcid: 0000-0001-8686-1888
citation:
ama: Castellano I, Giordano Bruno A, Zava N. Weakly weighted generalised quasi-metric
spaces and semilattices. Theoretical Computer Science. 2023;977. doi:10.1016/j.tcs.2023.114129
apa: Castellano, I., Giordano Bruno, A., & Zava, N. (2023). Weakly weighted
generalised quasi-metric spaces and semilattices. Theoretical Computer Science.
Elsevier. https://doi.org/10.1016/j.tcs.2023.114129
chicago: Castellano, Ilaria, Anna Giordano Bruno, and Nicolò Zava. “Weakly Weighted
Generalised Quasi-Metric Spaces and Semilattices.” Theoretical Computer Science.
Elsevier, 2023. https://doi.org/10.1016/j.tcs.2023.114129.
ieee: I. Castellano, A. Giordano Bruno, and N. Zava, “Weakly weighted generalised
quasi-metric spaces and semilattices,” Theoretical Computer Science, vol.
977. Elsevier, 2023.
ista: Castellano I, Giordano Bruno A, Zava N. 2023. Weakly weighted generalised
quasi-metric spaces and semilattices. Theoretical Computer Science. 977, 114129.
mla: Castellano, Ilaria, et al. “Weakly Weighted Generalised Quasi-Metric Spaces
and Semilattices.” Theoretical Computer Science, vol. 977, 114129, Elsevier,
2023, doi:10.1016/j.tcs.2023.114129.
short: I. Castellano, A. Giordano Bruno, N. Zava, Theoretical Computer Science 977
(2023).
corr_author: '1'
date_created: 2023-09-24T22:01:11Z
date_published: 2023-10-25T00:00:00Z
date_updated: 2024-10-09T21:07:00Z
day: '25'
department:
- _id: HeEd
doi: 10.1016/j.tcs.2023.114129
external_id:
arxiv:
- '2212.08424'
isi:
- '001076934000001'
intvolume: ' 977'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: 'https://doi.org/10.48550/arXiv.2212.08424 '
month: '10'
oa: 1
oa_version: Preprint
publication: Theoretical Computer Science
publication_identifier:
issn:
- 0304-3975
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Weakly weighted generalised quasi-metric spaces and semilattices
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 977
year: '2023'
...
---
_id: '12566'
abstract:
- lang: eng
text: "Approximate agreement is one of the few variants of consensus that can be
solved in a wait-free manner in asynchronous systems where processes communicate
by reading and writing to shared memory. In this work, we consider a natural generalisation
of approximate agreement on arbitrary undirected connected graphs. Each process
is given a node of the graph as input and, if non-faulty, must output a node such
that\r\n– all the outputs are within distance 1 of one another, and\r\n– each
output value lies on a shortest path between two input values.\r\nFrom prior work,
it is known that there is no wait-free algorithm among processes for this problem
on any cycle of length , by reduction from 2-set agreement (Castañeda et al.,
2018).\r\n\r\nIn this work, we investigate the solvability of this task on general
graphs. We give a new, direct proof of the impossibility of approximate agreement
on cycles of length , via a generalisation of Sperner's Lemma to convex polygons.
We also extend the reduction from 2-set agreement to a larger class of graphs,
showing that approximate agreement on these graphs is unsolvable. On the positive
side, we present a wait-free algorithm for a different class of graphs, which
properly contains the class of chordal graphs."
acknowledgement: This project has received funding from the European Research Council
(ERC) under the European Union’s Horizon 2020 research and innovation programme
(grant agreement No. 805223 ScaleML) and under the Marie Skłodowska-Curie grant
agreement No. 840605 and from the Natural Sciences and Engineering Research Council
of Canada grant RGPIN-2020-04178. Part of this work was done while Faith Ellen was
visiting IST Austria.
article_number: '113733'
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
- first_name: Faith
full_name: Ellen, Faith
last_name: Ellen
- first_name: Joel
full_name: Rybicki, Joel
id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
last_name: Rybicki
orcid: 0000-0002-6432-6646
citation:
ama: Alistarh D-A, Ellen F, Rybicki J. Wait-free approximate agreement on graphs.
Theoretical Computer Science. 2023;948(2). doi:10.1016/j.tcs.2023.113733
apa: Alistarh, D.-A., Ellen, F., & Rybicki, J. (2023). Wait-free approximate
agreement on graphs. Theoretical Computer Science. Elsevier. https://doi.org/10.1016/j.tcs.2023.113733
chicago: Alistarh, Dan-Adrian, Faith Ellen, and Joel Rybicki. “Wait-Free Approximate
Agreement on Graphs.” Theoretical Computer Science. Elsevier, 2023. https://doi.org/10.1016/j.tcs.2023.113733.
ieee: D.-A. Alistarh, F. Ellen, and J. Rybicki, “Wait-free approximate agreement
on graphs,” Theoretical Computer Science, vol. 948, no. 2. Elsevier, 2023.
ista: Alistarh D-A, Ellen F, Rybicki J. 2023. Wait-free approximate agreement on
graphs. Theoretical Computer Science. 948(2), 113733.
mla: Alistarh, Dan-Adrian, et al. “Wait-Free Approximate Agreement on Graphs.” Theoretical
Computer Science, vol. 948, no. 2, 113733, Elsevier, 2023, doi:10.1016/j.tcs.2023.113733.
short: D.-A. Alistarh, F. Ellen, J. Rybicki, Theoretical Computer Science 948 (2023).
corr_author: '1'
date_created: 2023-02-19T23:00:55Z
date_published: 2023-02-28T00:00:00Z
date_updated: 2025-04-14T07:49:16Z
day: '28'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.1016/j.tcs.2023.113733
ec_funded: 1
external_id:
isi:
- '000934262700001'
file:
- access_level: open_access
checksum: b27c5290f2f1500c403494364ee39c9f
content_type: application/pdf
creator: dernst
date_created: 2023-02-20T07:30:20Z
date_updated: 2023-02-20T07:30:20Z
file_id: '12570'
file_name: 2023_TheoreticalCompScience_Alistarh.pdf
file_size: 602333
relation: main_file
success: 1
file_date_updated: 2023-02-20T07:30:20Z
has_accepted_license: '1'
intvolume: ' 948'
isi: 1
issue: '2'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '805223'
name: Elastic Coordination for Scalable Machine Learning
- _id: 26A5D39A-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '840605'
name: Coordination in constrained and natural distributed systems
publication: Theoretical Computer Science
publication_identifier:
issn:
- 0304-3975
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Wait-free approximate agreement on graphs
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 948
year: '2023'
...
---
_id: '9647'
abstract:
- lang: eng
text: 'Gene expression is regulated by the set of transcription factors (TFs) that
bind to the promoter. The ensuing regulating function is often represented as
a combinational logic circuit, where output (gene expression) is determined by
current input values (promoter bound TFs) only. However, the simultaneous arrival
of TFs is a strong assumption, since transcription and translation of genes introduce
intrinsic time delays and there is no global synchronisation among the arrival
times of different molecular species at their targets. We present an experimentally
implementable genetic circuit with two inputs and one output, which in the presence
of small delays in input arrival, exhibits qualitatively distinct population-level
phenotypes, over timescales that are longer than typical cell doubling times.
From a dynamical systems point of view, these phenotypes represent long-lived
transients: although they converge to the same value eventually, they do so after
a very long time span. The key feature of this toy model genetic circuit is that,
despite having only two inputs and one output, it is regulated by twenty-three
distinct DNA-TF configurations, two of which are more stable than others (DNA
looped states), one promoting and another blocking the expression of the output
gene. Small delays in input arrival time result in a majority of cells in the
population quickly reaching the stable state associated with the first input,
while exiting of this stable state occurs at a slow timescale. In order to mechanistically
model the behaviour of this genetic circuit, we used a rule-based modelling language,
and implemented a grid-search to find parameter combinations giving rise to long-lived
transients. Our analysis shows that in the absence of feedback, there exist path-dependent
gene regulatory mechanisms based on the long timescale of transients. The behaviour
of this toy model circuit suggests that gene regulatory networks can exploit event
timing to create phenotypes, and it opens the possibility that they could use
event timing to memorise events, without regulatory feedback. The model reveals
the importance of (i) mechanistically modelling the transitions between the different
DNA-TF states, and (ii) employing transient analysis thereof.'
acknowledgement: 'Tatjana Petrov’s research was supported in part by SNSF Advanced
Postdoctoral Mobility Fellowship grant number P300P2 161067, the Ministry of Science,
Research and the Arts of the state of Baden-Wurttemberg, and the DFG Centre of Excellence
2117 ‘Centre for the Advanced Study of Collective Behaviour’ (ID: 422037984). Claudia
Igler is the recipient of a DOC Fellowship of the Austrian Academy of Sciences.
Thomas A. Henzinger’s research was supported in part by the Austrian Science Fund
(FWF) under grant Z211-N23 (Wittgenstein Award).'
article_processing_charge: No
article_type: original
author:
- first_name: Tatjana
full_name: Petrov, Tatjana
last_name: Petrov
- first_name: Claudia
full_name: Igler, Claudia
id: 46613666-F248-11E8-B48F-1D18A9856A87
last_name: Igler
- first_name: Ali
full_name: Sezgin, Ali
id: 4C7638DA-F248-11E8-B48F-1D18A9856A87
last_name: Sezgin
- 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: Calin C
full_name: Guet, Calin C
id: 47F8433E-F248-11E8-B48F-1D18A9856A87
last_name: Guet
orcid: 0000-0001-6220-2052
citation:
ama: Petrov T, Igler C, Sezgin A, Henzinger TA, Guet CC. Long lived transients in
gene regulation. Theoretical Computer Science. 2021;893:1-16. doi:10.1016/j.tcs.2021.05.023
apa: Petrov, T., Igler, C., Sezgin, A., Henzinger, T. A., & Guet, C. C. (2021).
Long lived transients in gene regulation. Theoretical Computer Science.
Elsevier. https://doi.org/10.1016/j.tcs.2021.05.023
chicago: Petrov, Tatjana, Claudia Igler, Ali Sezgin, Thomas A Henzinger, and Calin
C Guet. “Long Lived Transients in Gene Regulation.” Theoretical Computer Science.
Elsevier, 2021. https://doi.org/10.1016/j.tcs.2021.05.023.
ieee: T. Petrov, C. Igler, A. Sezgin, T. A. Henzinger, and C. C. Guet, “Long lived
transients in gene regulation,” Theoretical Computer Science, vol. 893.
Elsevier, pp. 1–16, 2021.
ista: Petrov T, Igler C, Sezgin A, Henzinger TA, Guet CC. 2021. Long lived transients
in gene regulation. Theoretical Computer Science. 893, 1–16.
mla: Petrov, Tatjana, et al. “Long Lived Transients in Gene Regulation.” Theoretical
Computer Science, vol. 893, Elsevier, 2021, pp. 1–16, doi:10.1016/j.tcs.2021.05.023.
short: T. Petrov, C. Igler, A. Sezgin, T.A. Henzinger, C.C. Guet, Theoretical Computer
Science 893 (2021) 1–16.
corr_author: '1'
date_created: 2021-07-11T22:01:18Z
date_published: 2021-06-04T00:00:00Z
date_updated: 2025-04-15T06:25:56Z
day: '04'
ddc:
- '004'
department:
- _id: ToHe
- _id: CaGu
doi: 10.1016/j.tcs.2021.05.023
external_id:
isi:
- '000710180500002'
file:
- access_level: open_access
checksum: d3aef34cfb13e53bba4cf44d01680793
content_type: application/pdf
creator: dernst
date_created: 2022-05-12T12:13:27Z
date_updated: 2022-05-12T12:13:27Z
file_id: '11364'
file_name: 2021_TheoreticalComputerScience_Petrov.pdf
file_size: 2566504
relation: main_file
success: 1
file_date_updated: 2022-05-12T12:13:27Z
has_accepted_license: '1'
intvolume: ' 893'
isi: 1
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 1-16
project:
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: Formal methods for the design and analysis of complex systems
publication: Theoretical Computer Science
publication_identifier:
issn:
- 0304-3975
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Long lived transients in gene regulation
tmp:
image: /images/cc_by_nc_nd.png
legal_code_url: https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode
name: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
(CC BY-NC-ND 4.0)
short: CC BY-NC-ND (4.0)
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 893
year: '2021'
...
---
_id: '9827'
abstract:
- lang: eng
text: 'The Nearest neighbour search (NNS) is a fundamental problem in many application
domains dealing with multidimensional data. In a concurrent setting, where dynamic
modifications are allowed, a linearizable implementation of the NNS is highly
desirable.This paper introduces the LockFree-kD-tree (LFkD-tree ): a lock-free
concurrent kD-tree, which implements an abstract data type (ADT) that provides
the operations Add, Remove, Contains, and NNS. Our implementation is linearizable.
The operations in the LFkD-tree use single-word read and compare-and-swap (Image
1 ) atomic primitives, which are readily supported on available multi-core processors.
We experimentally evaluate the LFkD-tree using several benchmarks comprising real-world
and synthetic datasets. The experiments show that the presented design is scalable
and achieves significant speed-up compared to the implementations of an existing
sequential kD-tree and a recently proposed multidimensional indexing structure,
PH-tree.'
article_processing_charge: No
article_type: original
author:
- first_name: Bapi
full_name: Chatterjee, Bapi
id: 3C41A08A-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-2742-4028
- first_name: Ivan
full_name: Walulya, Ivan
last_name: Walulya
- first_name: Philippas
full_name: Tsigas, Philippas
last_name: Tsigas
citation:
ama: Chatterjee B, Walulya I, Tsigas P. Concurrent linearizable nearest neighbour
search in LockFree-kD-tree. Theoretical Computer Science. 2021;886:27-48.
doi:10.1016/j.tcs.2021.06.041
apa: Chatterjee, B., Walulya, I., & Tsigas, P. (2021). Concurrent linearizable
nearest neighbour search in LockFree-kD-tree. Theoretical Computer Science.
Elsevier. https://doi.org/10.1016/j.tcs.2021.06.041
chicago: Chatterjee, Bapi, Ivan Walulya, and Philippas Tsigas. “Concurrent Linearizable
Nearest Neighbour Search in LockFree-KD-Tree.” Theoretical Computer Science.
Elsevier, 2021. https://doi.org/10.1016/j.tcs.2021.06.041.
ieee: B. Chatterjee, I. Walulya, and P. Tsigas, “Concurrent linearizable nearest
neighbour search in LockFree-kD-tree,” Theoretical Computer Science, vol.
886. Elsevier, pp. 27–48, 2021.
ista: Chatterjee B, Walulya I, Tsigas P. 2021. Concurrent linearizable nearest neighbour
search in LockFree-kD-tree. Theoretical Computer Science. 886, 27–48.
mla: Chatterjee, Bapi, et al. “Concurrent Linearizable Nearest Neighbour Search
in LockFree-KD-Tree.” Theoretical Computer Science, vol. 886, Elsevier,
2021, pp. 27–48, doi:10.1016/j.tcs.2021.06.041.
short: B. Chatterjee, I. Walulya, P. Tsigas, Theoretical Computer Science 886 (2021)
27–48.
corr_author: '1'
date_created: 2021-08-08T22:01:31Z
date_published: 2021-09-13T00:00:00Z
date_updated: 2024-10-09T21:00:45Z
day: '13'
department:
- _id: DaAl
doi: 10.1016/j.tcs.2021.06.041
external_id:
isi:
- '000694718900004'
intvolume: ' 886'
isi: 1
keyword:
- Concurrent data structure
- kD-tree
- Nearest neighbor search
- Similarity search
- Lock-free
- Linearizability
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://publications.lib.chalmers.se/records/fulltext/232185/232185.pdf
month: '09'
oa: 1
oa_version: Submitted Version
page: 27-48
publication: Theoretical Computer Science
publication_identifier:
issn:
- 0304-3975
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Concurrent linearizable nearest neighbour search in LockFree-kD-tree
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 886
year: '2021'
...
---
_id: '6761'
abstract:
- lang: eng
text: In resource allocation games, selfish players share resources that are needed
in order to fulfill their objectives. The cost of using a resource depends on
the load on it. In the traditional setting, the players make their choices concurrently
and in one-shot. That is, a strategy for a player is a subset of the resources.
We introduce and study dynamic resource allocation games. In this setting, the
game proceeds in phases. In each phase each player chooses one resource. A scheduler
dictates the order in which the players proceed in a phase, possibly scheduling
several players to proceed concurrently. The game ends when each player has collected
a set of resources that fulfills his objective. The cost for each player then
depends on this set as well as on the load on the resources in it – we consider
both congestion and cost-sharing games. We argue that the dynamic setting is the
suitable setting for many applications in practice. We study the stability of
dynamic resource allocation games, where the appropriate notion of stability is
that of subgame perfect equilibrium, study the inefficiency incurred due to selfish
behavior, and also study problems that are particular to the dynamic setting,
like constraints on the order in which resources can be chosen or the problem
of finding a scheduler that achieves stability.
article_processing_charge: No
article_type: original
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: Orna
full_name: Kupferman, Orna
last_name: Kupferman
citation:
ama: Avni G, Henzinger TA, Kupferman O. Dynamic resource allocation games. Theoretical
Computer Science. 2020;807:42-55. doi:10.1016/j.tcs.2019.06.031
apa: Avni, G., Henzinger, T. A., & Kupferman, O. (2020). Dynamic resource allocation
games. Theoretical Computer Science. Elsevier. https://doi.org/10.1016/j.tcs.2019.06.031
chicago: Avni, Guy, Thomas A Henzinger, and Orna Kupferman. “Dynamic Resource Allocation
Games.” Theoretical Computer Science. Elsevier, 2020. https://doi.org/10.1016/j.tcs.2019.06.031.
ieee: G. Avni, T. A. Henzinger, and O. Kupferman, “Dynamic resource allocation games,”
Theoretical Computer Science, vol. 807. Elsevier, pp. 42–55, 2020.
ista: Avni G, Henzinger TA, Kupferman O. 2020. Dynamic resource allocation games.
Theoretical Computer Science. 807, 42–55.
mla: Avni, Guy, et al. “Dynamic Resource Allocation Games.” Theoretical Computer
Science, vol. 807, Elsevier, 2020, pp. 42–55, doi:10.1016/j.tcs.2019.06.031.
short: G. Avni, T.A. Henzinger, O. Kupferman, Theoretical Computer Science 807 (2020)
42–55.
date_created: 2019-08-04T21:59:20Z
date_published: 2020-02-06T00:00:00Z
date_updated: 2026-04-16T09:35:15Z
day: '06'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.1016/j.tcs.2019.06.031
external_id:
isi:
- '000512219400004'
file:
- access_level: open_access
checksum: e86635417f45eb2cd75778f91382f737
content_type: application/pdf
creator: dernst
date_created: 2020-10-09T06:31:22Z
date_updated: 2020-10-09T06:31:22Z
file_id: '8639'
file_name: 2020_TheoreticalCS_Avni.pdf
file_size: 1413001
relation: main_file
success: 1
file_date_updated: 2020-10-09T06:31:22Z
has_accepted_license: '1'
intvolume: ' 807'
isi: 1
language:
- iso: eng
month: '02'
oa: 1
oa_version: Submitted Version
page: 42-55
project:
- _id: 25F2ACDE-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11402-N23
name: Rigorous Systems Engineering
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: Formal methods for the design and analysis of complex systems
- _id: 264B3912-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: M02369
name: Formal Methods meets Algorithmic Game Theory
publication: Theoretical Computer Science
publication_identifier:
issn:
- 0304-3975
publication_status: published
publisher: Elsevier
quality_controlled: '1'
related_material:
record:
- id: '1341'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Dynamic resource allocation games
type: journal_article
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 807
year: '2020'
...
---
_id: '11898'
abstract:
- lang: eng
text: "We build upon the recent papers by Weinstein and Yu (FOCS'16), Larsen (FOCS'12),
and Clifford et al. (FOCS'15) to present a general framework that gives amortized
lower bounds on the update and query times of dynamic data structures. Using our
framework, we present two concrete results.\r\n(1) For the dynamic polynomial
evaluation problem, where the polynomial is defined over a finite field of size
n1+Ω(1) and has degree n, any dynamic data structure must either have an amortized
update time of Ω((lgn/lglgn)2) or an amortized query time of Ω((lgn/lglgn)2).\r\n(2)
For the dynamic online matrix vector multiplication problem, where we get an n×n
matrix whose entires are drawn from a finite field of size nΘ(1), any dynamic
data structure must either have an amortized update time of Ω((lgn/lglgn)2) or
an amortized query time of Ω(n⋅(lgn/lglgn)2).\r\nFor these two problems, the previous
works by Larsen (FOCS'12) and Clifford et al. (FOCS'15) gave the same lower bounds,
but only for worst case update and query times. Our bounds match the highest unconditional
lower bounds known till date for any dynamic problem in the cell-probe model."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Sayan
full_name: Bhattacharya, Sayan
last_name: Bhattacharya
- 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: Stefan
full_name: Neumann, Stefan
last_name: Neumann
citation:
ama: Bhattacharya S, Henzinger M, Neumann S. New amortized cell-probe lower bounds
for dynamic problems. Theoretical Computer Science. 2019;779:72-87. doi:10.1016/j.tcs.2019.01.043
apa: Bhattacharya, S., Henzinger, M., & Neumann, S. (2019). New amortized cell-probe
lower bounds for dynamic problems. Theoretical Computer Science. Elsevier.
https://doi.org/10.1016/j.tcs.2019.01.043
chicago: Bhattacharya, Sayan, Monika Henzinger, and Stefan Neumann. “New Amortized
Cell-Probe Lower Bounds for Dynamic Problems.” Theoretical Computer Science.
Elsevier, 2019. https://doi.org/10.1016/j.tcs.2019.01.043.
ieee: S. Bhattacharya, M. Henzinger, and S. Neumann, “New amortized cell-probe lower
bounds for dynamic problems,” Theoretical Computer Science, vol. 779. Elsevier,
pp. 72–87, 2019.
ista: Bhattacharya S, Henzinger M, Neumann S. 2019. New amortized cell-probe lower
bounds for dynamic problems. Theoretical Computer Science. 779, 72–87.
mla: Bhattacharya, Sayan, et al. “New Amortized Cell-Probe Lower Bounds for Dynamic
Problems.” Theoretical Computer Science, vol. 779, Elsevier, 2019, pp.
72–87, doi:10.1016/j.tcs.2019.01.043.
short: S. Bhattacharya, M. Henzinger, S. Neumann, Theoretical Computer Science 779
(2019) 72–87.
date_created: 2022-08-17T09:02:15Z
date_published: 2019-08-02T00:00:00Z
date_updated: 2024-11-06T12:23:49Z
day: '02'
doi: 10.1016/j.tcs.2019.01.043
extern: '1'
external_id:
arxiv:
- '1902.02304'
intvolume: ' 779'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1902.02304
month: '08'
oa: 1
oa_version: Preprint
page: 72-87
publication: Theoretical Computer Science
publication_identifier:
issn:
- 0304-3975
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: New amortized cell-probe lower bounds for dynamic problems
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 779
year: '2019'
...
---
_id: '11901'
abstract:
- lang: eng
text: We consider auctions of indivisible items to unit-demand bidders with budgets.
This setting was suggested as an expressive model for single sponsored search
auctions. Prior work presented mechanisms that compute bidder-optimal outcomes
and are truthful for a restricted set of inputs, i.e., inputs in so-called general
position. This condition is easily violated. We provide the first mechanism that
is truthful in expectation for all inputs and achieves for each bidder no worse
utility than the bidder-optimal outcome. Additionally we give a complete characterization
for which inputs mechanisms that compute bidder-optimal outcomes are truthful.
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: Veronika
full_name: Loitzenbauer, Veronika
last_name: Loitzenbauer
citation:
ama: Henzinger M, Loitzenbauer V. Truthful unit-demand auctions with budgets revisited.
Theoretical Computer Science. 2015;573:1-15. doi:10.1016/j.tcs.2015.01.033
apa: Henzinger, M., & Loitzenbauer, V. (2015). Truthful unit-demand auctions
with budgets revisited. Theoretical Computer Science. Elsevier. https://doi.org/10.1016/j.tcs.2015.01.033
chicago: Henzinger, Monika, and Veronika Loitzenbauer. “Truthful Unit-Demand Auctions
with Budgets Revisited.” Theoretical Computer Science. Elsevier, 2015.
https://doi.org/10.1016/j.tcs.2015.01.033.
ieee: M. Henzinger and V. Loitzenbauer, “Truthful unit-demand auctions with budgets
revisited,” Theoretical Computer Science, vol. 573. Elsevier, pp. 1–15,
2015.
ista: Henzinger M, Loitzenbauer V. 2015. Truthful unit-demand auctions with budgets
revisited. Theoretical Computer Science. 573, 1–15.
mla: Henzinger, Monika, and Veronika Loitzenbauer. “Truthful Unit-Demand Auctions
with Budgets Revisited.” Theoretical Computer Science, vol. 573, Elsevier,
2015, pp. 1–15, doi:10.1016/j.tcs.2015.01.033.
short: M. Henzinger, V. Loitzenbauer, Theoretical Computer Science 573 (2015) 1–15.
date_created: 2022-08-17T09:06:53Z
date_published: 2015-03-30T00:00:00Z
date_updated: 2024-11-06T12:24:01Z
day: '30'
doi: 10.1016/j.tcs.2015.01.033
extern: '1'
intvolume: ' 573'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1016/j.tcs.2015.01.033
month: '03'
oa: 1
oa_version: None
page: 1-15
publication: Theoretical Computer Science
publication_identifier:
issn:
- 0304-3975
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Truthful unit-demand auctions with budgets revisited
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 573
year: '2015'
...
---
_id: '5804'
abstract:
- lang: eng
text: We present here the first integer-based algorithm for constructing a well-defined
lattice sphere specified by integer radius and integer center. The algorithm evolves
from a unique correspondence between the lattice points comprising the sphere
and the distribution of sum of three square numbers in integer intervals. We characterize
these intervals to derive a useful set of recurrences, which, in turn, aids in
efficient computation. Each point of the lattice sphere is determined by resorting
to only a few primitive operations in the integer domain. The symmetry of its
quadraginta octants provides an added advantage by confining the computation to
its prima quadraginta octant. Detailed theoretical analysis and experimental results
have been furnished to demonstrate its simplicity and elegance.
author:
- first_name: Ranita
full_name: Biswas, Ranita
id: 3C2B033E-F248-11E8-B48F-1D18A9856A87
last_name: Biswas
orcid: 0000-0002-5372-7890
- first_name: Partha
full_name: Bhowmick, Partha
last_name: Bhowmick
citation:
ama: Biswas R, Bhowmick P. From prima quadraginta octant to lattice sphere through
primitive integer operations. Theoretical Computer Science. 2015;624(4):56-72.
doi:10.1016/j.tcs.2015.11.018
apa: Biswas, R., & Bhowmick, P. (2015). From prima quadraginta octant to lattice
sphere through primitive integer operations. Theoretical Computer Science.
Elsevier. https://doi.org/10.1016/j.tcs.2015.11.018
chicago: Biswas, Ranita, and Partha Bhowmick. “From Prima Quadraginta Octant to
Lattice Sphere through Primitive Integer Operations.” Theoretical Computer
Science. Elsevier, 2015. https://doi.org/10.1016/j.tcs.2015.11.018.
ieee: R. Biswas and P. Bhowmick, “From prima quadraginta octant to lattice sphere
through primitive integer operations,” Theoretical Computer Science, vol.
624, no. 4. Elsevier, pp. 56–72, 2015.
ista: Biswas R, Bhowmick P. 2015. From prima quadraginta octant to lattice sphere
through primitive integer operations. Theoretical Computer Science. 624(4), 56–72.
mla: Biswas, Ranita, and Partha Bhowmick. “From Prima Quadraginta Octant to Lattice
Sphere through Primitive Integer Operations.” Theoretical Computer Science,
vol. 624, no. 4, Elsevier, 2015, pp. 56–72, doi:10.1016/j.tcs.2015.11.018.
short: R. Biswas, P. Bhowmick, Theoretical Computer Science 624 (2015) 56–72.
date_created: 2019-01-08T20:44:06Z
date_published: 2015-04-18T00:00:00Z
date_updated: 2021-01-12T08:03:36Z
day: '18'
doi: 10.1016/j.tcs.2015.11.018
extern: '1'
intvolume: ' 624'
issue: '4'
language:
- iso: eng
month: '04'
oa_version: None
page: 56-72
publication: Theoretical Computer Science
publication_identifier:
issn:
- 0304-3975
publication_status: published
publisher: Elsevier
quality_controlled: '1'
status: public
title: From prima quadraginta octant to lattice sphere through primitive integer operations
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 624
year: '2015'
...
---
_id: '5807'
author:
- first_name: Ranita
full_name: Biswas, Ranita
id: 3C2B033E-F248-11E8-B48F-1D18A9856A87
last_name: Biswas
orcid: 0000-0002-5372-7890
- first_name: Partha
full_name: Bhowmick, Partha
last_name: Bhowmick
citation:
ama: Biswas R, Bhowmick P. On different topological classes of spherical geodesic
paths and circles inZ3. Theoretical Computer Science. 2015;605(11):146-163.
doi:10.1016/j.tcs.2015.09.003
apa: Biswas, R., & Bhowmick, P. (2015). On different topological classes of
spherical geodesic paths and circles inZ3. Theoretical Computer Science.
Elsevier. https://doi.org/10.1016/j.tcs.2015.09.003
chicago: Biswas, Ranita, and Partha Bhowmick. “On Different Topological Classes
of Spherical Geodesic Paths and Circles InZ3.” Theoretical Computer Science.
Elsevier, 2015. https://doi.org/10.1016/j.tcs.2015.09.003.
ieee: R. Biswas and P. Bhowmick, “On different topological classes of spherical
geodesic paths and circles inZ3,” Theoretical Computer Science, vol. 605,
no. 11. Elsevier, pp. 146–163, 2015.
ista: Biswas R, Bhowmick P. 2015. On different topological classes of spherical
geodesic paths and circles inZ3. Theoretical Computer Science. 605(11), 146–163.
mla: Biswas, Ranita, and Partha Bhowmick. “On Different Topological Classes of Spherical
Geodesic Paths and Circles InZ3.” Theoretical Computer Science, vol. 605,
no. 11, Elsevier, 2015, pp. 146–63, doi:10.1016/j.tcs.2015.09.003.
short: R. Biswas, P. Bhowmick, Theoretical Computer Science 605 (2015) 146–163.
date_created: 2019-01-08T20:44:52Z
date_published: 2015-11-09T00:00:00Z
date_updated: 2021-01-12T08:03:37Z
day: '09'
doi: 10.1016/j.tcs.2015.09.003
extern: '1'
intvolume: ' 605'
issue: '11'
language:
- iso: eng
month: '11'
oa_version: None
page: 146-163
publication: Theoretical Computer Science
publication_identifier:
issn:
- 0304-3975
publication_status: published
publisher: Elsevier
quality_controlled: '1'
status: public
title: On different topological classes of spherical geodesic paths and circles inZ3
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 605
year: '2015'
...
---
_id: '2246'
abstract:
- lang: eng
text: 'Muller games are played by two players moving a token along a graph; the
winner is determined by the set of vertices that occur infinitely often. The central
algorithmic problem is to compute the winning regions for the players. Different
classes and representations of Muller games lead to problems of varying computational
complexity. One such class are parity games; these are of particular significance
in computational complexity, as they remain one of the few combinatorial problems
known to be in NP ∩ co-NP but not known to be in P. We show that winning regions
for a Muller game can be determined from the alternating structure of its traps.
To every Muller game we then associate a natural number that we call its trap
depth; this parameter measures how complicated the trap structure is. We present
algorithms for parity games that run in polynomial time for graphs of bounded
trap depth, and in general run in time exponential in the trap depth. '
article_processing_charge: No
arxiv: 1
author:
- first_name: Andrey
full_name: Grinshpun, Andrey
last_name: Grinshpun
- first_name: Pakawat
full_name: Phalitnonkiat, Pakawat
last_name: Phalitnonkiat
- first_name: Sasha
full_name: Rubin, Sasha
id: 2EC51194-F248-11E8-B48F-1D18A9856A87
last_name: Rubin
- first_name: Andrei
full_name: Tarfulea, Andrei
last_name: Tarfulea
citation:
ama: Grinshpun A, Phalitnonkiat P, Rubin S, Tarfulea A. Alternating traps in Muller
and parity games. Theoretical Computer Science. 2014;521:73-91. doi:10.1016/j.tcs.2013.11.032
apa: Grinshpun, A., Phalitnonkiat, P., Rubin, S., & Tarfulea, A. (2014). Alternating
traps in Muller and parity games. Theoretical Computer Science. Elsevier.
https://doi.org/10.1016/j.tcs.2013.11.032
chicago: Grinshpun, Andrey, Pakawat Phalitnonkiat, Sasha Rubin, and Andrei Tarfulea.
“Alternating Traps in Muller and Parity Games.” Theoretical Computer Science.
Elsevier, 2014. https://doi.org/10.1016/j.tcs.2013.11.032.
ieee: A. Grinshpun, P. Phalitnonkiat, S. Rubin, and A. Tarfulea, “Alternating traps
in Muller and parity games,” Theoretical Computer Science, vol. 521. Elsevier,
pp. 73–91, 2014.
ista: Grinshpun A, Phalitnonkiat P, Rubin S, Tarfulea A. 2014. Alternating traps
in Muller and parity games. Theoretical Computer Science. 521, 73–91.
mla: Grinshpun, Andrey, et al. “Alternating Traps in Muller and Parity Games.” Theoretical
Computer Science, vol. 521, Elsevier, 2014, pp. 73–91, doi:10.1016/j.tcs.2013.11.032.
short: A. Grinshpun, P. Phalitnonkiat, S. Rubin, A. Tarfulea, Theoretical Computer
Science 521 (2014) 73–91.
corr_author: '1'
date_created: 2018-12-11T11:56:33Z
date_published: 2014-02-13T00:00:00Z
date_updated: 2026-04-16T10:08:15Z
day: '13'
department:
- _id: KrCh
doi: 10.1016/j.tcs.2013.11.032
external_id:
arxiv:
- '1303.3777'
isi:
- '000331433100007'
intvolume: ' 521'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1303.3777
month: '02'
oa: 1
oa_version: Submitted Version
page: 73 - 91
publication: Theoretical Computer Science
publication_identifier:
issn:
- 0304-3975
publication_status: published
publisher: Elsevier
publist_id: '4703'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Alternating traps in Muller and parity games
type: journal_article
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 521
year: '2014'
...
---
_id: '11902'
abstract:
- lang: eng
text: "We study the problem of matching bidders to items where each bidder i has
general, strictly monotonic utility functions ui,j(pj) expressing his utility
of being matched to item j at price pj. For this setting we prove that a bidder
optimal outcome always exists, even when the utility functions are non-linear
and non-continuous. We give sufficient conditions under\r\nwhich every mechanism
that finds a bidder optimal outcome is incentive compatible. We also give a mechanism
that finds a bidder optimal outcome if the conditions for incentive compatibility
are satisfied. The running time of this mechanism is exponential in the number
of items, but polynomial in the number of bidders."
article_processing_charge: No
article_type: original
author:
- first_name: Paul
full_name: Dütting, Paul
last_name: Dütting
- 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: Ingmar
full_name: Weber, Ingmar
last_name: Weber
citation:
ama: Dütting P, Henzinger M, Weber I. Bidder optimal assignments for general utilities.
Theoretical Computer Science. 2013;478(3):22-32. doi:10.1016/j.tcs.2013.01.030
apa: Dütting, P., Henzinger, M., & Weber, I. (2013). Bidder optimal assignments
for general utilities. Theoretical Computer Science. Elsevier. https://doi.org/10.1016/j.tcs.2013.01.030
chicago: Dütting, Paul, Monika Henzinger, and Ingmar Weber. “Bidder Optimal Assignments
for General Utilities.” Theoretical Computer Science. Elsevier, 2013. https://doi.org/10.1016/j.tcs.2013.01.030.
ieee: P. Dütting, M. Henzinger, and I. Weber, “Bidder optimal assignments for general
utilities,” Theoretical Computer Science, vol. 478, no. 3. Elsevier, pp.
22–32, 2013.
ista: Dütting P, Henzinger M, Weber I. 2013. Bidder optimal assignments for general
utilities. Theoretical Computer Science. 478(3), 22–32.
mla: Dütting, Paul, et al. “Bidder Optimal Assignments for General Utilities.” Theoretical
Computer Science, vol. 478, no. 3, Elsevier, 2013, pp. 22–32, doi:10.1016/j.tcs.2013.01.030.
short: P. Dütting, M. Henzinger, I. Weber, Theoretical Computer Science 478 (2013)
22–32.
date_created: 2022-08-17T11:11:04Z
date_published: 2013-03-25T00:00:00Z
date_updated: 2024-11-06T12:24:12Z
day: '25'
doi: 10.1016/j.tcs.2013.01.030
extern: '1'
intvolume: ' 478'
issue: '3'
language:
- iso: eng
month: '03'
oa_version: None
page: 22-32
publication: Theoretical Computer Science
publication_identifier:
issn:
- 0304-3975
publication_status: published
publisher: Elsevier
quality_controlled: '1'
related_material:
record:
- id: '11799'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Bidder optimal assignments for general utilities
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 478
year: '2013'
...
---
_id: '4407'
abstract:
- lang: eng
text: 'This paper presents a complete axiomatization of two decidable propositional
real-time linear temporal logics: Event Clock Logic (EventClockTL) and Metric
Interval Temporal Logic with past (MetricIntervalTL). The completeness proof consists
of an effective proof building procedure for EventClockTL. From this result we
obtain a complete axiomatization of MetricIntervalTL by providing axioms translating
MetricIntervalTL formulae into EventClockTL formulae, the two logics being equally
expressive. Our proof is structured to yield axiomatizations also for interesting
fragments of these logics, such as the linear temporal logic of the real numbers
(TLR).'
article_processing_charge: No
article_type: original
author:
- first_name: Jean
full_name: Raskin, Jean
last_name: Raskin
- first_name: Pierre
full_name: Schobbens, Pierre
last_name: Schobbens
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
citation:
ama: Raskin J, Schobbens P, Henzinger TA. Axioms for real-time logics. Theoretical
Computer Science. 2002;274(1-2):151-182. doi:10.1016/S0304-3975(00)00308-X
apa: Raskin, J., Schobbens, P., & Henzinger, T. A. (2002). Axioms for real-time
logics. Theoretical Computer Science. Elsevier. https://doi.org/10.1016/S0304-3975(00)00308-X
chicago: Raskin, Jean, Pierre Schobbens, and Thomas A Henzinger. “Axioms for Real-Time
Logics.” Theoretical Computer Science. Elsevier, 2002. https://doi.org/10.1016/S0304-3975(00)00308-X.
ieee: J. Raskin, P. Schobbens, and T. A. Henzinger, “Axioms for real-time logics,”
Theoretical Computer Science, vol. 274, no. 1–2. Elsevier, pp. 151–182,
2002.
ista: Raskin J, Schobbens P, Henzinger TA. 2002. Axioms for real-time logics. Theoretical
Computer Science. 274(1–2), 151–182.
mla: Raskin, Jean, et al. “Axioms for Real-Time Logics.” Theoretical Computer
Science, vol. 274, no. 1–2, Elsevier, 2002, pp. 151–82, doi:10.1016/S0304-3975(00)00308-X.
short: J. Raskin, P. Schobbens, T.A. Henzinger, Theoretical Computer Science 274
(2002) 151–182.
date_created: 2018-12-11T12:08:42Z
date_published: 2002-03-01T00:00:00Z
date_updated: 2023-06-06T09:10:56Z
day: '01'
doi: 10.1016/S0304-3975(00)00308-X
extern: '1'
intvolume: ' 274'
issue: 1-2
language:
- iso: eng
month: '03'
oa_version: None
page: 151 - 182
publication: Theoretical Computer Science
publication_identifier:
issn:
- 0304-3975
publication_status: published
publisher: Elsevier
publist_id: '324'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Axioms for real-time logics
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 274
year: '2002'
...
---
_id: '4442'
abstract:
- lang: eng
text: Rectangular hybrid automata model digital control programs of analog plant
environments. We study rectangular hybrid automata where the plant state evolves
continuously in real-numbered time, and the controller samples the plant state
and changes the control state discretely, only at the integer points in time.
We prove that rectangular hybrid automata have finite bisimilarity quotients when
all control transitions happen at integer times, even if the constraints on the
derivatives of the variables vary between control states. This is in contrast
with the conventional model where control transitions may happen at any real time,
and already the reachability problem is undecidable. Based on the finite bisimilarity
quotients, we give an exponential algorithm for the symbolic sampling-controller
synthesis of rectangular automata. We show our algorithm to be optimal by proving
the problem to be EXPTIME-hard. We also show that rectangular automata form a
maximal class of systems for which the sampling-controller synthesis problem can
be solved algorithmically.
article_processing_charge: No
article_type: original
author:
- 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: Peter
full_name: Kopke, Peter
last_name: Kopke
citation:
ama: Henzinger TA, Kopke P. Discrete-time control for rectangular hybrid automata.
Theoretical Computer Science. 1999;221(1-2):369-392. doi:10.1016/S0304-3975(99)00038-9
apa: Henzinger, T. A., & Kopke, P. (1999). Discrete-time control for rectangular
hybrid automata. Theoretical Computer Science. Elsevier. https://doi.org/10.1016/S0304-3975(99)00038-9
chicago: Henzinger, Thomas A, and Peter Kopke. “Discrete-Time Control for Rectangular
Hybrid Automata.” Theoretical Computer Science. Elsevier, 1999. https://doi.org/10.1016/S0304-3975(99)00038-9.
ieee: T. A. Henzinger and P. Kopke, “Discrete-time control for rectangular hybrid
automata,” Theoretical Computer Science, vol. 221, no. 1–2. Elsevier, pp.
369–392, 1999.
ista: Henzinger TA, Kopke P. 1999. Discrete-time control for rectangular hybrid
automata. Theoretical Computer Science. 221(1–2), 369–392.
mla: Henzinger, Thomas A., and Peter Kopke. “Discrete-Time Control for Rectangular
Hybrid Automata.” Theoretical Computer Science, vol. 221, no. 1–2, Elsevier,
1999, pp. 369–92, doi:10.1016/S0304-3975(99)00038-9.
short: T.A. Henzinger, P. Kopke, Theoretical Computer Science 221 (1999) 369–392.
date_created: 2018-12-11T12:08:52Z
date_published: 1999-01-01T00:00:00Z
date_updated: 2022-09-06T08:03:48Z
day: '01'
doi: 10.1016/S0304-3975(99)00038-9
extern: '1'
intvolume: ' 221'
issue: 1-2
language:
- iso: eng
month: '01'
oa_version: None
page: 369 - 392
publication: Theoretical Computer Science
publication_identifier:
issn:
- 0304-3975
publication_status: published
publisher: Elsevier
publist_id: '290'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Discrete-time control for rectangular hybrid automata
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 221
year: '1999'
...
---
_id: '4613'
abstract:
- lang: eng
text: We present a general framework for the formal specification and algorithmic
analysis of hybrid systems. A hybrid system consists of a discrete program with
an analog environment. We model hybrid systems as finite automata equipped with
variables that evolve continuously with time according to dynamical laws. For
verification purposes, we restrict ourselves to linear hybrid systems, where all
variables follow piecewise-linear trajectories. We provide decidability and undecidability
results for classes of linear hybrid systems, and we show that standard program-analysis
techniques can be adapted to linear hybrid systems. In particular, we consider
symbolic model-checking and minimization procedures that are based on the reachability
analysis of an infinite state space. The procedures iteratively compute state
sets that are definable as unions of convex polyhedra in multidimensional real
space. We also present approximation techniques for dealing with systems for which
the iterative procedures do not converge.
article_processing_charge: No
article_type: original
author:
- first_name: Rajeev
full_name: Alur, Rajeev
last_name: Alur
- first_name: Costas
full_name: Courcoubetis, Costas
last_name: Courcoubetis
- first_name: Nicolas
full_name: Halbwachs, Nicolas
last_name: Halbwachs
- 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: Pei
full_name: Ho, Pei
last_name: Ho
- first_name: Xavier
full_name: Nicollin, Xavier
last_name: Nicollin
- first_name: Alfredo
full_name: Olivero, Alfredo
last_name: Olivero
- first_name: Joseph
full_name: Sifakis, Joseph
last_name: Sifakis
- first_name: Sergio
full_name: Yovine, Sergio
last_name: Yovine
citation:
ama: Alur R, Courcoubetis C, Halbwachs N, et al. The algorithmic analysis of hybrid
systems. Theoretical Computer Science. 1995;138(1):3-34. doi:10.1016/0304-3975(94)00202-T
apa: Alur, R., Courcoubetis, C., Halbwachs, N., Henzinger, T. A., Ho, P., Nicollin,
X., … Yovine, S. (1995). The algorithmic analysis of hybrid systems. Theoretical
Computer Science. Elsevier. https://doi.org/10.1016/0304-3975(94)00202-T
chicago: Alur, Rajeev, Costas Courcoubetis, Nicolas Halbwachs, Thomas A Henzinger,
Pei Ho, Xavier Nicollin, Alfredo Olivero, Joseph Sifakis, and Sergio Yovine. “The
Algorithmic Analysis of Hybrid Systems.” Theoretical Computer Science.
Elsevier, 1995. https://doi.org/10.1016/0304-3975(94)00202-T.
ieee: R. Alur et al., “The algorithmic analysis of hybrid systems,” Theoretical
Computer Science, vol. 138, no. 1. Elsevier, pp. 3–34, 1995.
ista: Alur R, Courcoubetis C, Halbwachs N, Henzinger TA, Ho P, Nicollin X, Olivero
A, Sifakis J, Yovine S. 1995. The algorithmic analysis of hybrid systems. Theoretical
Computer Science. 138(1), 3–34.
mla: Alur, Rajeev, et al. “The Algorithmic Analysis of Hybrid Systems.” Theoretical
Computer Science, vol. 138, no. 1, Elsevier, 1995, pp. 3–34, doi:10.1016/0304-3975(94)00202-T.
short: R. Alur, C. Courcoubetis, N. Halbwachs, T.A. Henzinger, P. Ho, X. Nicollin,
A. Olivero, J. Sifakis, S. Yovine, Theoretical Computer Science 138 (1995) 3–34.
date_created: 2018-12-11T12:09:45Z
date_published: 1995-02-06T00:00:00Z
date_updated: 2022-06-09T13:40:48Z
day: '06'
doi: 10.1016/0304-3975(94)00202-T
extern: '1'
intvolume: ' 138'
issue: '1'
language:
- iso: eng
main_file_link:
- url: https://www.sciencedirect.com/science/article/pii/030439759400202T?via%3Dihub
month: '02'
oa_version: None
page: 3 - 34
publication: Theoretical Computer Science
publication_identifier:
issn:
- 0304-3975
publication_status: published
publisher: Elsevier
publist_id: '94'
quality_controlled: '1'
status: public
title: The algorithmic analysis of hybrid systems
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 138
year: '1995'
...
---
_id: '4047'
abstract:
- lang: eng
text: Arrangements of curves in the plane are fundamental to many problems in computational
and combinatorial geometry (e.g. motion planning, algebraic cell decomposition,
etc.). In this paper we study various topological and combinatorial properties
of such arrangements under some mild assumptions on the shape of the curves, and
develop basic tools for the construction, manipulation, and analysis of these
arrangements. Our main results include a generalization of the zone theorem of
Edelsbrunner (1986) and Chazelle (1985) to arrangements of curves (in which we
show that the combinatorial complexity of the zone of a curve is nearly linear
in the number of curves) and an application of that theorem to obtain a nearly
quadratic incremental algorithm for the construction of such arrangements.
acknowledgement: 'Work on this paper by the first author has been supported by the
National Science Foundation under grant CCR-8714565. Work by the third and sixth
authors has been supported by Office of Naval Research Grant NOOOl4-82-K-0381, by
National Science Foundation Grant No. NSF-DCR-83-20085, by grants from the Digital
Equipment Corporation, and the IBM Corporation. Work by the sixth author has also
been supported by a research grant from the NCRD- the Israeli National Council for
Research and Development. Work by the fourth author has been supported by National
Science Foundation Grant DMS-8501947. '
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
- first_name: János
full_name: Pach, János
last_name: Pach
- first_name: Richard
full_name: Pollack, Richard
last_name: Pollack
- first_name: Raimund
full_name: Seidel, Raimund
last_name: Seidel
- first_name: Micha
full_name: Sharir, Micha
last_name: Sharir
citation:
ama: Edelsbrunner H, Guibas L, Pach J, Pollack R, Seidel R, Sharir M. Arrangements
of curves in the plane - topology, combinatorics, and algorithms. Theoretical
Computer Science. 1992;92(2):319-336. doi:10.1016/0304-3975(92)90319-B
apa: Edelsbrunner, H., Guibas, L., Pach, J., Pollack, R., Seidel, R., & Sharir,
M. (1992). Arrangements of curves in the plane - topology, combinatorics, and
algorithms. Theoretical Computer Science. Elsevier. https://doi.org/10.1016/0304-3975(92)90319-B
chicago: Edelsbrunner, Herbert, Leonidas Guibas, János Pach, Richard Pollack, Raimund
Seidel, and Micha Sharir. “Arrangements of Curves in the Plane - Topology, Combinatorics,
and Algorithms.” Theoretical Computer Science. Elsevier, 1992. https://doi.org/10.1016/0304-3975(92)90319-B.
ieee: H. Edelsbrunner, L. Guibas, J. Pach, R. Pollack, R. Seidel, and M. Sharir,
“Arrangements of curves in the plane - topology, combinatorics, and algorithms,”
Theoretical Computer Science, vol. 92, no. 2. Elsevier, pp. 319–336, 1992.
ista: Edelsbrunner H, Guibas L, Pach J, Pollack R, Seidel R, Sharir M. 1992. Arrangements
of curves in the plane - topology, combinatorics, and algorithms. Theoretical
Computer Science. 92(2), 319–336.
mla: Edelsbrunner, Herbert, et al. “Arrangements of Curves in the Plane - Topology,
Combinatorics, and Algorithms.” Theoretical Computer Science, vol. 92,
no. 2, Elsevier, 1992, pp. 319–36, doi:10.1016/0304-3975(92)90319-B.
short: H. Edelsbrunner, L. Guibas, J. Pach, R. Pollack, R. Seidel, M. Sharir, Theoretical
Computer Science 92 (1992) 319–336.
date_created: 2018-12-11T12:06:37Z
date_published: 1992-01-20T00:00:00Z
date_updated: 2022-03-16T09:04:37Z
day: '20'
doi: 10.1016/0304-3975(92)90319-B
extern: '1'
intvolume: ' 92'
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.sciencedirect.com/science/article/pii/030439759290319B?via%3Dihub
month: '01'
oa: 1
oa_version: Published Version
page: 319 - 336
publication: Theoretical Computer Science
publication_identifier:
issn:
- 0304-3975
publication_status: published
publisher: Elsevier
publist_id: '2079'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Arrangements of curves in the plane - topology, combinatorics, and algorithms
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 92
year: '1992'
...
---
_id: '4052'
abstract:
- lang: eng
text: This paper describes an effective procedure for stratifying a real semi-algebraic
set into cells of constant description size. The attractive feature of our method
is that the number of cells produced is singly exponential in the number of input
variables. This compares favorably with the doubly exponential size of Collins'
decomposition. Unlike Collins' construction, however, our scheme does not produce
a cell complex but only a smooth stratification. Nevertheless, we are able to
apply our results in interesting ways to problems of point location and geometric
optimization.
acknowledgement: The authors wish to thank DEC/Systems Research Center and DEC/Paris
Research Laboratory, where part of this research was conducted. For individual support,
Bernard Chazelle acknowledges the National Science Foundation for supporting this
research in part under Grant CCR-8700917. Herbert Edelsbrunner acknowledges the
support of the National Science Foundation under Grant CCR-8714565. Micha Sharir
acknowledges the Office of Naval Research under Grant N00014-87-K-0129, the National
Science Foundation under Grant No. NSF-DCR-83-20085, grants from the Digital Equipment
Corporation and the IBM Corporation, and a research grant from the US-Israeli Binational
Science Foundation.
article_processing_charge: No
article_type: original
author:
- first_name: Bernard
full_name: Chazelle, Bernard
last_name: Chazelle
- 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
- first_name: Micha
full_name: Sharir, Micha
last_name: Sharir
citation:
ama: Chazelle B, Edelsbrunner H, Guibas L, Sharir M. A singly exponential stratification
scheme for real semi-algebraic varieties and its applications. Theoretical
Computer Science. 1991;84(1):77-105. doi:10.1016/0304-3975(91)90261-Y
apa: Chazelle, B., Edelsbrunner, H., Guibas, L., & Sharir, M. (1991). A singly
exponential stratification scheme for real semi-algebraic varieties and its applications.
Theoretical Computer Science. Elsevier. https://doi.org/10.1016/0304-3975(91)90261-Y
chicago: Chazelle, Bernard, Herbert Edelsbrunner, Leonidas Guibas, and Micha Sharir.
“A Singly Exponential Stratification Scheme for Real Semi-Algebraic Varieties
and Its Applications.” Theoretical Computer Science. Elsevier, 1991. https://doi.org/10.1016/0304-3975(91)90261-Y.
ieee: B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir, “A singly exponential
stratification scheme for real semi-algebraic varieties and its applications,”
Theoretical Computer Science, vol. 84, no. 1. Elsevier, pp. 77–105, 1991.
ista: Chazelle B, Edelsbrunner H, Guibas L, Sharir M. 1991. A singly exponential
stratification scheme for real semi-algebraic varieties and its applications.
Theoretical Computer Science. 84(1), 77–105.
mla: Chazelle, Bernard, et al. “A Singly Exponential Stratification Scheme for Real
Semi-Algebraic Varieties and Its Applications.” Theoretical Computer Science,
vol. 84, no. 1, Elsevier, 1991, pp. 77–105, doi:10.1016/0304-3975(91)90261-Y.
short: B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, Theoretical Computer
Science 84 (1991) 77–105.
date_created: 2018-12-11T12:06:39Z
date_published: 1991-07-22T00:00:00Z
date_updated: 2022-03-02T10:23:58Z
day: '22'
doi: 10.1016/0304-3975(91)90261-Y
extern: '1'
intvolume: ' 84'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.sciencedirect.com/science/article/pii/030439759190261Y?via%3Dihub
month: '07'
oa: 1
oa_version: Published Version
page: 77 - 105
publication: Theoretical Computer Science
publication_identifier:
eissn:
- 1879-2294
issn:
- 0304-3975
publication_status: published
publisher: Elsevier
publist_id: '2073'
quality_controlled: '1'
scopus_import: '1'
status: public
title: A singly exponential stratification scheme for real semi-algebraic varieties
and its applications
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 84
year: '1991'
...
---
_id: '4084'
abstract:
- lang: eng
text: "A tour of a finite set P of points is a necklace-tour if there are disks
with the points in P as centers such that two disks intersect if and only if their
centers are adjacent in . It has been observed by Sanders that a necklace-tour
is an optimal traveling salesman tour.\r\n\r\nIn this paper, we present an algorithm
that either reports that no necklace-tour exists or outputs a necklace-tour of
a given set of n points in O(n2 log n) time. If a tour is given, then we can test
in O(n2) time whether or not this tour is a necklace-tour. Both algorithms can
be generalized to ƒ-factors of point sets in the plane. The complexity results
rely on a combinatorial analysis of certain intersection graphs of disks defined
for finite sets of points in the plane."
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: Günter
full_name: Rote, Günter
last_name: Rote
- first_name: Emo
full_name: Welzl, Emo
last_name: Welzl
citation:
ama: Edelsbrunner H, Rote G, Welzl E. Testing the necklace condition for shortest
tours and optimal factors in the plane. Theoretical Computer Science. 1989;66(2):157-180.
doi:10.1016/0304-3975(89)90133-3
apa: Edelsbrunner, H., Rote, G., & Welzl, E. (1989). Testing the necklace condition
for shortest tours and optimal factors in the plane. Theoretical Computer Science.
Elsevier. https://doi.org/10.1016/0304-3975(89)90133-3
chicago: Edelsbrunner, Herbert, Günter Rote, and Emo Welzl. “Testing the Necklace
Condition for Shortest Tours and Optimal Factors in the Plane.” Theoretical
Computer Science. Elsevier, 1989. https://doi.org/10.1016/0304-3975(89)90133-3.
ieee: H. Edelsbrunner, G. Rote, and E. Welzl, “Testing the necklace condition for
shortest tours and optimal factors in the plane,” Theoretical Computer Science,
vol. 66, no. 2. Elsevier, pp. 157–180, 1989.
ista: Edelsbrunner H, Rote G, Welzl E. 1989. Testing the necklace condition for
shortest tours and optimal factors in the plane. Theoretical Computer Science.
66(2), 157–180.
mla: Edelsbrunner, Herbert, et al. “Testing the Necklace Condition for Shortest
Tours and Optimal Factors in the Plane.” Theoretical Computer Science,
vol. 66, no. 2, Elsevier, 1989, pp. 157–80, doi:10.1016/0304-3975(89)90133-3.
short: H. Edelsbrunner, G. Rote, E. Welzl, Theoretical Computer Science 66 (1989)
157–180.
date_created: 2018-12-11T12:06:51Z
date_published: 1989-08-01T00:00:00Z
date_updated: 2022-02-11T11:15:43Z
day: '01'
doi: 10.1016/0304-3975(89)90133-3
extern: '1'
intvolume: ' 66'
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.sciencedirect.com/science/article/pii/0304397589901333?via%3Dihub
month: '08'
oa: 1
oa_version: Published Version
page: 157 - 180
publication: Theoretical Computer Science
publication_identifier:
eissn:
- 1879-2294
issn:
- 0304-3975
publication_status: published
publisher: Elsevier
publist_id: '2041'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Testing the necklace condition for shortest tours and optimal factors in the
plane
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 66
year: '1989'
...
---
_id: '4116'
abstract:
- lang: eng
text: 'A straight line that intersects all members of a set S of objects in the
real plane is called a transversal of S. Geometric transforms are described that
reduce transversal problems for various types of objects to convex hull problems
for points. These reductions lead to efficient algorithms for finding transversals
which are also described. Applications of the algorithms are found in computer
graphics: “Reproduce the line displayed by a collection of pixels”, and in statistics:
“Find the line that minimizes the maximum distance from a collection of (weighted)
points in the plane”.'
acknowledgement: 'The author gratefully acknowledges the criticism of an anonymous
referee who discovered a serious flaw in an earlier version of this paper. '
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. Finding Transversals for Sets of Simple Geometric-Figures.
Theoretical Computer Science. 1985;35(1):55-69. doi:10.1016/0304-3975(85)90005-2
apa: Edelsbrunner, H. (1985). Finding Transversals for Sets of Simple Geometric-Figures.
Theoretical Computer Science. Elsevier. https://doi.org/10.1016/0304-3975(85)90005-2
chicago: Edelsbrunner, Herbert. “Finding Transversals for Sets of Simple Geometric-Figures.”
Theoretical Computer Science. Elsevier, 1985. https://doi.org/10.1016/0304-3975(85)90005-2.
ieee: H. Edelsbrunner, “Finding Transversals for Sets of Simple Geometric-Figures,”
Theoretical Computer Science, vol. 35, no. 1. Elsevier, pp. 55–69, 1985.
ista: Edelsbrunner H. 1985. Finding Transversals for Sets of Simple Geometric-Figures.
Theoretical Computer Science. 35(1), 55–69.
mla: Edelsbrunner, Herbert. “Finding Transversals for Sets of Simple Geometric-Figures.”
Theoretical Computer Science, vol. 35, no. 1, Elsevier, 1985, pp. 55–69,
doi:10.1016/0304-3975(85)90005-2.
short: H. Edelsbrunner, Theoretical Computer Science 35 (1985) 55–69.
date_created: 2018-12-11T12:07:02Z
date_published: 1985-01-01T00:00:00Z
date_updated: 2022-01-31T11:09:26Z
day: '01'
doi: 10.1016/0304-3975(85)90005-2
extern: '1'
intvolume: ' 35'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.sciencedirect.com/science/article/pii/0304397585900052?via%3Dihub
month: '01'
oa: 1
oa_version: Published Version
page: 55 - 69
publication: Theoretical Computer Science
publication_identifier:
eissn:
- 0304-3975
issn:
- 0304-3975
publication_status: published
publisher: Elsevier
publist_id: '2008'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Finding Transversals for Sets of Simple Geometric-Figures
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 35
year: '1985'
...
---
OA_place: publisher
OA_type: hybrid
_id: '4133'
abstract:
- lang: eng
text: In 1979 Kirpatrick obtained a practically feasible algorithm for planar regionlocation
working in linear space and logarithmic time, provided the regions are bounded
by straight line segments. No algorithm requiring only linear space and log-polynomial
time was known, so far, for general planar regionlocation, i.e. for the case where
regions are bounded by curves more complicated than straight line segments. As
main result of this paper such an algorithm is presented.
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: Hermann
full_name: Maurer, Hermann
last_name: Maurer
citation:
ama: Edelsbrunner H, Maurer H. A space-optimal solution of general region location.
Theoretical Computer Science. 1981;16(3):329-336. doi:10.1016/0304-3975(81)90103-1
apa: Edelsbrunner, H., & Maurer, H. (1981). A space-optimal solution of general
region location. Theoretical Computer Science. Elsevier. https://doi.org/10.1016/0304-3975(81)90103-1
chicago: Edelsbrunner, Herbert, and Hermann Maurer. “A Space-Optimal Solution of
General Region Location.” Theoretical Computer Science. Elsevier, 1981.
https://doi.org/10.1016/0304-3975(81)90103-1.
ieee: H. Edelsbrunner and H. Maurer, “A space-optimal solution of general region
location,” Theoretical Computer Science, vol. 16, no. 3. Elsevier, pp.
329–336, 1981.
ista: Edelsbrunner H, Maurer H. 1981. A space-optimal solution of general region
location. Theoretical Computer Science. 16(3), 329–336.
mla: Edelsbrunner, Herbert, and Hermann Maurer. “A Space-Optimal Solution of General
Region Location.” Theoretical Computer Science, vol. 16, no. 3, Elsevier,
1981, pp. 329–36, doi:10.1016/0304-3975(81)90103-1.
short: H. Edelsbrunner, H. Maurer, Theoretical Computer Science 16 (1981) 329–336.
date_created: 2018-12-11T12:07:08Z
date_published: 1981-01-01T00:00:00Z
date_updated: 2024-10-16T14:45:11Z
day: '01'
doi: 10.1016/0304-3975(81)90103-1
extern: '1'
intvolume: ' 16'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.sciencedirect.com/science/article/pii/0304397581901031
month: '01'
oa: 1
oa_version: Published Version
page: 329 - 336
publication: Theoretical Computer Science
publication_identifier:
issn:
- 0304-3975
publication_status: published
publisher: Elsevier
publist_id: '1989'
quality_controlled: '1'
scopus_import: '1'
status: public
title: A space-optimal solution of general region location
type: journal_article
user_id: 0043cee0-e5fc-11ee-9736-f83bc23afbf0
volume: 16
year: '1981'
...