---
_id: '14043'
abstract:
- lang: eng
text: 'Over the last two decades, a significant line of work in theoretical algorithms
has made progress in solving linear systems of the form Lx=b, where L is the Laplacian
matrix of a weighted graph with weights w(i,j)>0 on the edges. The solution x
of the linear system can be interpreted as the potentials of an electrical flow
in which the resistance on edge (i, j) is 1/w(i, j). Kelner et al. (in: Proceedings
of the 45th Annual ACM Symposium on the Theory of Computing, pp 911–920, 2013.
https://doi.org/10.1145/2488608.2488724) give a combinatorial, near-linear time
algorithm that maintains the Kirchoff Current Law, and gradually enforces the
Kirchoff Potential Law by updating flows around cycles (cycle toggling). In this
paper, we consider a dual version of the algorithm that maintains the Kirchoff
Potential Law, and gradually enforces the Kirchoff Current Law by cut toggling:
each iteration updates all potentials on one side of a fundamental cut of a spanning
tree by the same amount. We prove that this dual algorithm also runs in a near-linear
number of iterations. We show, however, that if we abstract cut toggling as a
natural data structure problem, this problem can be reduced to the online vector–matrix-vector
problem, which has been conjectured to be difficult for dynamic algorithms (Henzinger
et al., in: Proceedings of the 47th Annual ACM Symposium on the Theory of Computing,
pp 21–30, 2015. https://doi.org/10.1145/2746539.2746609). The conjecture implies
that the data structure does not have an O(n1−ϵ) time algorithm for any ϵ>0, and
thus a straightforward implementation of the cut-toggling algorithm requires essentially
linear time per iteration. To circumvent the lower bound, we batch update steps,
and perform them simultaneously instead of sequentially. An appropriate choice
of batching leads to an O˜(m1.5) time cut-toggling algorithm for solving Laplacian
systems. Furthermore, we show that if we sparsify the graph and call our algorithm
recursively on the Laplacian system implied by batching and sparsifying, we can
reduce the running time to O(m1+ϵ) for any ϵ>0. Thus, the dual cut-toggling algorithm
can achieve (almost) the same running time as its primal cycle-toggling counterpart.'
acknowledgement: Monika Henzinger was supported by funding from the European Research
Council (ERC) under the European Union’s Horizon 2020 research and innovation programme
Grant agreement No. 101019564 “The Design of Modern Fully Dynamic Data Structures
(MoDynStruct)” and from the Austrian Science Fund (FWF) project “Fast Algorithms
for a Reactive Network Layer (ReactNet)”, P 33775-N, with additional funding from
the netidee SCIENCE Stiftung, 2020–2024. Billy Jin was Supported in part by NSERC
fellowship PGSD3-532673-2019 and NSF grant CCF-2007009. Richard Peng was supported
in part by an NSERC Discovery Grant and NSF grant CCF-1846218. David P. Williamson
was supported in part by NSF grant CCF-2007009.
article_processing_charge: No
article_type: original
arxiv: 1
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: Billy
full_name: Jin, Billy
last_name: Jin
- first_name: Richard
full_name: Peng, Richard
last_name: Peng
- first_name: David P.
full_name: Williamson, David P.
last_name: Williamson
citation:
ama: Henzinger MH, Jin B, Peng R, Williamson DP. A combinatorial cut-toggling algorithm
for solving Laplacian linear systems. Algorithmica. 2023;85:2680-3716.
doi:10.1007/s00453-023-01154-8
apa: Henzinger, M. H., Jin, B., Peng, R., & Williamson, D. P. (2023). A combinatorial
cut-toggling algorithm for solving Laplacian linear systems. Algorithmica.
Springer Nature. https://doi.org/10.1007/s00453-023-01154-8
chicago: Henzinger, Monika H, Billy Jin, Richard Peng, and David P. Williamson.
“A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems.”
Algorithmica. Springer Nature, 2023. https://doi.org/10.1007/s00453-023-01154-8.
ieee: M. H. Henzinger, B. Jin, R. Peng, and D. P. Williamson, “A combinatorial cut-toggling
algorithm for solving Laplacian linear systems,” Algorithmica, vol. 85.
Springer Nature, pp. 2680–3716, 2023.
ista: Henzinger MH, Jin B, Peng R, Williamson DP. 2023. A combinatorial cut-toggling
algorithm for solving Laplacian linear systems. Algorithmica. 85, 2680–3716.
mla: Henzinger, Monika H., et al. “A Combinatorial Cut-Toggling Algorithm for Solving
Laplacian Linear Systems.” Algorithmica, vol. 85, Springer Nature, 2023,
pp. 2680–3716, doi:10.1007/s00453-023-01154-8.
short: M.H. Henzinger, B. Jin, R. Peng, D.P. Williamson, Algorithmica 85 (2023)
2680–3716.
date_created: 2023-08-13T22:01:13Z
date_published: 2023-12-01T00:00:00Z
date_updated: 2024-01-30T12:33:10Z
day: '01'
department:
- _id: MoHe
doi: 10.1007/s00453-023-01154-8
ec_funded: 1
external_id:
arxiv:
- '2010.16316'
isi:
- '001041254900002'
intvolume: ' 85'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2010.16316
month: '12'
oa: 1
oa_version: Preprint
page: 2680-3716
project:
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
call_identifier: H2020
grant_number: '101019564'
name: The design and evaluation of modern fully dynamic data structures
- _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
grant_number: 'P33775 '
name: Fast Algorithms for a Reactive Network Layer
publication: Algorithmica
publication_identifier:
eissn:
- 1432-0541
issn:
- 0178-4617
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: A combinatorial cut-toggling algorithm for solving Laplacian linear systems
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 85
year: '2023'
...
---
_id: '12086'
abstract:
- lang: eng
text: We present a simple algorithm for computing higher-order Delaunay mosaics
that works in Euclidean spaces of any finite dimensions. The algorithm selects
the vertices of the order-k mosaic from incrementally constructed lower-order
mosaics and uses an algorithm for weighted first-order Delaunay mosaics as a black-box
to construct the order-k mosaic from its vertices. Beyond this black-box, the
algorithm uses only combinatorial operations, thus facilitating easy implementation.
We extend this algorithm to compute higher-order α-shapes and provide open-source
implementations. We present experimental results for properties of higher-order
Delaunay mosaics of random point sets.
acknowledgement: Open access funding provided by Austrian Science Fund (FWF). This
project has received funding from the European Research Council (ERC) under the
European Union’s Horizon 2020 research and innovation programme, Grant No. 788183,
from the Wittgenstein Prize, Austrian Science Fund (FWF), Grant No. Z 342-N31, and
from the DFG Collaborative Research Center TRR 109, ‘Discretization in Geometry
and Dynamics’, Austrian Science Fund (FWF), Grant No. I 02979-N35.
article_processing_charge: Yes (via OA deal)
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: Georg F
full_name: Osang, Georg F
id: 464B40D6-F248-11E8-B48F-1D18A9856A87
last_name: Osang
citation:
ama: Edelsbrunner H, Osang GF. A simple algorithm for higher-order Delaunay mosaics
and alpha shapes. Algorithmica. 2023;85:277-295. doi:10.1007/s00453-022-01027-6
apa: Edelsbrunner, H., & Osang, G. F. (2023). A simple algorithm for higher-order
Delaunay mosaics and alpha shapes. Algorithmica. Springer Nature. https://doi.org/10.1007/s00453-022-01027-6
chicago: Edelsbrunner, Herbert, and Georg F Osang. “A Simple Algorithm for Higher-Order
Delaunay Mosaics and Alpha Shapes.” Algorithmica. Springer Nature, 2023.
https://doi.org/10.1007/s00453-022-01027-6.
ieee: H. Edelsbrunner and G. F. Osang, “A simple algorithm for higher-order Delaunay
mosaics and alpha shapes,” Algorithmica, vol. 85. Springer Nature, pp.
277–295, 2023.
ista: Edelsbrunner H, Osang GF. 2023. A simple algorithm for higher-order Delaunay
mosaics and alpha shapes. Algorithmica. 85, 277–295.
mla: Edelsbrunner, Herbert, and Georg F. Osang. “A Simple Algorithm for Higher-Order
Delaunay Mosaics and Alpha Shapes.” Algorithmica, vol. 85, Springer Nature,
2023, pp. 277–95, doi:10.1007/s00453-022-01027-6.
short: H. Edelsbrunner, G.F. Osang, Algorithmica 85 (2023) 277–295.
date_created: 2022-09-11T22:01:57Z
date_published: 2023-01-01T00:00:00Z
date_updated: 2023-06-27T12:53:43Z
day: '01'
ddc:
- '510'
department:
- _id: HeEd
doi: 10.1007/s00453-022-01027-6
ec_funded: 1
external_id:
isi:
- '000846967100001'
file:
- access_level: open_access
checksum: 71685ca5121f4c837f40c3f8eb50c915
content_type: application/pdf
creator: dernst
date_created: 2023-01-20T10:02:48Z
date_updated: 2023-01-20T10:02:48Z
file_id: '12322'
file_name: 2023_Algorithmica_Edelsbrunner.pdf
file_size: 911017
relation: main_file
success: 1
file_date_updated: 2023-01-20T10:02:48Z
has_accepted_license: '1'
intvolume: ' 85'
isi: 1
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
page: 277-295
project:
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '788183'
name: Alpha Shape Theory Extended
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: The Wittgenstein Prize
- _id: 2561EBF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: I02979-N35
name: Persistence and stability of geometric complexes
publication: Algorithmica
publication_identifier:
eissn:
- 1432-0541
issn:
- 0178-4617
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: A simple algorithm for higher-order Delaunay mosaics and alpha shapes
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: 2EBD1598-F248-11E8-B48F-1D18A9856A87
volume: 85
year: '2023'
...
---
_id: '8286'
abstract:
- lang: eng
text: "We consider the following dynamic load-balancing process: given an underlying
graph G with n nodes, in each step t≥ 0, one unit of load is created, and placed
at a randomly chosen graph node. In the same step, the chosen node picks a random
neighbor, and the two nodes balance their loads by averaging them. We are interested
in the expected gap between the minimum and maximum loads at nodes as the process
progresses, and its dependence on n and on the graph structure. Variants of the
above graphical balanced allocation process have been studied previously by Peres,
Talwar, and Wieder [Peres et al., 2015], and by Sauerwald and Sun [Sauerwald and
Sun, 2015]. These authors left as open the question of characterizing the gap
in the case of cycle graphs in the dynamic case, where weights are created during
the algorithm’s execution. For this case, the only known upper bound is of \U0001D4AA(n
log n), following from a majorization argument due to [Peres et al., 2015], which
analyzes a related graphical allocation process. In this paper, we provide an
upper bound of \U0001D4AA (√n log n) on the expected gap of the above process
for cycles of length n. We introduce a new potential analysis technique, which
enables us to bound the difference in load between k-hop neighbors on the cycle,
for any k ≤ n/2. We complement this with a \"gap covering\" argument, which bounds
the maximum value of the gap by bounding its value across all possible subsets
of a certain structure, and recursively bounding the gaps within each subset.
We provide analytical and experimental evidence that our upper bound on the gap
is tight up to a logarithmic factor. "
acknowledgement: The authors sincerely thank Thomas Sauerwald and George Giakkoupis
for insightful discussions, and Mohsen Ghaffari, Yuval Peres, and Udi Wieder for
feedback on earlier versions of this draft. We also thank the ICALP anonymous reviewers
for their very useful comments. Open access funding provided by Institute of Science
and Technology (IST Austria). Funding was provided by European Research Council
(Grant No. PR1042ERC01).
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
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: Giorgi
full_name: Nadiradze, Giorgi
id: 3279A00C-F248-11E8-B48F-1D18A9856A87
last_name: Nadiradze
orcid: 0000-0001-5634-0731
- first_name: Amirmojtaba
full_name: Sabour, Amirmojtaba
id: bcc145fd-e77f-11ea-ae8b-80d661dbff67
last_name: Sabour
citation:
ama: Alistarh D-A, Nadiradze G, Sabour A. Dynamic averaging load balancing on cycles.
Algorithmica. 2021. doi:10.1007/s00453-021-00905-9
apa: 'Alistarh, D.-A., Nadiradze, G., & Sabour, A. (2021). Dynamic averaging
load balancing on cycles. Algorithmica. Virtual, Online; Germany: Springer
Nature. https://doi.org/10.1007/s00453-021-00905-9'
chicago: Alistarh, Dan-Adrian, Giorgi Nadiradze, and Amirmojtaba Sabour. “Dynamic
Averaging Load Balancing on Cycles.” Algorithmica. Springer Nature, 2021.
https://doi.org/10.1007/s00453-021-00905-9.
ieee: D.-A. Alistarh, G. Nadiradze, and A. Sabour, “Dynamic averaging load balancing
on cycles,” Algorithmica. Springer Nature, 2021.
ista: Alistarh D-A, Nadiradze G, Sabour A. 2021. Dynamic averaging load balancing
on cycles. Algorithmica.
mla: Alistarh, Dan-Adrian, et al. “Dynamic Averaging Load Balancing on Cycles.”
Algorithmica, Springer Nature, 2021, doi:10.1007/s00453-021-00905-9.
short: D.-A. Alistarh, G. Nadiradze, A. Sabour, Algorithmica (2021).
conference:
end_date: 2020-07-11
location: Virtual, Online; Germany
name: 'ICALP: International Colloquium on Automata, Languages, and Programming '
start_date: 2020-07-08
date_created: 2020-08-24T06:24:04Z
date_published: 2021-12-24T00:00:00Z
date_updated: 2024-03-05T07:35:53Z
day: '24'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.1007/s00453-021-00905-9
ec_funded: 1
external_id:
arxiv:
- '2003.09297'
isi:
- '000734004600001'
file:
- access_level: open_access
checksum: 21169b25b0c8e17b21e12af22bff9870
content_type: application/pdf
creator: cchlebak
date_created: 2021-12-27T10:36:40Z
date_updated: 2021-12-27T10:36:40Z
file_id: '10577'
file_name: 2021_Algorithmica_Alistarh.pdf
file_size: 525950
relation: main_file
success: 1
file_date_updated: 2021-12-27T10:36:40Z
has_accepted_license: '1'
isi: 1
language:
- iso: eng
month: '12'
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: B67AFEDC-15C9-11EA-A837-991A96BB2854
name: IST Austria Open Access Fund
publication: Algorithmica
publication_identifier:
eissn:
- 1432-0541
issn:
- 0178-4617
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
link:
- relation: earlier_version
url: https://doi.org/10.4230/LIPIcs.ICALP.2020.7
record:
- id: '15077'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Dynamic averaging load balancing on cycles
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
year: '2021'
...
---
_id: '11674'
abstract:
- lang: eng
text: In this paper, we study the problem of opening centers to cluster a set of
clients in a metric space so as to minimize the sum of the costs of the centers
and of the cluster radii, in a dynamic environment where clients arrive and depart,
and the solution must be updated efficiently while remaining competitive with
respect to the current optimal solution. We call this dynamic sum-of-radii clustering
problem. We present a data structure that maintains a solution whose cost is within
a constant factor of the cost of an optimal solution in metric spaces with bounded
doubling dimension and whose worst-case update time is logarithmic in the parameters
of the problem.
article_processing_charge: No
article_type: original
arxiv: 1
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: Dariusz
full_name: Leniowski, Dariusz
last_name: Leniowski
- first_name: Claire
full_name: Mathieu, Claire
last_name: Mathieu
citation:
ama: Henzinger MH, Leniowski D, Mathieu C. Dynamic clustering to minimize the sum
of radii. Algorithmica. 2020;82(11):3183-3194. doi:10.1007/s00453-020-00721-7
apa: Henzinger, M. H., Leniowski, D., & Mathieu, C. (2020). Dynamic clustering
to minimize the sum of radii. Algorithmica. Springer Nature. https://doi.org/10.1007/s00453-020-00721-7
chicago: Henzinger, Monika H, Dariusz Leniowski, and Claire Mathieu. “Dynamic Clustering
to Minimize the Sum of Radii.” Algorithmica. Springer Nature, 2020. https://doi.org/10.1007/s00453-020-00721-7.
ieee: M. H. Henzinger, D. Leniowski, and C. Mathieu, “Dynamic clustering to minimize
the sum of radii,” Algorithmica, vol. 82, no. 11. Springer Nature, pp.
3183–3194, 2020.
ista: Henzinger MH, Leniowski D, Mathieu C. 2020. Dynamic clustering to minimize
the sum of radii. Algorithmica. 82(11), 3183–3194.
mla: Henzinger, Monika H., et al. “Dynamic Clustering to Minimize the Sum of Radii.”
Algorithmica, vol. 82, no. 11, Springer Nature, 2020, pp. 3183–94, doi:10.1007/s00453-020-00721-7.
short: M.H. Henzinger, D. Leniowski, C. Mathieu, Algorithmica 82 (2020) 3183–3194.
date_created: 2022-07-27T13:58:58Z
date_published: 2020-11-01T00:00:00Z
date_updated: 2022-09-12T08:50:14Z
day: '01'
doi: 10.1007/s00453-020-00721-7
extern: '1'
external_id:
arxiv:
- '1707.02577'
intvolume: ' 82'
issue: '11'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.1707.02577
month: '11'
oa: 1
oa_version: Preprint
page: 3183-3194
publication: Algorithmica
publication_identifier:
eissn:
- 1432-0541
issn:
- 0178-4617
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Dynamic clustering to minimize the sum of radii
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 82
year: '2020'
...
---
_id: '11675'
abstract:
- lang: eng
text: 'We consider the problems of maintaining an approximate maximum matching and
an approximate minimum vertex cover in a dynamic graph undergoing a sequence of
edge insertions/deletions. Starting with the seminal work of Onak and Rubinfeld
(in: Proceedings of the ACM symposium on theory of computing (STOC), 2010), this
problem has received significant attention in recent years. Very recently, extending
the framework of Baswana et al. (in: Proceedings of the IEEE symposium on foundations
of computer science (FOCS), 2011) , Solomon (in: Proceedings of the IEEE symposium
on foundations of computer science (FOCS), 2016) gave a randomized dynamic algorithm
for this problem that has an approximation ratio of 2 and an amortized update
time of O(1) with high probability. This algorithm requires the assumption of
an oblivious adversary, meaning that the future sequence of edge insertions/deletions
in the graph cannot depend in any way on the algorithm’s past output. A natural
way to remove the assumption on oblivious adversary is to give a deterministic
dynamic algorithm for the same problem in O(1) update time. In this paper, we
resolve this question. We present a new deterministic fully dynamic algorithm
that maintains a O(1)-approximate minimum vertex cover and maximum fractional
matching, with an amortized update time of O(1). Previously, the best deterministic
algorithm for this problem was due to Bhattacharya et al. (in: Proceedings of
the ACM-SIAM symposium on discrete algorithms (SODA), 2015); it had an approximation
ratio of (2+ε) and an amortized update time of O(logn/ε2). Our result can be generalized
to give a fully dynamic O(f3)-approximate algorithm with O(f2) amortized update
time for the hypergraph vertex cover and fractional hypergraph matching problem,
where every hyperedge has at most f vertices.'
article_processing_charge: No
article_type: original
author:
- first_name: Sayan
full_name: Bhattacharya, Sayan
last_name: Bhattacharya
- first_name: Deeparnab
full_name: Chakrabarty, Deeparnab
last_name: Chakrabarty
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
citation:
ama: Bhattacharya S, Chakrabarty D, Henzinger MH. Deterministic dynamic matching
in O(1) update time. Algorithmica. 2020;82(4):1057-1080. doi:10.1007/s00453-019-00630-4
apa: Bhattacharya, S., Chakrabarty, D., & Henzinger, M. H. (2020). Deterministic
dynamic matching in O(1) update time. Algorithmica. Springer Nature. https://doi.org/10.1007/s00453-019-00630-4
chicago: Bhattacharya, Sayan, Deeparnab Chakrabarty, and Monika H Henzinger. “Deterministic
Dynamic Matching in O(1) Update Time.” Algorithmica. Springer Nature, 2020.
https://doi.org/10.1007/s00453-019-00630-4.
ieee: S. Bhattacharya, D. Chakrabarty, and M. H. Henzinger, “Deterministic dynamic
matching in O(1) update time,” Algorithmica, vol. 82, no. 4. Springer Nature,
pp. 1057–1080, 2020.
ista: Bhattacharya S, Chakrabarty D, Henzinger MH. 2020. Deterministic dynamic matching
in O(1) update time. Algorithmica. 82(4), 1057–1080.
mla: Bhattacharya, Sayan, et al. “Deterministic Dynamic Matching in O(1) Update
Time.” Algorithmica, vol. 82, no. 4, Springer Nature, 2020, pp. 1057–80,
doi:10.1007/s00453-019-00630-4.
short: S. Bhattacharya, D. Chakrabarty, M.H. Henzinger, Algorithmica 82 (2020) 1057–1080.
date_created: 2022-07-27T14:31:06Z
date_published: 2020-04-01T00:00:00Z
date_updated: 2022-09-12T08:55:46Z
day: '01'
doi: 10.1007/s00453-019-00630-4
extern: '1'
intvolume: ' 82'
issue: '4'
keyword:
- Dynamic algorithms
- Data structures
- Graph algorithms
- Matching
- Vertex cover
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1007/s00453-019-00630-4
month: '04'
oa: 1
oa_version: Published Version
page: 1057-1080
publication: Algorithmica
publication_identifier:
eissn:
- 1432-0541
issn:
- 0178-4617
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Deterministic dynamic matching in O(1) update time
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 82
year: '2020'
...
---
_id: '11676'
abstract:
- lang: eng
text: We study the problem of maximizing a monotone submodular function with viability
constraints. This problem originates from computational biology, where we are
given a phylogenetic tree over a set of species and a directed graph, the so-called
food web, encoding viability constraints between these species. These food webs
usually have constant depth. The goal is to select a subset of k species that
satisfies the viability constraints and has maximal phylogenetic diversity. As
this problem is known to be NP-hard, we investigate approximation algorithms.
We present the first constant factor approximation algorithm if the depth is constant.
Its approximation ratio is (1−1e√). This algorithm not only applies to phylogenetic
trees with viability constraints but for arbitrary monotone submodular set functions
with viability constraints. Second, we show that there is no (1−1/e+ϵ)-approximation
algorithm for our problem setting (even for additive functions) and that there
is no approximation algorithm for a slight extension of this setting.
acknowledgement: "The research leading to these results has received funding from
the European Research\r\nCouncil under the European Union’s Seventh Framework Programme
(FP/2007-2013)/ERC Grant Agreement No. 340506."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Wolfgang
full_name: Dvořák, Wolfgang
last_name: Dvořák
- 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: David P.
full_name: Williamson, David P.
last_name: Williamson
citation:
ama: Dvořák W, Henzinger MH, Williamson DP. Maximizing a submodular function with
viability constraints. Algorithmica. 2017;77(1):152-172. doi:10.1007/s00453-015-0066-y
apa: Dvořák, W., Henzinger, M. H., & Williamson, D. P. (2017). Maximizing a
submodular function with viability constraints. Algorithmica. Springer
Nature. https://doi.org/10.1007/s00453-015-0066-y
chicago: Dvořák, Wolfgang, Monika H Henzinger, and David P. Williamson. “Maximizing
a Submodular Function with Viability Constraints.” Algorithmica. Springer
Nature, 2017. https://doi.org/10.1007/s00453-015-0066-y.
ieee: W. Dvořák, M. H. Henzinger, and D. P. Williamson, “Maximizing a submodular
function with viability constraints,” Algorithmica, vol. 77, no. 1. Springer
Nature, pp. 152–172, 2017.
ista: Dvořák W, Henzinger MH, Williamson DP. 2017. Maximizing a submodular function
with viability constraints. Algorithmica. 77(1), 152–172.
mla: Dvořák, Wolfgang, et al. “Maximizing a Submodular Function with Viability Constraints.”
Algorithmica, vol. 77, no. 1, Springer Nature, 2017, pp. 152–72, doi:10.1007/s00453-015-0066-y.
short: W. Dvořák, M.H. Henzinger, D.P. Williamson, Algorithmica 77 (2017) 152–172.
date_created: 2022-07-27T14:37:24Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2022-09-12T08:58:16Z
day: '01'
doi: 10.1007/s00453-015-0066-y
extern: '1'
external_id:
arxiv:
- '1611.05753'
intvolume: ' 77'
issue: '1'
keyword:
- Approximation algorithms
- Submodular functions
- Phylogenetic diversity
- Viability constraints
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1611.05753
month: '01'
oa: 1
oa_version: Preprint
page: 152-172
publication: Algorithmica
publication_identifier:
eissn:
- 1432-0541
issn:
- 0178-4617
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Maximizing a submodular function with viability constraints
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 77
year: '2017'
...
---
_id: '11679'
abstract:
- lang: eng
text: "We are given a set T = {T 1 ,T 2 , . . .,T k } of rooted binary trees, each
T i leaf-labeled by a subset L(Ti)⊂{1,2,...,n} . If T is a tree on {1,2, . . .,n
}, we let T|L denote the minimal subtree of T induced by the nodes of L and all
their ancestors. The consensus tree problem asks whether there exists a tree T
* such that, for every i , T∗|L(Ti) is homeomorphic to T i .\r\n\r\nWe present
algorithms which test if a given set of trees has a consensus tree and if so,
construct one. The deterministic algorithm takes time min{O(N n 1/2 ), O(N+ n
2 log n )}, where N=∑i|Ti| , and uses linear space. The randomized algorithm takes
time O(N log3 n) and uses linear space. The previous best for this problem was
a 1981 O(Nn) algorithm by Aho et al. Our faster deterministic algorithm uses a
new efficient algorithm for the following interesting dynamic graph problem: Given
a graph G with n nodes and m edges and a sequence of b batches of one or more
edge deletions, then, after each batch, either find a new component that has just
been created or determine that there is no such component. For this problem, we
have a simple algorithm with running time O(n 2 log n + b 0 min{n 2 , m log n
}), where b 0 is the number of batches which do not result in a new component.
For our particular application, b0≤1 . If all edges are deleted, then the best
previously known deterministic algorithm requires time O(mn−−√) to solve this
problem. We also present two applications of these consensus tree algorithms which
solve other problems in computational evolutionary biology."
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: V.
full_name: King, V.
last_name: King
- first_name: T.
full_name: Warnow, T.
last_name: Warnow
citation:
ama: Henzinger MH, King V, Warnow T. Constructing a tree from homeomorphic subtrees,
with applications to computational evolutionary biology. Algorithmica.
1999;24:1-13. doi:10.1007/pl00009268
apa: Henzinger, M. H., King, V., & Warnow, T. (1999). Constructing a tree from
homeomorphic subtrees, with applications to computational evolutionary biology.
Algorithmica. Springer Nature. https://doi.org/10.1007/pl00009268
chicago: Henzinger, Monika H, V. King, and T. Warnow. “Constructing a Tree from
Homeomorphic Subtrees, with Applications to Computational Evolutionary Biology.”
Algorithmica. Springer Nature, 1999. https://doi.org/10.1007/pl00009268.
ieee: M. H. Henzinger, V. King, and T. Warnow, “Constructing a tree from homeomorphic
subtrees, with applications to computational evolutionary biology,” Algorithmica,
vol. 24. Springer Nature, pp. 1–13, 1999.
ista: Henzinger MH, King V, Warnow T. 1999. Constructing a tree from homeomorphic
subtrees, with applications to computational evolutionary biology. Algorithmica.
24, 1–13.
mla: Henzinger, Monika H., et al. “Constructing a Tree from Homeomorphic Subtrees,
with Applications to Computational Evolutionary Biology.” Algorithmica,
vol. 24, Springer Nature, 1999, pp. 1–13, doi:10.1007/pl00009268.
short: M.H. Henzinger, V. King, T. Warnow, Algorithmica 24 (1999) 1–13.
date_created: 2022-07-27T15:02:28Z
date_published: 1999-05-01T00:00:00Z
date_updated: 2023-02-21T16:33:24Z
day: '01'
doi: 10.1007/pl00009268
extern: '1'
intvolume: ' 24'
keyword:
- Algorithms
- Data structures
- Evolutionary biology
- Theory of databases
language:
- iso: eng
month: '05'
oa_version: None
page: 1-13
publication: Algorithmica
publication_identifier:
eissn:
- 1432-0541
issn:
- 0178-4617
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '11927'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Constructing a tree from homeomorphic subtrees, with applications to computational
evolutionary biology
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 24
year: '1999'
...
---
_id: '11680'
abstract:
- lang: eng
text: 'We present a model for edge updates with restricted randomness in dynamic
graph algorithms and a general technique for analyzing the expected running time
of an update operation. This model is able to capture the average case in many
applications, since (1) it allows restrictions on the set of edges which can be
used for insertions and (2) the type (insertion or deletion) of each update operation
is arbitrary, i.e., not random. We use our technique to analyze existing and new
dynamic algorithms for the following problems: maximum cardinality matching, minimum
spanning forest, connectivity, 2-edge connectivity, k -edge connectivity, k -vertex
connectivity, and bipartiteness. Given a random graph G with m 0 edges and n vertices
and a sequence of l update operations such that the graph contains m i edges after
operation i , the expected time for performing the updates for any l is O(llogn+∑li=1n/m−−√i)
in the case of minimum spanning forests, connectivity, 2-edge connectivity, and
bipartiteness. The expected time per update operation is O(n) in the case of maximum
matching. We also give improved bounds for k -edge and k -vertex connectivity.
Additionally we give an insertions-only algorithm for maximum cardinality matching
with worst-case O(n) amortized time per insertion.'
acknowledgement: The authors would like to thank Emo Welzl for helpful discussions.
article_processing_charge: No
article_type: original
author:
- first_name: D.
full_name: Alberts, D.
last_name: Alberts
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
citation:
ama: Alberts D, Henzinger MH. Average-case analysis of dynamic graph algorithms.
Algorithmica. 1998;20:31-60. doi:10.1007/pl00009186
apa: Alberts, D., & Henzinger, M. H. (1998). Average-case analysis of dynamic
graph algorithms. Algorithmica. Springer Nature. https://doi.org/10.1007/pl00009186
chicago: Alberts, D., and Monika H Henzinger. “Average-Case Analysis of Dynamic
Graph Algorithms.” Algorithmica. Springer Nature, 1998. https://doi.org/10.1007/pl00009186.
ieee: D. Alberts and M. H. Henzinger, “Average-case analysis of dynamic graph algorithms,”
Algorithmica, vol. 20. Springer Nature, pp. 31–60, 1998.
ista: Alberts D, Henzinger MH. 1998. Average-case analysis of dynamic graph algorithms.
Algorithmica. 20, 31–60.
mla: Alberts, D., and Monika H. Henzinger. “Average-Case Analysis of Dynamic Graph
Algorithms.” Algorithmica, vol. 20, Springer Nature, 1998, pp. 31–60, doi:10.1007/pl00009186.
short: D. Alberts, M.H. Henzinger, Algorithmica 20 (1998) 31–60.
date_created: 2022-07-28T06:50:51Z
date_published: 1998-01-01T00:00:00Z
date_updated: 2023-02-21T16:33:27Z
day: '01'
doi: 10.1007/pl00009186
extern: '1'
intvolume: ' 20'
keyword:
- Dynamic graph algorithm
- Average-case analysis
- Minimum spanning forest
- Connectivity
- Bipartiteness
- Maximum matching.
language:
- iso: eng
month: '01'
oa_version: None
page: 31-60
publication: Algorithmica
publication_identifier:
eissn:
- 1432-0541
issn:
- 0178-4617
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '11928'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Average-case analysis of dynamic graph algorithms
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 20
year: '1998'
...
---
_id: '11681'
abstract:
- lang: eng
text: We prove lower bounds on the complexity of maintaining fully dynamic k -edge
or k -vertex connectivity in plane graphs and in (k-1) -vertex connected graphs.
We show an amortized lower bound of Ω (log n / {k (log log n} + log b)) per edge
insertion, deletion, or query operation in the cell probe model, where b is the
word size of the machine and n is the number of vertices in G . We also show an
amortized lower bound of Ω (log n /(log log n + log b)) per operation for fully
dynamic planarity testing in embedded graphs. These are the first lower bounds
for fully dynamic connectivity problems.
acknowledgement: .
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: M. L.
full_name: Fredman, M. L.
last_name: Fredman
citation:
ama: Henzinger MH, Fredman ML. Lower bounds for fully dynamic connectivity problems
in graphs. Algorithmica. 1998;22(3):351-362. doi:10.1007/pl00009228
apa: Henzinger, M. H., & Fredman, M. L. (1998). Lower bounds for fully dynamic
connectivity problems in graphs. Algorithmica. Springer Nature. https://doi.org/10.1007/pl00009228
chicago: Henzinger, Monika H, and M. L. Fredman. “Lower Bounds for Fully Dynamic
Connectivity Problems in Graphs.” Algorithmica. Springer Nature, 1998.
https://doi.org/10.1007/pl00009228.
ieee: M. H. Henzinger and M. L. Fredman, “Lower bounds for fully dynamic connectivity
problems in graphs,” Algorithmica, vol. 22, no. 3. Springer Nature, pp.
351–362, 1998.
ista: Henzinger MH, Fredman ML. 1998. Lower bounds for fully dynamic connectivity
problems in graphs. Algorithmica. 22(3), 351–362.
mla: Henzinger, Monika H., and M. L. Fredman. “Lower Bounds for Fully Dynamic Connectivity
Problems in Graphs.” Algorithmica, vol. 22, no. 3, Springer Nature, 1998,
pp. 351–62, doi:10.1007/pl00009228.
short: M.H. Henzinger, M.L. Fredman, Algorithmica 22 (1998) 351–362.
date_created: 2022-07-28T06:58:36Z
date_published: 1998-11-01T00:00:00Z
date_updated: 2022-09-12T09:03:36Z
day: '01'
doi: 10.1007/pl00009228
extern: '1'
intvolume: ' 22'
issue: '3'
keyword:
- Dynamic planarity testing
- Dynamic connectivity testing
- Lower bounds
- Cell probe model
language:
- iso: eng
month: '11'
oa_version: None
page: 351-362
publication: Algorithmica
publication_identifier:
eissn:
- 1432-0541
issn:
- 0178-4617
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Lower bounds for fully dynamic connectivity problems in graphs
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 22
year: '1998'
...
---
_id: '11677'
abstract:
- lang: eng
text: "We present an algorithm for maintaining the biconnected components of a graph
during a sequence of edge insertions and deletions. It requires linear storage
and preprocessing time. The amortized running time for insertions and for deletions
isO(m 2/3 ), wherem is the number of edges in the graph. Any query of the form
‘Are the verticesu andv biconnected?’ can be answered in timeO(1). This is the
first sublinear algorithm for this problem. We can also output all articulation
points separating any two vertices efficiently.\r\n\r\nIf the input is a plane
graph, the amortized running time for insertions and deletions drops toO(√n logn)
and the query time isO(log2 n), wheren is the number of vertices in the graph.
The best previously known solution takes timeO(n 2/3 ) per update or query."
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
citation:
ama: Henzinger MH. Fully dynamic biconnectivity in graphs. Algorithmica.
1995;13(6):503-538. doi:10.1007/bf01189067
apa: Henzinger, M. H. (1995). Fully dynamic biconnectivity in graphs. Algorithmica.
Springer Nature. https://doi.org/10.1007/bf01189067
chicago: Henzinger, Monika H. “Fully Dynamic Biconnectivity in Graphs.” Algorithmica.
Springer Nature, 1995. https://doi.org/10.1007/bf01189067.
ieee: M. H. Henzinger, “Fully dynamic biconnectivity in graphs,” Algorithmica,
vol. 13, no. 6. Springer Nature, pp. 503–538, 1995.
ista: Henzinger MH. 1995. Fully dynamic biconnectivity in graphs. Algorithmica.
13(6), 503–538.
mla: Henzinger, Monika H. “Fully Dynamic Biconnectivity in Graphs.” Algorithmica,
vol. 13, no. 6, Springer Nature, 1995, pp. 503–38, doi:10.1007/bf01189067.
short: M.H. Henzinger, Algorithmica 13 (1995) 503–538.
date_created: 2022-07-27T14:50:46Z
date_published: 1995-06-01T00:00:00Z
date_updated: 2022-09-12T09:00:14Z
day: '01'
doi: 10.1007/bf01189067
extern: '1'
intvolume: ' 13'
issue: '6'
language:
- iso: eng
month: '06'
oa_version: None
page: 503-538
publication: Algorithmica
publication_identifier:
eissn:
- 1432-0541
issn:
- 0178-4617
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Fully dynamic biconnectivity in graphs
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 13
year: '1995'
...
---
_id: '4075'
abstract:
- lang: eng
text: A key problem in computational geometry is the identification of subsets of
a point set having particular properties. We study this problem for the properties
of convexity and emptiness. We show that finding empty triangles is related to
the problem of determining pairs of vertices that see each other in a star-shaped
polygon. A linear-time algorithm for this problem which is of independent interest
yields an optimal algorithm for finding all empty triangles. This result is then
extended to an algorithm for finding empty convex r-gons (r> 3) and for determining
a largest empty convex subset. Finally, extensions to higher dimensions are mentioned.
acknowledgement: The first author is pleased to acknowledge support by the National
Science Foundation under Grant CCR-8700917. The research of the second author was
supported by Amoco Foundation Faculty Development Grant CS 1-6-44862 and by the
National Science Foundatio
article_processing_charge: No
article_type: original
author:
- first_name: David
full_name: Dobkin, David
last_name: Dobkin
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Mark
full_name: Overmars, Mark
last_name: Overmars
citation:
ama: Dobkin D, Edelsbrunner H, Overmars M. Searching for empty convex polygons.
Algorithmica. 1990;5(4):561-571. doi:10.1007/BF01840404
apa: Dobkin, D., Edelsbrunner, H., & Overmars, M. (1990). Searching for empty
convex polygons. Algorithmica. Springer. https://doi.org/10.1007/BF01840404
chicago: Dobkin, David, Herbert Edelsbrunner, and Mark Overmars. “Searching for
Empty Convex Polygons.” Algorithmica. Springer, 1990. https://doi.org/10.1007/BF01840404.
ieee: D. Dobkin, H. Edelsbrunner, and M. Overmars, “Searching for empty convex polygons,”
Algorithmica, vol. 5, no. 4. Springer, pp. 561–571, 1990.
ista: Dobkin D, Edelsbrunner H, Overmars M. 1990. Searching for empty convex polygons.
Algorithmica. 5(4), 561–571.
mla: Dobkin, David, et al. “Searching for Empty Convex Polygons.” Algorithmica,
vol. 5, no. 4, Springer, 1990, pp. 561–71, doi:10.1007/BF01840404.
short: D. Dobkin, H. Edelsbrunner, M. Overmars, Algorithmica 5 (1990) 561–571.
date_created: 2018-12-11T12:06:47Z
date_published: 1990-06-01T00:00:00Z
date_updated: 2022-02-21T10:55:13Z
day: '01'
doi: 10.1007/BF01840404
extern: '1'
intvolume: ' 5'
issue: '4'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/article/10.1007/BF01840404
month: '06'
oa_version: None
page: 561 - 571
publication: Algorithmica
publication_identifier:
eissn:
- 1432-0541
issn:
- 0178-4617
publication_status: published
publisher: Springer
publist_id: '2049'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Searching for empty convex polygons
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 5
year: '1990'
...
---
_id: '3580'
abstract:
- lang: eng
text: "An edge-skeleton in an arrangementA(H) of a finite set of planes inE 3 is
a connected collection of edges inA(H). We give a method that constructs a skeleton
inO(√n logn) time per edge. This method implies new and more efficient algorithms
for a number of structures in computational geometry including order-k power diagrams
inE 2 and space cutting trees inE 3.\r\nWe also give a novel method for handling
special cases which has the potential to substantially decrease the amount of
effort needed to implement geometric algorithms."
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. Edge-skeletons in arrangements with applications. Algorithmica.
1986;1(1-4):93-109. doi:10.1007/BF01840438
apa: Edelsbrunner, H. (1986). Edge-skeletons in arrangements with applications.
Algorithmica. Springer. https://doi.org/10.1007/BF01840438
chicago: Edelsbrunner, Herbert. “Edge-Skeletons in Arrangements with Applications.”
Algorithmica. Springer, 1986. https://doi.org/10.1007/BF01840438.
ieee: H. Edelsbrunner, “Edge-skeletons in arrangements with applications,” Algorithmica,
vol. 1, no. 1–4. Springer, pp. 93–109, 1986.
ista: Edelsbrunner H. 1986. Edge-skeletons in arrangements with applications. Algorithmica.
1(1–4), 93–109.
mla: Edelsbrunner, Herbert. “Edge-Skeletons in Arrangements with Applications.”
Algorithmica, vol. 1, no. 1–4, Springer, 1986, pp. 93–109, doi:10.1007/BF01840438.
short: H. Edelsbrunner, Algorithmica 1 (1986) 93–109.
date_created: 2018-12-11T12:04:04Z
date_published: 1986-11-01T00:00:00Z
date_updated: 2022-02-02T09:36:32Z
day: '01'
doi: 10.1007/BF01840438
extern: '1'
intvolume: ' 1'
issue: 1-4
language:
- iso: eng
month: '11'
oa_version: None
page: 93 - 109
publication: Algorithmica
publication_identifier:
eissn:
- 1432-0541
issn:
- 0178-4617
publication_status: published
publisher: Springer
publist_id: '2805'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Edge-skeletons in arrangements with applications
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 1
year: '1986'
...