---
_id: '14769'
abstract:
- lang: eng
text: 'For a set of points in Rd, the Euclidean k-means problems consists of finding
k centers such that the sum of distances squared from each data point to its closest
center is minimized. Coresets are one the main tools developed recently to solve
this problem in a big data context. They allow to compress the initial dataset
while preserving its structure: running any algorithm on the coreset provides
a guarantee almost equivalent to running it on the full data. In this work, we
study coresets in a fully-dynamic setting: points are added and deleted with the
goal to efficiently maintain a coreset with which a k-means solution can be computed.
Based on an algorithm from Henzinger and Kale [ESA''20], we present an efficient
and practical implementation of a fully dynamic coreset algorithm, that improves
the running time by up to a factor of 20 compared to our non-optimized implementation
of the algorithm by Henzinger and Kale, without sacrificing more than 7% on the
quality of the k-means solution.'
acknowledgement: This project has received funding from the Euro-pean Research Council (ERC) under the EuropeanUnion’s Horizon 2020 research and innovation programme (Grant agreement No. 101019564 “The De-sign of Modern Fully Dynamic Data Structures (Mo-DynStruct)” and the Austrian Science Fund (FWF)project
Z 422-N, project “Static and Dynamic Hierar-chical Graph Decompositions”, I 5982-N, and project“Fast Algorithms for a Reactive Network Layer (Re-actNet)”,
P 33775-N, with additional funding from thenetidee SCIENCE Stiftung, 2020–2024.D. Sauplic has received funding from the Euro-pean Union’s Horizon 2020 research and innovation
programme under the Marie Sklodowska-Curie grant agreementNo 101034413.
article_processing_charge: No
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: David
full_name: Saulpic, David
id: f8e48cf0-b0ff-11ed-b0e9-b4c35598f964
last_name: Saulpic
- first_name: Leonhard
full_name: Sidl, Leonhard
id: 8b563fd0-b441-11ee-9101-a3891c61efa6
last_name: Sidl
citation:
ama: 'Henzinger MH, Saulpic D, Sidl L. Experimental evaluation of fully dynamic
k-means via coresets. In: 2024 Proceedings of the Symposium on Algorithm Engineering
and Experiments. Society for Industrial & Applied Mathematics; 2024:220-233.
doi:10.1137/1.9781611977929.17'
apa: 'Henzinger, M. H., Saulpic, D., & Sidl, L. (2024). Experimental evaluation
of fully dynamic k-means via coresets. In 2024 Proceedings of the Symposium
on Algorithm Engineering and Experiments (pp. 220–233). Alexandria, VA, United
States: Society for Industrial & Applied Mathematics. https://doi.org/10.1137/1.9781611977929.17'
chicago: Henzinger, Monika H, David Saulpic, and Leonhard Sidl. “Experimental Evaluation
of Fully Dynamic K-Means via Coresets.” In 2024 Proceedings of the Symposium
on Algorithm Engineering and Experiments, 220–33. Society for Industrial &
Applied Mathematics, 2024. https://doi.org/10.1137/1.9781611977929.17.
ieee: M. H. Henzinger, D. Saulpic, and L. Sidl, “Experimental evaluation of fully
dynamic k-means via coresets,” in 2024 Proceedings of the Symposium on Algorithm
Engineering and Experiments, Alexandria, VA, United States, 2024, pp. 220–233.
ista: 'Henzinger MH, Saulpic D, Sidl L. 2024. Experimental evaluation of fully dynamic
k-means via coresets. 2024 Proceedings of the Symposium on Algorithm Engineering
and Experiments. ALENEX: Workshop on Algorithm Engineering and Experiments, 220–233.'
mla: Henzinger, Monika H., et al. “Experimental Evaluation of Fully Dynamic K-Means
via Coresets.” 2024 Proceedings of the Symposium on Algorithm Engineering and
Experiments, Society for Industrial & Applied Mathematics, 2024, pp. 220–33,
doi:10.1137/1.9781611977929.17.
short: M.H. Henzinger, D. Saulpic, L. Sidl, in:, 2024 Proceedings of the Symposium
on Algorithm Engineering and Experiments, Society for Industrial & Applied
Mathematics, 2024, pp. 220–233.
conference:
end_date: 2024-01-08
location: Alexandria, VA, United States
name: 'ALENEX: Workshop on Algorithm Engineering and Experiments'
start_date: 2024-01-07
date_created: 2024-01-09T16:22:47Z
date_published: 2024-01-04T00:00:00Z
date_updated: 2025-07-15T12:51:52Z
day: '04'
department:
- _id: MoHe
doi: 10.1137/1.9781611977929.17
ec_funded: 1
external_id:
arxiv:
- '2310.18034'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2310.18034
month: '01'
oa: 1
oa_version: Preprint
page: 220-233
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: 34def286-11ca-11ed-8bc3-da5948e1613c
grant_number: Z00422
name: Wittgenstein Award - Monika Henzinger
- _id: bda196b2-d553-11ed-ba76-8e8ee6c21103
grant_number: I05982
name: Static and Dynamic Hierarchical Graph Decompositions
- _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
grant_number: 'P33775 '
name: Fast Algorithms for a Reactive Network Layer
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
call_identifier: H2020
grant_number: '101034413'
name: 'IST-BRIDGE: International postdoctoral program'
publication: 2024 Proceedings of the Symposium on Algorithm Engineering and Experiments
publication_identifier:
eisbn:
- '9781611977929'
publication_status: published
publisher: Society for Industrial & Applied Mathematics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Experimental evaluation of fully dynamic k-means via coresets
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2024'
...
---
_id: '15008'
abstract:
- lang: eng
text: "Oblivious routing is a well-studied paradigm that uses static precomputed
routing tables for selecting routing paths within a network. Existing oblivious
routing schemes with polylogarithmic competitive ratio for general networks are
tree-based, in the sense that routing is performed according to a convex combination
of trees. However, this restriction to trees leads to a construction that has
time quadratic in the size of the network and does not parallelize well. \r\nIn
this paper we study oblivious routing schemes based on electrical routing. In
particular, we show that general networks with n vertices and m edges admit a
routing scheme that has competitive ratio O(log² n) and consists of a convex combination
of only O(√m) electrical routings. This immediately leads to an improved construction
algorithm with time Õ(m^{3/2}) that can also be implemented in parallel with
Õ(√m) depth."
acknowledgement: "Monika Henzinger and A. R. Sricharan: This project has received
funding from the European Research Council (ERC) under the European Union’s Horizon
2020 research and innovation\r\nprogramme (Grant agreement No. 101019564) and the
Austrian Science Fund (FWF) project Z\r\n422-N, project I 5982-N, and project P
33775-N, with additional funding from the netidee SCIENCE Stiftung, 2020–2024.\r\nHarald
Räcke: Research supported by German Research Foundation (DFG), grant 470029389\r\n(FlexNets),
2021-2024.\r\nSushant Sachdeva: SS’s work is supported by an Natural Sciences and
Engineering Research Council of Canada (NSERC) Discovery Grant RGPIN-2018-06398
and a Sloan Research Fellowship."
alternative_title:
- LIPIcs
article_number: '55'
article_processing_charge: No
arxiv: 1
author:
- first_name: Gramoz
full_name: Goranci, Gramoz
last_name: Goranci
- 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: Harald
full_name: Räcke, Harald
last_name: Räcke
- first_name: Sushant
full_name: Sachdeva, Sushant
last_name: Sachdeva
- first_name: A. R.
full_name: Sricharan, A. R.
last_name: Sricharan
citation:
ama: 'Goranci G, Henzinger MH, Räcke H, Sachdeva S, Sricharan AR. Electrical flows
for polylogarithmic competitive oblivious routing. In: 15th Innovations in
Theoretical Computer Science Conference. Vol 287. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik; 2024. doi:10.4230/LIPIcs.ITCS.2024.55'
apa: 'Goranci, G., Henzinger, M. H., Räcke, H., Sachdeva, S., & Sricharan, A.
R. (2024). Electrical flows for polylogarithmic competitive oblivious routing.
In 15th Innovations in Theoretical Computer Science Conference (Vol. 287).
Berkeley, CA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.ITCS.2024.55'
chicago: Goranci, Gramoz, Monika H Henzinger, Harald Räcke, Sushant Sachdeva, and
A. R. Sricharan. “Electrical Flows for Polylogarithmic Competitive Oblivious Routing.”
In 15th Innovations in Theoretical Computer Science Conference, Vol. 287.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.ITCS.2024.55.
ieee: G. Goranci, M. H. Henzinger, H. Räcke, S. Sachdeva, and A. R. Sricharan, “Electrical
flows for polylogarithmic competitive oblivious routing,” in 15th Innovations
in Theoretical Computer Science Conference, Berkeley, CA, United States, 2024,
vol. 287.
ista: 'Goranci G, Henzinger MH, Räcke H, Sachdeva S, Sricharan AR. 2024. Electrical
flows for polylogarithmic competitive oblivious routing. 15th Innovations in Theoretical
Computer Science Conference. ITCS: Innovations in Theoretical Computer Science
Conference, LIPIcs, vol. 287, 55.'
mla: Goranci, Gramoz, et al. “Electrical Flows for Polylogarithmic Competitive Oblivious
Routing.” 15th Innovations in Theoretical Computer Science Conference,
vol. 287, 55, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.ITCS.2024.55.
short: G. Goranci, M.H. Henzinger, H. Räcke, S. Sachdeva, A.R. Sricharan, in:, 15th
Innovations in Theoretical Computer Science Conference, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2024.
conference:
end_date: 2024-02-02
location: Berkeley, CA, United States
name: 'ITCS: Innovations in Theoretical Computer Science Conference'
start_date: 2024-01-30
date_created: 2024-02-18T23:01:02Z
date_published: 2024-01-24T00:00:00Z
date_updated: 2025-07-15T12:51:53Z
day: '24'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ITCS.2024.55
ec_funded: 1
external_id:
arxiv:
- '2303.02491'
file:
- access_level: open_access
checksum: b89716aae6a5599f187897e39de1e53a
content_type: application/pdf
creator: dernst
date_created: 2024-02-26T10:10:48Z
date_updated: 2024-02-26T10:10:48Z
file_id: '15030'
file_name: 2024_LIPICs_Goranci.pdf
file_size: 1054754
relation: main_file
success: 1
file_date_updated: 2024-02-26T10:10:48Z
has_accepted_license: '1'
intvolume: ' 287'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '01'
oa: 1
oa_version: Published Version
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: 34def286-11ca-11ed-8bc3-da5948e1613c
grant_number: Z00422
name: Wittgenstein Award - Monika Henzinger
- _id: bda196b2-d553-11ed-ba76-8e8ee6c21103
grant_number: I05982
name: Static and Dynamic Hierarchical Graph Decompositions
- _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
grant_number: 'P33775 '
name: Fast Algorithms for a Reactive Network Layer
publication: 15th Innovations in Theoretical Computer Science Conference
publication_identifier:
isbn:
- '9783959773096'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Electrical flows for polylogarithmic competitive oblivious routing
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: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 287
year: '2024'
...
---
_id: '14462'
abstract:
- lang: eng
text: "We study fine-grained error bounds for differentially private algorithms
for counting under continual observation. Our main insight is that the matrix
mechanism when using lower-triangular matrices can be used in the continual observation
model. More specifically, we give an explicit factorization for the counting matrix
Mcount and upper bound the error explicitly. We also give a fine-grained analysis,
specifying the exact constant in the upper bound. Our analysis is based on upper
and lower bounds of the completely bounded norm (cb-norm) of Mcount\r\n. Along
the way, we improve the best-known bound of 28 years by Mathias (SIAM Journal
on Matrix Analysis and Applications, 1993) on the cb-norm of Mcount for a large
range of the dimension of Mcount. Furthermore, we are the first to give concrete
error bounds for various problems under continual observation such as binary counting,
maintaining a histogram, releasing an approximately cut-preserving synthetic graph,
many graph-based statistics, and substring and episode counting. Finally, we note
that our result can be used to get a fine-grained error bound for non-interactive
local learning and the first lower bounds on the additive error for (ϵ,δ)-differentially-private
counting under continual observation. Subsequent to this work, Henzinger et al.
(SODA, 2023) showed that our factorization also achieves fine-grained mean-squared
error."
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.\r\n101019564 “The Design of Modern Fully Dynamic Data Structures
(MoDynStruct)” and from the Austrian Science Fund (FWF) project Z 422-N, and project
“Fast Algorithms for a Reactive Network Layer (ReactNet)”, P 33775-N, with additional
funding from the netidee SCIENCE Stiftung, 2020–2024. 2020–2024. JU’s research was
funded by Decanal Research Grant. A part of this work was done when JU was visiting
Indian Statistical Institute, Delhi. The authors would like to thank Rajat Bhatia,
Aleksandar Nikolov, Shanta Laisharam, Vern Paulsen, Ryan Rogers, Abhradeep Thakurta,
and Sarvagya Upadhyay for useful discussions."
alternative_title:
- PMLR
article_processing_charge: No
author:
- first_name: Hendrik
full_name: Fichtenberger, Hendrik
last_name: Fichtenberger
- 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: Jalaj
full_name: Upadhyay, Jalaj
last_name: Upadhyay
citation:
ama: 'Fichtenberger H, Henzinger MH, Upadhyay J. Constant matters: Fine-grained
error bound on differentially private continual observation. In: Proceedings
of the 40th International Conference on Machine Learning. Vol 202. ML Research
Press; 2023:10072-10092.'
apa: 'Fichtenberger, H., Henzinger, M. H., & Upadhyay, J. (2023). Constant matters:
Fine-grained error bound on differentially private continual observation. In Proceedings
of the 40th International Conference on Machine Learning (Vol. 202, pp. 10072–10092).
Honolulu, Hawaii, HI, United States: ML Research Press.'
chicago: 'Fichtenberger, Hendrik, Monika H Henzinger, and Jalaj Upadhyay. “Constant
Matters: Fine-Grained Error Bound on Differentially Private Continual Observation.”
In Proceedings of the 40th International Conference on Machine Learning,
202:10072–92. ML Research Press, 2023.'
ieee: 'H. Fichtenberger, M. H. Henzinger, and J. Upadhyay, “Constant matters: Fine-grained
error bound on differentially private continual observation,” in Proceedings
of the 40th International Conference on Machine Learning, Honolulu, Hawaii,
HI, United States, 2023, vol. 202, pp. 10072–10092.'
ista: 'Fichtenberger H, Henzinger MH, Upadhyay J. 2023. Constant matters: Fine-grained
error bound on differentially private continual observation. Proceedings of the
40th International Conference on Machine Learning. ICML: International Conference
on Machine Learning, PMLR, vol. 202, 10072–10092.'
mla: 'Fichtenberger, Hendrik, et al. “Constant Matters: Fine-Grained Error Bound
on Differentially Private Continual Observation.” Proceedings of the 40th International
Conference on Machine Learning, vol. 202, ML Research Press, 2023, pp. 10072–92.'
short: H. Fichtenberger, M.H. Henzinger, J. Upadhyay, in:, Proceedings of the 40th
International Conference on Machine Learning, ML Research Press, 2023, pp. 10072–10092.
conference:
end_date: 2023-07-29
location: Honolulu, Hawaii, HI, United States
name: 'ICML: International Conference on Machine Learning'
start_date: 2023-07-23
date_created: 2023-10-29T23:01:17Z
date_published: 2023-07-30T00:00:00Z
date_updated: 2025-07-15T12:51:52Z
day: '30'
department:
- _id: MoHe
ec_funded: 1
intvolume: ' 202'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://proceedings.mlr.press/v202/fichtenberger23a/fichtenberger23a.pdf
month: '07'
oa: 1
oa_version: Published Version
page: 10072-10092
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: 34def286-11ca-11ed-8bc3-da5948e1613c
grant_number: Z00422
name: Wittgenstein Award - Monika Henzinger
- _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
grant_number: 'P33775 '
name: Fast Algorithms for a Reactive Network Layer
publication: Proceedings of the 40th International Conference on Machine Learning
publication_identifier:
eissn:
- 2640-3498
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Constant matters: Fine-grained error bound on differentially private continual
observation'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 202
year: '2023'
...
---
_id: '14558'
abstract:
- lang: eng
text: "n the dynamic minimum set cover problem, the challenge is to minimize the
update time while guaranteeing a close-to-optimal min{O(log n), f} approximation
factor. (Throughout, n, m, f , and C are parameters denoting the maximum number
of elements, the number of sets, the frequency, and the cost range.) In the high-frequency
range, when f = Ω(log n) , this was achieved by a deterministic O(log n) -approximation
algorithm with O(f log n) amortized update time by Gupta et al. [Online and dynamic
algorithms for set cover, in Proceedings STOC 2017, ACM, pp. 537–550]. In this
paper we consider the low-frequency range, when f = O(log n) , and obtain deterministic
algorithms with a (1 + ∈)f -approximation ratio and the following guarantees on
the update time. (1) O ((f/∈)-log(Cn)) amortized update time: Prior to our work,
the best approximation ratio guaranteed by deterministic algorithms was O(f2)
of Bhattacharya, Henzinger, and Italiano [Design of dynamic algorithms via primal-dual
method, in Proceedings ICALP 2015, Springer, pp. 206–218]. In contrast, the only
result with O(f) -approximation was that of Abboud et al. [Dynamic set cover:
Improved algorithms and lower bounds, in Proceedings STOC 2019, ACM, pp. 114–125],
who designed a randomized (1+∈)f -approximation algorithm with amortized update
time. (2) O(f2/∈3 + (f/∈2).logC) amortized update time: This result improves the
above update time bound for most values of f\r\n in the low-frequency range, i.e.,
f=o(log n) . It is also the first result that is independent of m\r\n and n. It
subsumes the constant amortized update time of Bhattacharya and Kulkarni [Deterministically
maintaining a (2 + ∈) -approximate minimum vertex cover in O(1/∈2) amortized update
time, in Proceedings SODA 2019, SIAM, pp. 1872–1885] for unweighted dynamic vertex
cover (i.e., when f = 2 and C = 1). (3) O((f/∈3).log2(Cn)) worst-case update time:
No nontrivial worst-case update time was previously known for the dynamic set
cover problem. Our bound subsumes and improves by a logarithmic factor the O(log3n/poly
(∈)) \r\n worst-case update time for the unweighted dynamic vertex cover problem
(i.e., when f = 2\r\n and C =1) of Bhattacharya, Henzinger, and Nanongkai [Fully
dynamic approximate maximum matching and minimum vertex cover in O(log3)n worst
case update time, in Proceedings SODA 2017, SIAM, pp. 470–489]. We achieve our
results via the primal-dual approach, by maintaining a fractional packing solution
as a dual certificate. Prior work in dynamic algorithms that employs the primal-dual
approach uses a local update scheme that maintains relaxed complementary slackness
conditions for every set. For our first result we use instead a global update
scheme that does not always maintain complementary slackness conditions. For our
second result we combine the global and the local update schema. To achieve our
third result we use a hierarchy of background schedulers. It is an interesting
open question whether this background scheduler technique can also be used to
transform algorithms with amortized running time bounds into algorithms with worst-case
running time bounds."
acknowledgement: "This project has received funding from the European Research Council
(ERC) under the European Union's Horizon 2020 research and innovation programme
(grants 715672 and\r\n101019564 ``The Design of Modern Fully Dynamic Data Structures
(MoDynStruct)\"\") and from the Engineering and Physical Sciences Research Council,
UK (EPSRC) under grant EP/S03353X/1. The second author was also supported by 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, project ``Static and Dynamic Hierarchical Graph Decompositions,\"\"I
5982-N, and project Z 422-N. The third author was also supported by the Swedish
Research Council (Reg. No. 2015-04659). The fourth author was also supported by
the Science and Technology Development Fund (FDCT), Macau SAR (file 0014/2022/AFJ,
0085/2022/A, 0143/2020/A3, and SKL-IOTSC-2021-2023)."
article_processing_charge: No
article_type: original
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: Danupon
full_name: Nanongkai, Danupon
last_name: Nanongkai
- first_name: Xiaowei
full_name: Wu, Xiaowei
last_name: Wu
citation:
ama: Bhattacharya S, Henzinger MH, Nanongkai D, Wu X. Deterministic near-optimal
approximation algorithms for dynamic set cover. SIAM Journal on Computing.
2023;52(5):1132-1192. doi:10.1137/21M1428649
apa: Bhattacharya, S., Henzinger, M. H., Nanongkai, D., & Wu, X. (2023). Deterministic
near-optimal approximation algorithms for dynamic set cover. SIAM Journal on
Computing. Society for Industrial and Applied Mathematics. https://doi.org/10.1137/21M1428649
chicago: Bhattacharya, Sayan, Monika H Henzinger, Danupon Nanongkai, and Xiaowei
Wu. “Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover.”
SIAM Journal on Computing. Society for Industrial and Applied Mathematics,
2023. https://doi.org/10.1137/21M1428649.
ieee: S. Bhattacharya, M. H. Henzinger, D. Nanongkai, and X. Wu, “Deterministic
near-optimal approximation algorithms for dynamic set cover,” SIAM Journal
on Computing, vol. 52, no. 5. Society for Industrial and Applied Mathematics,
pp. 1132–1192, 2023.
ista: Bhattacharya S, Henzinger MH, Nanongkai D, Wu X. 2023. Deterministic near-optimal
approximation algorithms for dynamic set cover. SIAM Journal on Computing. 52(5),
1132–1192.
mla: Bhattacharya, Sayan, et al. “Deterministic Near-Optimal Approximation Algorithms
for Dynamic Set Cover.” SIAM Journal on Computing, vol. 52, no. 5, Society
for Industrial and Applied Mathematics, 2023, pp. 1132–92, doi:10.1137/21M1428649.
short: S. Bhattacharya, M.H. Henzinger, D. Nanongkai, X. Wu, SIAM Journal on Computing
52 (2023) 1132–1192.
date_created: 2023-11-19T23:00:56Z
date_published: 2023-10-01T00:00:00Z
date_updated: 2025-07-15T12:51:52Z
day: '01'
department:
- _id: MoHe
doi: 10.1137/21M1428649
ec_funded: 1
intvolume: ' 52'
issue: '5'
language:
- iso: eng
month: '10'
oa_version: None
page: 1132-1192
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
- _id: 34def286-11ca-11ed-8bc3-da5948e1613c
grant_number: Z00422
name: Wittgenstein Award - Monika Henzinger
- _id: bda196b2-d553-11ed-ba76-8e8ee6c21103
grant_number: I05982
name: Static and Dynamic Hierarchical Graph Decompositions
publication: SIAM Journal on Computing
publication_identifier:
eissn:
- 1095-7111
issn:
- 0097-5397
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Deterministic near-optimal approximation algorithms for dynamic set cover
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 52
year: '2023'
...
---
_id: '13236'
abstract:
- lang: eng
text: We present an auction algorithm using multiplicative instead of constant weight
updates to compute a (1−ε)-approximate maximum weight matching (MWM) in a bipartite
graph with n vertices and m edges in time O(mε−1log(ε−1)), matching the running
time of the linear-time approximation algorithm of Duan and Pettie [JACM ’14].
Our algorithm is very simple and it can be extended to give a dynamic data structure
that maintains a (1−ε)-approximate maximum weight matching under (1) one-sided
vertex deletions (with incident edges) and (2) one-sided vertex insertions (with
incident edges sorted by weight) to the other side. The total time time used is
O(mε−1log(ε−1)), where m is the sum of the number of initially existing and inserted
edges.
acknowledgement: The first author thanks to Chandra Chekuri for useful discussions
about this paper. 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. 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.
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Da Wei
full_name: Zheng, Da Wei
last_name: Zheng
- 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: 'Zheng DW, Henzinger MH. Multiplicative auction algorithm for approximate maximum
weight bipartite matching. In: International Conference on Integer Programming
and Combinatorial Optimization. Vol 13904. Springer Nature; 2023:453-465.
doi:10.1007/978-3-031-32726-1_32'
apa: 'Zheng, D. W., & Henzinger, M. H. (2023). Multiplicative auction algorithm
for approximate maximum weight bipartite matching. In International Conference
on Integer Programming and Combinatorial Optimization (Vol. 13904, pp. 453–465).
Madison, WI, United States: Springer Nature. https://doi.org/10.1007/978-3-031-32726-1_32'
chicago: Zheng, Da Wei, and Monika H Henzinger. “Multiplicative Auction Algorithm
for Approximate Maximum Weight Bipartite Matching.” In International Conference
on Integer Programming and Combinatorial Optimization, 13904:453–65. Springer
Nature, 2023. https://doi.org/10.1007/978-3-031-32726-1_32.
ieee: D. W. Zheng and M. H. Henzinger, “Multiplicative auction algorithm for approximate
maximum weight bipartite matching,” in International Conference on Integer
Programming and Combinatorial Optimization, Madison, WI, United States, 2023,
vol. 13904, pp. 453–465.
ista: 'Zheng DW, Henzinger MH. 2023. Multiplicative auction algorithm for approximate
maximum weight bipartite matching. International Conference on Integer Programming
and Combinatorial Optimization. IPCO: Integer Programming and Combinatorial Optimization,
LNCS, vol. 13904, 453–465.'
mla: Zheng, Da Wei, and Monika H. Henzinger. “Multiplicative Auction Algorithm for Approximate
Maximum Weight Bipartite Matching.” International Conference on Integer Programming
and Combinatorial Optimization, vol. 13904, Springer Nature, 2023, pp. 453–65,
doi:10.1007/978-3-031-32726-1_32.
short: D.W. Zheng, M.H. Henzinger, in:, International Conference on Integer Programming
and Combinatorial Optimization, Springer Nature, 2023, pp. 453–465.
conference:
end_date: 2023-06-23
location: Madison, WI, United States
name: 'IPCO: Integer Programming and Combinatorial Optimization'
start_date: 2023-06-21
date_created: 2023-07-16T22:01:11Z
date_published: 2023-05-22T00:00:00Z
date_updated: 2023-07-18T07:08:51Z
day: '22'
department:
- _id: MoHe
doi: 10.1007/978-3-031-32726-1_32
ec_funded: 1
external_id:
arxiv:
- '2301.09217'
intvolume: ' 13904'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2301.09217
month: '05'
oa: 1
oa_version: Preprint
page: 453-465
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: International Conference on Integer Programming and Combinatorial Optimization
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783031327254'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Multiplicative auction algorithm for approximate maximum weight bipartite matching
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 13904
year: '2023'
...
---
_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: '14085'
abstract:
- lang: eng
text: We show an (1+ϵ)-approximation algorithm for maintaining maximum s-t flow
under m edge insertions in m1/2+o(1)ϵ−1/2 amortized update time for directed,
unweighted graphs. This constitutes the first sublinear dynamic maximum flow algorithm
in general sparse graphs with arbitrarily good approximation guarantee.
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.\r\n101019564 “The Design of Modern Fully Dynamic Data Structures
(MoDynStruct)” and from the\r\nAustrian Science Fund (FWF) project “Static and Dynamic
Hierarchical Graph Decompositions”,\r\nI 5982-N, and project “Fast Algorithms for
a Reactive Network Layer (ReactNet)”, P 33775-N, with additional funding from the
netidee SCIENCE Stiftung, 2020–2024.\r\nThis work was done in part while Gramoz
Goranci was at Institute for Theoretical Studies, ETH Zurich, Switzerland. There,
he was supported by Dr. Max Rössler, the Walter Haefner Foundation and the ETH Zürich
Foundation. We also thank Richard Peng, Thatchaphol Saranurak, Sebastian Forster
and Sushant Sachdeva for helpful discussions, and the anonymous reviewers for their
insightful comments."
alternative_title:
- LIPIcs
article_number: '69'
article_processing_charge: Yes
author:
- first_name: Gramoz
full_name: Goranci, Gramoz
last_name: Goranci
- 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: 'Goranci G, Henzinger MH. Efficient data structures for incremental exact and
approximate maximum flow. In: 50th International Colloquium on Automata, Languages,
and Programming. Vol 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
2023. doi:10.4230/LIPIcs.ICALP.2023.69'
apa: 'Goranci, G., & Henzinger, M. H. (2023). Efficient data structures for
incremental exact and approximate maximum flow. In 50th International Colloquium
on Automata, Languages, and Programming (Vol. 261). Paderborn, Germany: Schloss
Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2023.69'
chicago: Goranci, Gramoz, and Monika H Henzinger. “Efficient Data Structures for
Incremental Exact and Approximate Maximum Flow.” In 50th International Colloquium
on Automata, Languages, and Programming, Vol. 261. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2023. https://doi.org/10.4230/LIPIcs.ICALP.2023.69.
ieee: G. Goranci and M. H. Henzinger, “Efficient data structures for incremental
exact and approximate maximum flow,” in 50th International Colloquium on Automata,
Languages, and Programming, Paderborn, Germany, 2023, vol. 261.
ista: 'Goranci G, Henzinger MH. 2023. Efficient data structures for incremental
exact and approximate maximum flow. 50th International Colloquium on Automata,
Languages, and Programming. ICALP: International Colloquium on Automata, Languages,
and Programming, LIPIcs, vol. 261, 69.'
mla: Goranci, Gramoz, and Monika H. Henzinger. “Efficient Data Structures for Incremental
Exact and Approximate Maximum Flow.” 50th International Colloquium on Automata,
Languages, and Programming, vol. 261, 69, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2023, doi:10.4230/LIPIcs.ICALP.2023.69.
short: G. Goranci, M.H. Henzinger, in:, 50th International Colloquium on Automata,
Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2023.
conference:
end_date: 2023-07-14
location: Paderborn, Germany
name: 'ICALP: International Colloquium on Automata, Languages, and Programming'
start_date: 2023-07-10
date_created: 2023-08-20T22:01:14Z
date_published: 2023-07-01T00:00:00Z
date_updated: 2023-08-21T07:00:49Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ICALP.2023.69
ec_funded: 1
external_id:
unknown:
- '2211.09606'
file:
- access_level: open_access
checksum: 074177e815a1656de5d4071c7a3dffa6
content_type: application/pdf
creator: dernst
date_created: 2023-08-21T06:59:05Z
date_updated: 2023-08-21T06:59:05Z
file_id: '14089'
file_name: 2023_LIPIcsICALP_Goranci.pdf
file_size: 875910
relation: main_file
success: 1
file_date_updated: 2023-08-21T06:59:05Z
has_accepted_license: '1'
intvolume: ' 261'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
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: bda196b2-d553-11ed-ba76-8e8ee6c21103
grant_number: I05982
name: Static and Dynamic Hierarchical Graph Decompositions
- _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
grant_number: 'P33775 '
name: Fast Algorithms for a Reactive Network Layer
publication: 50th International Colloquium on Automata, Languages, and Programming
publication_identifier:
isbn:
- '9783959772785'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Efficient data structures for incremental exact and approximate maximum flow
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: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 261
year: '2023'
...
---
_id: '14086'
abstract:
- lang: eng
text: "The maximization of submodular functions have found widespread application
in areas such as machine learning, combinatorial optimization, and economics,
where practitioners often wish to enforce various constraints; the matroid constraint
has been investigated extensively due to its algorithmic properties and expressive
power. Though tight approximation algorithms for general matroid constraints exist
in theory, the running times of such algorithms typically scale quadratically,
and are not practical for truly large scale settings. Recent progress has focused
on fast algorithms for important classes of matroids given in explicit form. Currently,
nearly-linear time algorithms only exist for graphic and partition matroids [Alina
Ene and Huy L. Nguyen, 2019]. In this work, we develop algorithms for monotone
submodular maximization constrained by graphic, transversal matroids, or laminar
matroids in time near-linear in the size of their representation. Our algorithms
achieve an optimal approximation of 1-1/e-ε and both generalize and accelerate
the results of Ene and Nguyen [Alina Ene and Huy L. Nguyen, 2019]. In fact, the
running time of our algorithm cannot be improved within the fast continuous greedy
framework of Badanidiyuru and Vondrák [Ashwinkumar Badanidiyuru and Jan Vondrák,
2014].\r\nTo achieve near-linear running time, we make use of dynamic data structures
that maintain bases with approximate maximum cardinality and weight under certain
element updates. These data structures need to support a weight decrease operation
and a novel Freeze operation that allows the algorithm to freeze elements (i.e.
force to be contained) in its basis regardless of future data structure operations.
For the laminar matroid, we present a new dynamic data structure using the top
tree interface of Alstrup, Holm, de Lichtenberg, and Thorup [Stephen Alstrup et
al., 2005] that maintains the maximum weight basis under insertions and deletions
of elements in O(log n) time. This data structure needs to support certain subtree
query and path update operations that are performed every insertion and deletion
that are non-trivial to handle in conjunction. For the transversal matroid the
Freeze operation corresponds to requiring the data structure to keep a certain
set S of vertices matched, a property that we call S-stability. While there is
a large body of work on dynamic matching algorithms, none are S-stable and maintain
an approximate maximum weight matching under vertex updates. We give the first
such algorithm for bipartite graphs with total running time linear (up to log
factors) in the number of edges."
acknowledgement: " Monika Henzinger: This project has received funding from the European
Research Council\r\n(ERC) under the European Union’s Horizon 2020 research and innovation
programme (Grant\r\nagreement No. 101019564 “The Design of Modern Fully Dynamic
Data Structures (MoDynStruct)” and from the Austrian Science Fund (FWF) project
“Static and Dynamic Hierarchical Graph Decompositions”, I 5982-N, and project “Fast
Algorithms for a Reactive Network Layer (ReactNet)”, P 33775-N, with additional
funding from the netidee SCIENCE Stiftung, 2020–2024. Jan Vondrák: Supported by
NSF Award 2127781."
alternative_title:
- LIPIcs
article_number: '74'
article_processing_charge: Yes
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: Paul
full_name: Liu, Paul
last_name: Liu
- first_name: Jan
full_name: Vondrák, Jan
last_name: Vondrák
- first_name: Da Wei
full_name: Zheng, Da Wei
last_name: Zheng
citation:
ama: 'Henzinger MH, Liu P, Vondrák J, Zheng DW. Faster submodular maximization for
several classes of matroids. In: 50th International Colloquium on Automata,
Languages, and Programming. Vol 261. Schloss Dagstuhl - Leibniz-Zentrum für
Informatik; 2023. doi:10.4230/LIPIcs.ICALP.2023.74'
apa: 'Henzinger, M. H., Liu, P., Vondrák, J., & Zheng, D. W. (2023). Faster
submodular maximization for several classes of matroids. In 50th International
Colloquium on Automata, Languages, and Programming (Vol. 261). Paderborn,
Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2023.74'
chicago: Henzinger, Monika H, Paul Liu, Jan Vondrák, and Da Wei Zheng. “Faster Submodular
Maximization for Several Classes of Matroids.” In 50th International Colloquium
on Automata, Languages, and Programming, Vol. 261. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2023. https://doi.org/10.4230/LIPIcs.ICALP.2023.74.
ieee: M. H. Henzinger, P. Liu, J. Vondrák, and D. W. Zheng, “Faster submodular maximization
for several classes of matroids,” in 50th International Colloquium on Automata,
Languages, and Programming, Paderborn, Germany, 2023, vol. 261.
ista: 'Henzinger MH, Liu P, Vondrák J, Zheng DW. 2023. Faster submodular maximization
for several classes of matroids. 50th International Colloquium on Automata, Languages,
and Programming. ICALP: International Colloquium on Automata, Languages, and Programming,
LIPIcs, vol. 261, 74.'
mla: Henzinger, Monika H., et al. “Faster Submodular Maximization for Several Classes
of Matroids.” 50th International Colloquium on Automata, Languages, and Programming,
vol. 261, 74, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:10.4230/LIPIcs.ICALP.2023.74.
short: M.H. Henzinger, P. Liu, J. Vondrák, D.W. Zheng, in:, 50th International Colloquium
on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für
Informatik, 2023.
conference:
end_date: 2023-07-14
location: Paderborn, Germany
name: 'ICALP: International Colloquium on Automata, Languages, and Programming'
start_date: 2023-07-10
date_created: 2023-08-20T22:01:14Z
date_published: 2023-07-01T00:00:00Z
date_updated: 2023-08-21T07:05:47Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ICALP.2023.74
ec_funded: 1
external_id:
arxiv:
- '2305.00122'
file:
- access_level: open_access
checksum: a5eef225014e003efbfbe4830fdd23cb
content_type: application/pdf
creator: dernst
date_created: 2023-08-21T07:04:36Z
date_updated: 2023-08-21T07:04:36Z
file_id: '14090'
file_name: 2023_LIPIcsICALP_HenzingerM.pdf
file_size: 930943
relation: main_file
success: 1
file_date_updated: 2023-08-21T07:04:36Z
has_accepted_license: '1'
intvolume: ' 261'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
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: bda196b2-d553-11ed-ba76-8e8ee6c21103
grant_number: I05982
name: Static and Dynamic Hierarchical Graph Decompositions
- _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
grant_number: 'P33775 '
name: Fast Algorithms for a Reactive Network Layer
publication: 50th International Colloquium on Automata, Languages, and Programming
publication_identifier:
isbn:
- '9783959772785'
issn:
- '18688969'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Faster submodular maximization for several classes of matroids
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: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 261
year: '2023'
...
---
_id: '12760'
abstract:
- lang: eng
text: "Dynamic programming (DP) is one of the fundamental paradigms in algorithm
design. However,\r\nmany DP algorithms have to fill in large DP tables, represented
by two-dimensional arrays, which causes at least quadratic running times and space
usages. This has led to the development of improved algorithms for special cases
when the DPs satisfy additional properties like, e.g., the Monge property or total
monotonicity.\r\nIn this paper, we consider a new condition which assumes (among
some other technical assumptions) that the rows of the DP table are monotone.
Under this assumption, we introduce\r\na novel data structure for computing (1
+ ϵ)-approximate DP solutions in near-linear time and\r\nspace in the static setting,
and with polylogarithmic update times when the DP entries change\r\ndynamically.
To the best of our knowledge, our new condition is incomparable to previous conditions
and is the first which allows to derive dynamic algorithms based on existing DPs.
Instead of using two-dimensional arrays to store the DP tables, we store the rows
of the DP tables using monotone piecewise constant functions. This allows us to
store length-n DP table rows with entries in [0, W] using only polylog(n, W) bits,
and to perform operations, such as (min, +)-convolution or rounding, on these
functions in polylogarithmic time.\r\nWe further present several applications
of our data structure. For bicriteria versions of k-balanced graph partitioning
and simultaneous source location, we obtain the first dynamic algorithms with
subpolynomial update times, as well as the first static algorithms using only
near-linear time and space. Additionally, we obtain the currently fastest algorithm
for fully dynamic knapsack."
acknowledgement: "Monika Henzinger: This project has received funding from the European
Research Council\r\n(ERC) under the European Union’s Horizon 2020 research and innovation
programme (Grant\r\nagreement 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.\r\nStefan Neumann: This research
is supported by the the ERC Advanced Grant REBOUND (834862) and the EC H2020 RIA
project SoBigData++ (871042).\r\nStefan Schmid: Research supported by Austrian Science
Fund (FWF) project I 5025-N (DELTA), 2020-2024."
alternative_title:
- LIPIcs
article_number: '36'
article_processing_charge: No
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: Stefan
full_name: Neumann, Stefan
last_name: Neumann
- first_name: Harald
full_name: Räcke, Harald
last_name: Räcke
- first_name: Stefan
full_name: Schmid, Stefan
last_name: Schmid
citation:
ama: 'Henzinger MH, Neumann S, Räcke H, Schmid S. Dynamic maintenance of monotone
dynamic programs and applications. In: 40th International Symposium on Theoretical
Aspects of Computer Science. Vol 254. Schloss Dagstuhl - Leibniz-Zentrum für
Informatik; 2023. doi:10.4230/LIPIcs.STACS.2023.36'
apa: 'Henzinger, M. H., Neumann, S., Räcke, H., & Schmid, S. (2023). Dynamic
maintenance of monotone dynamic programs and applications. In 40th International
Symposium on Theoretical Aspects of Computer Science (Vol. 254). Hamburg,
Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.STACS.2023.36'
chicago: Henzinger, Monika H, Stefan Neumann, Harald Räcke, and Stefan Schmid. “Dynamic
Maintenance of Monotone Dynamic Programs and Applications.” In 40th International
Symposium on Theoretical Aspects of Computer Science, Vol. 254. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2023. https://doi.org/10.4230/LIPIcs.STACS.2023.36.
ieee: M. H. Henzinger, S. Neumann, H. Räcke, and S. Schmid, “Dynamic maintenance
of monotone dynamic programs and applications,” in 40th International Symposium
on Theoretical Aspects of Computer Science, Hamburg, Germany, 2023, vol. 254.
ista: 'Henzinger MH, Neumann S, Räcke H, Schmid S. 2023. Dynamic maintenance of
monotone dynamic programs and applications. 40th International Symposium on Theoretical
Aspects of Computer Science. STACS: Symposium on Theoretical Aspects of Computer
Science, LIPIcs, vol. 254, 36.'
mla: Henzinger, Monika H., et al. “Dynamic Maintenance of Monotone Dynamic Programs
and Applications.” 40th International Symposium on Theoretical Aspects of Computer
Science, vol. 254, 36, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2023, doi:10.4230/LIPIcs.STACS.2023.36.
short: M.H. Henzinger, S. Neumann, H. Räcke, S. Schmid, in:, 40th International
Symposium on Theoretical Aspects of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2023.
conference:
end_date: 2023-03-09
location: Hamburg, Germany
name: 'STACS: Symposium on Theoretical Aspects of Computer Science'
start_date: 2023-03-07
date_created: 2023-03-26T22:01:07Z
date_published: 2023-03-01T00:00:00Z
date_updated: 2023-03-27T06:46:27Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.STACS.2023.36
external_id:
arxiv:
- '2301.01744'
file:
- access_level: open_access
checksum: 22141ab8bc55188e2dfff665e5daecbd
content_type: application/pdf
creator: dernst
date_created: 2023-03-27T06:37:22Z
date_updated: 2023-03-27T06:37:22Z
file_id: '12769'
file_name: 2023_LIPICS_HenzingerM.pdf
file_size: 872706
relation: main_file
success: 1
file_date_updated: 2023-03-27T06:37:22Z
has_accepted_license: '1'
intvolume: ' 254'
language:
- iso: eng
month: '03'
oa: 1
oa_version: Published Version
publication: 40th International Symposium on Theoretical Aspects of Computer Science
publication_identifier:
isbn:
- '9783959772662'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Dynamic maintenance of monotone dynamic programs and applications
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: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 254
year: '2023'
...
---
_id: '11662'
abstract:
- lang: eng
text: We give a fully dynamic (Las-Vegas style) algorithm with constant expected
amortized time per update that maintains a proper (Δ +1)-vertex coloring of a
graph with maximum degree at most Δ. This improves upon the previous O(log Δ)-time
algorithm by Bhattacharya et al. (SODA 2018). Our algorithm uses an approach based
on assigning random ranks to vertices and does not need to maintain a hierarchical
graph decomposition. We show that our result does not only have optimal running
time but is also optimal in the sense that already deciding whether a Δ-coloring
exists in a dynamically changing graph with maximum degree at most Δ takes Ω (log
n) time per operation.
acknowledgement: We want to thank an anonymous referee who pointed out a mistake in
our conference paper as well as suggesting a fix using an approach in References.
article_number: '16'
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: Pan
full_name: Peng, Pan
last_name: Peng
citation:
ama: Henzinger MH, Peng P. Constant-time Dynamic (Δ +1)-Coloring. ACM Transactions
on Algorithms. 2022;18(2). doi:10.1145/3501403
apa: Henzinger, M. H., & Peng, P. (2022). Constant-time Dynamic (Δ +1)-Coloring.
ACM Transactions on Algorithms. Association for Computing Machinery (ACM).
https://doi.org/10.1145/3501403
chicago: Henzinger, Monika H, and Pan Peng. “Constant-Time Dynamic (Δ +1)-Coloring.”
ACM Transactions on Algorithms. Association for Computing Machinery (ACM),
2022. https://doi.org/10.1145/3501403.
ieee: M. H. Henzinger and P. Peng, “Constant-time Dynamic (Δ +1)-Coloring,” ACM
Transactions on Algorithms, vol. 18, no. 2. Association for Computing Machinery
(ACM), 2022.
ista: Henzinger MH, Peng P. 2022. Constant-time Dynamic (Δ +1)-Coloring. ACM Transactions
on Algorithms. 18(2), 16.
mla: Henzinger, Monika H., and Pan Peng. “Constant-Time Dynamic (Δ +1)-Coloring.”
ACM Transactions on Algorithms, vol. 18, no. 2, 16, Association for Computing
Machinery (ACM), 2022, doi:10.1145/3501403.
short: M.H. Henzinger, P. Peng, ACM Transactions on Algorithms 18 (2022).
date_created: 2022-07-27T10:58:53Z
date_published: 2022-03-04T00:00:00Z
date_updated: 2022-07-27T11:08:13Z
day: '04'
doi: 10.1145/3501403
extern: '1'
intvolume: ' 18'
issue: '2'
language:
- iso: eng
month: '03'
oa_version: None
publication: ACM Transactions on Algorithms
publication_identifier:
eissn:
- 1549-6333
issn:
- 1549-6325
publication_status: published
publisher: Association for Computing Machinery (ACM)
quality_controlled: '1'
scopus_import: '1'
status: public
title: Constant-time Dynamic (Δ +1)-Coloring
type: journal_article
user_id: 72615eeb-f1f3-11ec-aa25-d4573ddc34fd
volume: 18
year: '2022'
...
---
_id: '14236'
abstract:
- lang: eng
text: We show an $(1+\epsilon)$-approximation algorithm for maintaining maximum
$s$-$t$ flow under $m$ edge insertions in $m^{1/2+o(1)} \epsilon^{-1/2}$ amortized
update time for directed, unweighted graphs. This constitutes the first sublinear
dynamic maximum flow algorithm in general sparse graphs with arbitrarily good
approximation guarantee.
article_number: '2211.09606'
article_processing_charge: No
arxiv: 1
author:
- first_name: Gramoz
full_name: Goranci, Gramoz
last_name: Goranci
- 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: Goranci G, Henzinger MH. Incremental approximate maximum flow in m1/2+o(1)
update time. arXiv. doi:10.48550/arXiv.2211.09606
apa: Goranci, G., & Henzinger, M. H. (n.d.). Incremental approximate maximum
flow in m1/2+o(1) update time. arXiv. https://doi.org/10.48550/arXiv.2211.09606
chicago: Goranci, Gramoz, and Monika H Henzinger. “Incremental Approximate Maximum
Flow in M1/2+o(1) Update Time.” ArXiv, n.d. https://doi.org/10.48550/arXiv.2211.09606.
ieee: G. Goranci and M. H. Henzinger, “Incremental approximate maximum flow in m1/2+o(1)
update time,” arXiv. .
ista: Goranci G, Henzinger MH. Incremental approximate maximum flow in m1/2+o(1)
update time. arXiv, 2211.09606.
mla: Goranci, Gramoz, and Monika H. Henzinger. “Incremental Approximate Maximum
Flow in M1/2+o(1) Update Time.” ArXiv, 2211.09606, doi:10.48550/arXiv.2211.09606.
short: G. Goranci, M.H. Henzinger, ArXiv (n.d.).
date_created: 2023-08-25T15:04:29Z
date_published: 2022-11-17T00:00:00Z
date_updated: 2023-09-04T08:31:19Z
day: '17'
doi: 10.48550/arXiv.2211.09606
extern: '1'
external_id:
arxiv:
- '2211.09606'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2211.09606
month: '11'
oa: 1
oa_version: Preprint
publication: arXiv
publication_status: submitted
status: public
title: Incremental approximate maximum flow in m1/2+o(1) update time
type: preprint
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2022'
...
---
_id: '11808'
abstract:
- lang: eng
text: In recent years, significant advances have been made in the design and analysis
of fully dynamic algorithms. However, these theoretical results have received
very little attention from the practical perspective. Few of the algorithms are
implemented and tested on real datasets, and their practical potential is far
from understood. Here, we present a quick reference guide to recent engineering
and theory results in the area of fully dynamic graph algorithms.
alternative_title:
- LIPIcs
article_number: '1'
article_processing_charge: No
arxiv: 1
author:
- first_name: Kathrin
full_name: Hanauer, Kathrin
last_name: Hanauer
- 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: Christian
full_name: Schulz, Christian
last_name: Schulz
citation:
ama: 'Hanauer K, Henzinger MH, Schulz C. Recent advances in fully dynamic graph
algorithms. In: 1st Symposium on Algorithmic Foundations of Dynamic Networks.
Vol 221. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2022. doi:10.4230/LIPIcs.SAND.2022.1'
apa: 'Hanauer, K., Henzinger, M. H., & Schulz, C. (2022). Recent advances in
fully dynamic graph algorithms. In 1st Symposium on Algorithmic Foundations
of Dynamic Networks (Vol. 221). Virtual: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPIcs.SAND.2022.1'
chicago: Hanauer, Kathrin, Monika H Henzinger, and Christian Schulz. “Recent Advances
in Fully Dynamic Graph Algorithms.” In 1st Symposium on Algorithmic Foundations
of Dynamic Networks, Vol. 221. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2022. https://doi.org/10.4230/LIPIcs.SAND.2022.1.
ieee: K. Hanauer, M. H. Henzinger, and C. Schulz, “Recent advances in fully dynamic
graph algorithms,” in 1st Symposium on Algorithmic Foundations of Dynamic Networks,
Virtual, 2022, vol. 221.
ista: 'Hanauer K, Henzinger MH, Schulz C. 2022. Recent advances in fully dynamic
graph algorithms. 1st Symposium on Algorithmic Foundations of Dynamic Networks.
SAND: Symposium on Algorithmic Foundations of Dynamic Networks, LIPIcs, vol. 221,
1.'
mla: Hanauer, Kathrin, et al. “Recent Advances in Fully Dynamic Graph Algorithms.”
1st Symposium on Algorithmic Foundations of Dynamic Networks, vol. 221,
1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, doi:10.4230/LIPIcs.SAND.2022.1.
short: K. Hanauer, M.H. Henzinger, C. Schulz, in:, 1st Symposium on Algorithmic
Foundations of Dynamic Networks, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2022.
conference:
end_date: 2022-03-30
location: Virtual
name: 'SAND: Symposium on Algorithmic Foundations of Dynamic Networks'
start_date: 2022-03-28
date_created: 2022-08-11T14:35:52Z
date_published: 2022-04-29T00:00:00Z
date_updated: 2023-02-14T08:14:41Z
day: '29'
doi: 10.4230/LIPIcs.SAND.2022.1
extern: '1'
external_id:
arxiv:
- '2102.11169'
intvolume: ' 221'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.4230/LIPIcs.SAND.2022.1
month: '04'
oa: 1
oa_version: Published Version
publication: 1st Symposium on Algorithmic Foundations of Dynamic Networks
publication_identifier:
eissn:
- 1868-8969
isbn:
- '9783959772242'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Recent advances in fully dynamic graph algorithms
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 221
year: '2022'
...
---
_id: '11812'
abstract:
- lang: eng
text: "This paper presents a comprehensive study of algorithms for maintaining the
number of all connected four-vertex subgraphs in a dynamic graph. Specifically,
our algorithms maintain the number of paths of length three in deterministic amortized
O(m^{1/2}) update time, and any other connected four-vertex subgraph which is
not a clique in deterministic amortized update time O(m^{2/3}). Queries can be
answered in constant time. We also study the query times for subgraphs containing
an arbitrary edge that is supplied only with the query as well as the case where
only subgraphs containing a vertex s that is fixed beforehand are considered.
For length-3 paths, paws, 4-cycles, and diamonds our bounds match or are not far
from (conditional) lower bounds: Based on the OMv conjecture we show that any
dynamic algorithm that detects the existence of paws, diamonds, or 4-cycles or
that counts length-3 paths takes update time Ω(m^{1/2-δ}).\r\nAdditionally, for
4-cliques and all connected induced subgraphs, we show a lower bound of Ω(m^{1-δ})
for any small constant δ > 0 for the amortized update time, assuming the static
combinatorial 4-clique conjecture holds. This shows that the O(m) algorithm by
Eppstein et al. [David Eppstein et al., 2012] for these subgraphs cannot be improved
by a polynomial factor."
alternative_title:
- LIPIcs
article_number: '18'
article_processing_charge: No
arxiv: 1
author:
- first_name: Kathrin
full_name: Hanauer, Kathrin
last_name: Hanauer
- 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: Qi Cheng
full_name: Hua, Qi Cheng
last_name: Hua
citation:
ama: 'Hanauer K, Henzinger MH, Hua QC. Fully dynamic four-vertex subgraph counting.
In: 1st Symposium on Algorithmic Foundations of Dynamic Networks. Vol 221.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2022. doi:10.4230/LIPIcs.SAND.2022.18'
apa: 'Hanauer, K., Henzinger, M. H., & Hua, Q. C. (2022). Fully dynamic four-vertex
subgraph counting. In 1st Symposium on Algorithmic Foundations of Dynamic Networks
(Vol. 221). Virtual: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SAND.2022.18'
chicago: Hanauer, Kathrin, Monika H Henzinger, and Qi Cheng Hua. “Fully Dynamic
Four-Vertex Subgraph Counting.” In 1st Symposium on Algorithmic Foundations
of Dynamic Networks, Vol. 221. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2022. https://doi.org/10.4230/LIPIcs.SAND.2022.18.
ieee: K. Hanauer, M. H. Henzinger, and Q. C. Hua, “Fully dynamic four-vertex subgraph
counting,” in 1st Symposium on Algorithmic Foundations of Dynamic Networks,
Virtual, 2022, vol. 221.
ista: 'Hanauer K, Henzinger MH, Hua QC. 2022. Fully dynamic four-vertex subgraph
counting. 1st Symposium on Algorithmic Foundations of Dynamic Networks. SAND:
Symposium on Algorithmic Foundations of Dynamic Networks, LIPIcs, vol. 221, 18.'
mla: Hanauer, Kathrin, et al. “Fully Dynamic Four-Vertex Subgraph Counting.” 1st
Symposium on Algorithmic Foundations of Dynamic Networks, vol. 221, 18, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2022, doi:10.4230/LIPIcs.SAND.2022.18.
short: K. Hanauer, M.H. Henzinger, Q.C. Hua, in:, 1st Symposium on Algorithmic Foundations
of Dynamic Networks, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
conference:
end_date: 2022-04-30
location: Virtual
name: 'SAND: Symposium on Algorithmic Foundations of Dynamic Networks'
start_date: 2022-04-28
date_created: 2022-08-12T06:57:55Z
date_published: 2022-04-29T00:00:00Z
date_updated: 2023-02-14T08:25:42Z
day: '29'
doi: 10.4230/LIPIcs.SAND.2022.18
extern: '1'
external_id:
arxiv:
- '2106.15524'
intvolume: ' 221'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.4230/LIPIcs.SAND.2022.18
month: '04'
oa: 1
oa_version: Published Version
publication: 1st Symposium on Algorithmic Foundations of Dynamic Networks
publication_identifier:
isbn:
- '9783959772242'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Fully dynamic four-vertex subgraph counting
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 221
year: '2022'
...
---
_id: '11918'
abstract:
- lang: eng
text: "Statistics of small subgraph counts such as triangles, four-cycles, and s-t
paths of short lengths reveal important structural properties of the underlying
graph. These problems have been widely studied in social network analysis. In
most relevant applications, the graphs are not only massive but also change dynamically
over time. Most of these problems become hard in the dynamic setting when considering
the worst case. In this paper, we ask whether the question of small subgraph counting
over dynamic graphs is hard also in the average case.\r\n\r\nWe consider the simplest
possible average case model where the updates follow an Erdős-Rényi graph: each
update selects a pair of vertices (u, v) uniformly at random and flips the existence
of the edge (u, v). We develop new lower bounds and matching algorithms in this
model for counting four-cycles, counting triangles through a specified point s,
or a random queried point, and st paths of length 3, 4 and 5. Our results indicate
while computing st paths of length 3, and 4 are easy in the average case with
O(1) update time (note that they are hard in the worst case), it becomes hard
when considering st paths of length 5.\r\n\r\nWe introduce new techniques which
allow us to get average-case hardness for these graph problems from the worst-case
hardness of the Online Matrix vector problem (OMv). Our techniques rely on recent
advances in fine-grained average-case complexity. Our techniques advance this
literature, giving the ability to prove new lower bounds on average-case dynamic
algorithms."
article_processing_charge: No
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: Andrea
full_name: Lincoln, Andrea
last_name: Lincoln
- first_name: Barna
full_name: Saha, Barna
last_name: Saha
citation:
ama: 'Henzinger MH, Lincoln A, Saha B. The complexity of average-case dynamic subgraph
counting. In: 33rd Annual ACM-SIAM Symposium on Discrete Algorithms. Society
for Industrial and Applied Mathematics; 2022:459-498. doi:10.1137/1.9781611977073.23'
apa: 'Henzinger, M. H., Lincoln, A., & Saha, B. (2022). The complexity of average-case
dynamic subgraph counting. In 33rd Annual ACM-SIAM Symposium on Discrete Algorithms
(pp. 459–498). Alexandria, VA, United States: Society for Industrial and Applied
Mathematics. https://doi.org/10.1137/1.9781611977073.23'
chicago: Henzinger, Monika H, Andrea Lincoln, and Barna Saha. “The Complexity of
Average-Case Dynamic Subgraph Counting.” In 33rd Annual ACM-SIAM Symposium
on Discrete Algorithms, 459–98. Society for Industrial and Applied Mathematics,
2022. https://doi.org/10.1137/1.9781611977073.23.
ieee: M. H. Henzinger, A. Lincoln, and B. Saha, “The complexity of average-case
dynamic subgraph counting,” in 33rd Annual ACM-SIAM Symposium on Discrete Algorithms,
Alexandria, VA, United States, 2022, pp. 459–498.
ista: 'Henzinger MH, Lincoln A, Saha B. 2022. The complexity of average-case dynamic
subgraph counting. 33rd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA:
Symposium on Discrete Algorithms, 459–498.'
mla: Henzinger, Monika H., et al. “The Complexity of Average-Case Dynamic Subgraph
Counting.” 33rd Annual ACM-SIAM Symposium on Discrete Algorithms, Society
for Industrial and Applied Mathematics, 2022, pp. 459–98, doi:10.1137/1.9781611977073.23.
short: M.H. Henzinger, A. Lincoln, B. Saha, in:, 33rd Annual ACM-SIAM Symposium
on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2022,
pp. 459–498.
conference:
end_date: 2022-01-12
location: Alexandria, VA, United States
name: 'SODA: Symposium on Discrete Algorithms'
start_date: 2022-01-09
date_created: 2022-08-18T07:26:19Z
date_published: 2022-01-01T00:00:00Z
date_updated: 2023-02-17T11:23:02Z
day: '01'
doi: 10.1137/1.9781611977073.23
extern: '1'
language:
- iso: eng
month: '01'
oa_version: None
page: 459-498
publication: 33rd Annual ACM-SIAM Symposium on Discrete Algorithms
publication_identifier:
eisbn:
- 978-1-61197-707-3
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
scopus_import: '1'
status: public
title: The complexity of average-case dynamic subgraph counting
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2022'
...
---
_id: '11930'
abstract:
- lang: eng
text: We present a practically efficient algorithm for maintaining a global minimum
cut in large dynamic graphs under both edge insertions and deletions. While there
has been theoretical work on this problem, our algorithm is the first implementation
of a fully-dynamic algorithm. The algorithm uses the theoretical foundation and
combines it with efficient and finely-tuned implementations to give an algorithm
that can maintain the global minimum cut of a graph with rapid update times. We
show that our algorithm gives up to multiple orders of magnitude speedup compared
to static approaches both on edge insertions and deletions.
article_processing_charge: No
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: Alexander
full_name: Noe, Alexander
last_name: Noe
- first_name: Christian
full_name: Schulz, Christian
last_name: Schulz
citation:
ama: 'Henzinger MH, Noe A, Schulz C. Practical fully dynamic minimum cut algorithms.
In: 2022 Proceedings of the Symposium on Algorithm Engineering and Experiments.
Society for Industrial and Applied Mathematics; 2022:13-26. doi:10.1137/1.9781611977042.2'
apa: 'Henzinger, M. H., Noe, A., & Schulz, C. (2022). Practical fully dynamic
minimum cut algorithms. In 2022 Proceedings of the Symposium on Algorithm Engineering
and Experiments (pp. 13–26). Alexandria, VA, United States: Society for Industrial
and Applied Mathematics. https://doi.org/10.1137/1.9781611977042.2'
chicago: Henzinger, Monika H, Alexander Noe, and Christian Schulz. “Practical Fully
Dynamic Minimum Cut Algorithms.” In 2022 Proceedings of the Symposium on Algorithm
Engineering and Experiments, 13–26. Society for Industrial and Applied Mathematics,
2022. https://doi.org/10.1137/1.9781611977042.2.
ieee: M. H. Henzinger, A. Noe, and C. Schulz, “Practical fully dynamic minimum cut
algorithms,” in 2022 Proceedings of the Symposium on Algorithm Engineering
and Experiments, Alexandria, VA, United States, 2022, pp. 13–26.
ista: 'Henzinger MH, Noe A, Schulz C. 2022. Practical fully dynamic minimum cut
algorithms. 2022 Proceedings of the Symposium on Algorithm Engineering and Experiments.
ALENEX: Symposium on Algorithm Engineering and Experiments, 13–26.'
mla: Henzinger, Monika H., et al. “Practical Fully Dynamic Minimum Cut Algorithms.”
2022 Proceedings of the Symposium on Algorithm Engineering and Experiments,
Society for Industrial and Applied Mathematics, 2022, pp. 13–26, doi:10.1137/1.9781611977042.2.
short: M.H. Henzinger, A. Noe, C. Schulz, in:, 2022 Proceedings of the Symposium
on Algorithm Engineering and Experiments, Society for Industrial and Applied Mathematics,
2022, pp. 13–26.
conference:
end_date: 2022-01-10
location: Alexandria, VA, United States
name: 'ALENEX: Symposium on Algorithm Engineering and Experiments'
start_date: 2022-01-09
date_created: 2022-08-19T07:27:51Z
date_published: 2022-01-01T00:00:00Z
date_updated: 2023-02-17T13:57:17Z
day: '01'
doi: 10.1137/1.9781611977042.2
extern: '1'
external_id:
arxiv:
- '2101.05033'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2101.05033
month: '01'
oa: 1
oa_version: Preprint
page: 13-26
publication: 2022 Proceedings of the Symposium on Algorithm Engineering and Experiments
publication_identifier:
eisbn:
- 978-1-61197-704-2
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Practical fully dynamic minimum cut algorithms
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2022'
...
---
_id: '11649'
abstract:
- lang: eng
text: 'While operating communication networks adaptively may improve utilization
and performance, frequent adjustments also introduce an algorithmic challenge:
the re-optimization of traffic engineering solutions is time-consuming and may
limit the granularity at which a network can be adjusted. This paper is motivated
by question whether the reactivity of a network can be improved by re-optimizing
solutions dynamically rather than from scratch, especially if inputs such as link
weights do not change significantly. This paper explores to what extent dynamic
algorithms can be used to speed up fundamental tasks in network operations. We
specifically investigate optimizations related to traffic engineering (namely
shortest paths and maximum flow computations), but also consider spanning tree
and matching applications. While prior work on dynamic graph algorithms focusses
on link insertions and deletions, we are interested in the practical problem of
link weight changes. We revisit existing upper bounds in the weight-dynamic model,
and present several novel lower bounds on the amortized runtime for recomputing
solutions. In general, we find that the potential performance gains depend on
the application, and there are also strict limitations on what can be achieved,
even if link weights change only slightly.'
article_processing_charge: No
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: Ami
full_name: Paz, Ami
last_name: Paz
- first_name: Stefan
full_name: Schmid, Stefan
last_name: Schmid
citation:
ama: 'Henzinger MH, Paz A, Schmid S. On the complexity of weight-dynamic network
algorithms. In: IFIP Networking Conference. Institute of Electrical and
Electronics Engineers; 2021. doi:10.23919/ifipnetworking52078.2021.9472803'
apa: 'Henzinger, M. H., Paz, A., & Schmid, S. (2021). On the complexity of weight-dynamic
network algorithms. In IFIP Networking Conference. Espoo and Helsinki,
Finland: Institute of Electrical and Electronics Engineers. https://doi.org/10.23919/ifipnetworking52078.2021.9472803'
chicago: Henzinger, Monika H, Ami Paz, and Stefan Schmid. “On the Complexity of
Weight-Dynamic Network Algorithms.” In IFIP Networking Conference. Institute
of Electrical and Electronics Engineers, 2021. https://doi.org/10.23919/ifipnetworking52078.2021.9472803.
ieee: M. H. Henzinger, A. Paz, and S. Schmid, “On the complexity of weight-dynamic
network algorithms,” in IFIP Networking Conference, Espoo and Helsinki,
Finland, 2021.
ista: 'Henzinger MH, Paz A, Schmid S. 2021. On the complexity of weight-dynamic
network algorithms. IFIP Networking Conference. IFIP: Networking.'
mla: Henzinger, Monika H., et al. “On the Complexity of Weight-Dynamic Network Algorithms.”
IFIP Networking Conference, Institute of Electrical and Electronics Engineers,
2021, doi:10.23919/ifipnetworking52078.2021.9472803.
short: M.H. Henzinger, A. Paz, S. Schmid, in:, IFIP Networking Conference, Institute
of Electrical and Electronics Engineers, 2021.
conference:
end_date: 2021-06-24
location: ' Espoo and Helsinki, Finland'
name: 'IFIP: Networking'
start_date: 2021-06-21
date_created: 2022-07-25T11:13:06Z
date_published: 2021-06-21T00:00:00Z
date_updated: 2023-02-09T09:11:51Z
day: '21'
doi: 10.23919/ifipnetworking52078.2021.9472803
extern: '1'
external_id:
arxiv:
- '2105.13172'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: ' https://doi.org/10.48550/arXiv.2105.13172'
month: '06'
oa: 1
oa_version: Preprint
publication: IFIP Networking Conference
publication_identifier:
eissn:
- 1861-2288
publication_status: published
publisher: Institute of Electrical and Electronics Engineers
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the complexity of weight-dynamic network algorithms
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2021'
...
---
_id: '11663'
abstract:
- lang: eng
text: "Many dynamic graph algorithms have an amortized update time, rather than
a stronger worst-case guarantee. But amortized data structures are not suitable
for real-time systems, where each individual operation has to be executed quickly.
For this reason, there exist many recent randomized results that aim to provide
a guarantee stronger than amortized expected. The strongest possible guarantee
for a randomized algorithm is that it is always correct (Las Vegas) and has high-probability
worst-case update time, which gives a bound on the time for each individual operation
that holds with high probability.\r\n\r\nIn this article, we present the first
polylogarithmic high-probability worst-case time bounds for the dynamic spanner
and the dynamic maximal matching problem.\r\n\r\n(1)\r\n\r\nFor dynamic spanner,
the only known o(n) worst-case bounds were O(n3/4) high-probability worst-case
update time for maintaining a 3-spanner and O(n5/9) for maintaining a 5-spanner.
We give a O(1)k log3 (n) high-probability worst-case time bound for maintaining
a (2k-1)-spanner, which yields the first worst-case polylog update time for all
constant k. (All the results above maintain the optimal tradeoff of stretch 2k-1
and Õ(n1+1/k) edges.)\r\n\r\n(2)\r\n\r\nFor dynamic maximal matching, or dynamic
2-approximate maximum matching, no algorithm with o(n) worst-case time bound was
known and we present an algorithm with O(log 5 (n)) high-probability worst-case
time; similar worst-case bounds existed only for maintaining a matching that was
(2+ϵ)-approximate, and hence not maximal.\r\n\r\nOur results are achieved using
a new approach for converting amortized guarantees to worst-case ones for randomized
data structures by going through a third type of guarantee, which is a middle
ground between the two above: An algorithm is said to have worst-case expected
update time ɑ if for every update σ, the expected time to process σ is at most
ɑ. Although stronger than amortized expected, the worst-case expected guarantee
does not resolve the fundamental problem of amortization: A worst-case expected
update time of O(1) still allows for the possibility that every 1/f(n) updates
requires ϴ (f(n)) time to process, for arbitrarily high f(n). In this article,
we present a black-box reduction that converts any data structure with worst-case
expected update time into one with a high-probability worst-case update time:
The query time remains the same, while the update time increases by a factor of
O(log 2(n)).\r\n\r\nThus, we achieve our results in two steps:\r\n\r\n(1) First,
we show how to convert existing dynamic graph algorithms with amortized expected
polylogarithmic running times into algorithms with worst-case expected polylogarithmic
running times.\r\n\r\n(2) Then, we use our black-box reduction to achieve the
polylogarithmic high-probability worst-case time bound. All our algorithms are
Las-Vegas-type algorithms."
acknowledgement: 'The conference version of this article [10] had an error in the
analysis of the dynamic matching algorithm. In particular, Lemma 4.5 assumed an
independence between adversarial updates to the hierarchy that is in fact true,
but which requires a sophisticated proof. We are very grateful to the anonymous
reviewers of Transactions on Algorithms for pointing out this mistake in our analysis.
The mistake is fixed in Section 4.5. Almost the entire fix is a matter of analysis:
the only change to the algorithm itself is the introduction of responsible bits
in Algorithm 2. The first author would like to thank Mikkel Thorup and Alan Roytman
for a very helpful discussion of the proof of Theorem 1.1.'
article_number: '29'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Aaron
full_name: Bernstein, Aaron
last_name: Bernstein
- first_name: Sebastian
full_name: Forster, Sebastian
last_name: Forster
- 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: Bernstein A, Forster S, Henzinger MH. A deamortization approach for dynamic
spanner and dynamic maximal matching. ACM Transactions on Algorithms. 2021;17(4).
doi:10.1145/3469833
apa: Bernstein, A., Forster, S., & Henzinger, M. H. (2021). A deamortization
approach for dynamic spanner and dynamic maximal matching. ACM Transactions
on Algorithms. Association for Computing Machinery. https://doi.org/10.1145/3469833
chicago: Bernstein, Aaron, Sebastian Forster, and Monika H Henzinger. “A Deamortization
Approach for Dynamic Spanner and Dynamic Maximal Matching.” ACM Transactions
on Algorithms. Association for Computing Machinery, 2021. https://doi.org/10.1145/3469833.
ieee: A. Bernstein, S. Forster, and M. H. Henzinger, “A deamortization approach
for dynamic spanner and dynamic maximal matching,” ACM Transactions on Algorithms,
vol. 17, no. 4. Association for Computing Machinery, 2021.
ista: Bernstein A, Forster S, Henzinger MH. 2021. A deamortization approach for
dynamic spanner and dynamic maximal matching. ACM Transactions on Algorithms.
17(4), 29.
mla: Bernstein, Aaron, et al. “A Deamortization Approach for Dynamic Spanner and
Dynamic Maximal Matching.” ACM Transactions on Algorithms, vol. 17, no.
4, 29, Association for Computing Machinery, 2021, doi:10.1145/3469833.
short: A. Bernstein, S. Forster, M.H. Henzinger, ACM Transactions on Algorithms
17 (2021).
date_created: 2022-07-27T11:09:06Z
date_published: 2021-10-04T00:00:00Z
date_updated: 2022-09-09T11:35:44Z
day: '04'
doi: 10.1145/3469833
extern: '1'
external_id:
arxiv:
- '1810.10932'
intvolume: ' 17'
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1810.10932
month: '10'
oa: 1
oa_version: Preprint
publication: ACM Transactions on Algorithms
publication_identifier:
eissn:
- 1549-6333
issn:
- 1549-6325
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: A deamortization approach for dynamic spanner and dynamic maximal matching
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 17
year: '2021'
...
---
_id: '11756'
abstract:
- lang: eng
text: We give two fully dynamic algorithms that maintain a (1 + ε)-approximation
of the weight M of a minimum spanning forest (MSF) of an n-node graph G with edges
weights in [1, W ], for any ε > 0. (1) Our deterministic algorithm takes O (W
2 log W /ε3) worst-case update time, which is O (1) if both W and ε are constants.
(2) Our randomized (Monte-Carlo style) algorithm works with high probability and
runs in worst-case O (log W /ε4) update time if W = O ((m∗)1/6/log2/3 n), where
m∗ is the minimum number of edges in the graph throughout all the updates. It
works even against an adaptive adversary. We complement our algorithmic results
with two cell-probe lower bounds for dynamically maintaining an approximation
of the weight of an MSF of a graph.
article_number: '104805'
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: Pan
full_name: Peng, Pan
last_name: Peng
citation:
ama: Henzinger MH, Peng P. Constant-time dynamic weight approximation for minimum
spanning forest. Information and Computation. 2021;281(12). doi:10.1016/j.ic.2021.104805
apa: Henzinger, M. H., & Peng, P. (2021). Constant-time dynamic weight approximation
for minimum spanning forest. Information and Computation. Elsevier. https://doi.org/10.1016/j.ic.2021.104805
chicago: Henzinger, Monika H, and Pan Peng. “Constant-Time Dynamic Weight Approximation
for Minimum Spanning Forest.” Information and Computation. Elsevier, 2021.
https://doi.org/10.1016/j.ic.2021.104805.
ieee: M. H. Henzinger and P. Peng, “Constant-time dynamic weight approximation for
minimum spanning forest,” Information and Computation, vol. 281, no. 12.
Elsevier, 2021.
ista: Henzinger MH, Peng P. 2021. Constant-time dynamic weight approximation for
minimum spanning forest. Information and Computation. 281(12), 104805.
mla: Henzinger, Monika H., and Pan Peng. “Constant-Time Dynamic Weight Approximation
for Minimum Spanning Forest.” Information and Computation, vol. 281, no.
12, 104805, Elsevier, 2021, doi:10.1016/j.ic.2021.104805.
short: M.H. Henzinger, P. Peng, Information and Computation 281 (2021).
date_created: 2022-08-08T10:58:29Z
date_published: 2021-12-01T00:00:00Z
date_updated: 2022-09-12T09:29:29Z
day: '01'
doi: 10.1016/j.ic.2021.104805
extern: '1'
external_id:
arxiv:
- '2011.00977'
intvolume: ' 281'
issue: '12'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2011.00977
month: '12'
oa: 1
oa_version: Preprint
publication: Information and Computation
publication_identifier:
issn:
- 0890-5401
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Constant-time dynamic weight approximation for minimum spanning forest
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 281
year: '2021'
...
---
_id: '11771'
abstract:
- lang: eng
text: "Classic dynamic data structure problems maintain a data structure subject
to a sequence S of updates and they answer queries using the latest version of
the data structure, i.e., the data structure after processing the whole sequence.
To handle operations that change the sequence S of updates, Demaine et al. [7]
introduced retroactive data structures (RDS). A retroactive operation modifies
the update sequence S in a given position t, called time, and either creates or
cancels an update in S at time t. A fully retroactive data structure supports
queries at any time t: a query at time t is answered using only the updates of
S up to time t. While efficient RDS have been proposed for classic data structures,
e.g., stack, priority queue and binary search tree, the retroactive version of
graph problems are rarely studied.\r\n\r\nIn this paper we study retroactive graph
problems including connectivity, minimum spanning forest (MSF), maximum degree,
etc. We show that under the OMv conjecture (proposed by Henzinger et al. [15]),
there does not exist fully RDS maintaining connectivity or MSF, or incremental
fully RDS maintaining the maximum degree with \U0001D442(\U0001D45B1−\U0001D716)
time per operation, for any constant \U0001D716>0. Furthermore, We provide RDS
with almost tight time per operation. We give fully RDS for maintaining the maximum
degree, connectivity and MSF in \U0001D442̃ (\U0001D45B) time per operation. We
also give an algorithm for the incremental (insertion-only) fully retroactive
connectivity with \U0001D442̃ (1) time per operation, showing that the lower bound
cannot be extended to this setting.\r\n\r\nWe also study a restricted version
of RDS, where the only change to S is the swap of neighboring updates and show
that for this problem we can beat the above hardness result. This also implies
the first non-trivial dynamic Reeb graph computation algorithm."
alternative_title:
- LNCS
article_processing_charge: No
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: Xiaowei
full_name: Wu, Xiaowei
last_name: Wu
citation:
ama: 'Henzinger MH, Wu X. Upper and lower bounds for fully retroactive graph problems.
In: 17th International Symposium on Algorithms and Data Structures. Vol
12808. Springer Nature; 2021:471–484. doi:10.1007/978-3-030-83508-8_34'
apa: 'Henzinger, M. H., & Wu, X. (2021). Upper and lower bounds for fully retroactive
graph problems. In 17th International Symposium on Algorithms and Data Structures
(Vol. 12808, pp. 471–484). Virtual: Springer Nature. https://doi.org/10.1007/978-3-030-83508-8_34'
chicago: Henzinger, Monika H, and Xiaowei Wu. “Upper and Lower Bounds for Fully
Retroactive Graph Problems.” In 17th International Symposium on Algorithms
and Data Structures, 12808:471–484. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-83508-8_34.
ieee: M. H. Henzinger and X. Wu, “Upper and lower bounds for fully retroactive graph
problems,” in 17th International Symposium on Algorithms and Data Structures,
Virtual, 2021, vol. 12808, pp. 471–484.
ista: 'Henzinger MH, Wu X. 2021. Upper and lower bounds for fully retroactive graph
problems. 17th International Symposium on Algorithms and Data Structures. WADS:
Workshop on Algorithms and Data Structures, LNCS, vol. 12808, 471–484.'
mla: Henzinger, Monika H., and Xiaowei Wu. “Upper and Lower Bounds for Fully Retroactive
Graph Problems.” 17th International Symposium on Algorithms and Data Structures,
vol. 12808, Springer Nature, 2021, pp. 471–484, doi:10.1007/978-3-030-83508-8_34.
short: M.H. Henzinger, X. Wu, in:, 17th International Symposium on Algorithms and
Data Structures, Springer Nature, 2021, pp. 471–484.
conference:
end_date: 2021-08-11
location: Virtual
name: 'WADS: Workshop on Algorithms and Data Structures'
start_date: 2021-08-09
date_created: 2022-08-08T13:01:29Z
date_published: 2021-08-09T00:00:00Z
date_updated: 2023-02-10T08:31:50Z
day: '09'
doi: 10.1007/978-3-030-83508-8_34
extern: '1'
external_id:
arxiv:
- '1910.03332'
intvolume: ' 12808'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1910.03332
month: '08'
oa: 1
oa_version: Preprint
page: 471–484
publication: 17th International Symposium on Algorithms and Data Structures
publication_identifier:
eisbn:
- '9783030835088'
eissn:
- 1611-3349
isbn:
- '9783030835071'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Upper and lower bounds for fully retroactive graph problems
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 12808
year: '2021'
...
---
_id: '9293'
abstract:
- lang: eng
text: 'We consider planning problems for graphs, Markov Decision Processes (MDPs),
and games on graphs in an explicit state space. While graphs represent the most
basic planning model, MDPs represent interaction with nature and games on graphs
represent interaction with an adversarial environment. We consider two planning
problems with k different target sets: (a) the coverage problem asks whether there
is a plan for each individual target set; and (b) the sequential target reachability
problem asks whether the targets can be reached in a given sequence. For the coverage
problem, we present a linear-time algorithm for graphs, and quadratic conditional
lower bound for MDPs and games on graphs. For the sequential target problem, we
present a linear-time algorithm for graphs, a sub-quadratic algorithm for MDPs,
and a quadratic conditional lower bound for games on graphs. Our results with
conditional lower bounds, based on the boolean matrix multiplication (BMM) conjecture
and strong exponential time hypothesis (SETH), establish (i) model-separation
results showing that for the coverage problem MDPs and games on graphs are harder
than graphs, and for the sequential reachability problem games on graphs are harder
than MDPs and graphs; and (ii) problem-separation results showing that for MDPs
the coverage problem is harder than the sequential target problem.'
article_number: '103499'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: 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: Alexander
full_name: Svozil, Alexander
last_name: Svozil
citation:
ama: Chatterjee K, Dvořák W, Henzinger MH, Svozil A. Algorithms and conditional
lower bounds for planning problems. Artificial Intelligence. 2021;297(8).
doi:10.1016/j.artint.2021.103499
apa: Chatterjee, K., Dvořák, W., Henzinger, M. H., & Svozil, A. (2021). Algorithms
and conditional lower bounds for planning problems. Artificial Intelligence.
Elsevier. https://doi.org/10.1016/j.artint.2021.103499
chicago: Chatterjee, Krishnendu, Wolfgang Dvořák, Monika H Henzinger, and Alexander
Svozil. “Algorithms and Conditional Lower Bounds for Planning Problems.” Artificial
Intelligence. Elsevier, 2021. https://doi.org/10.1016/j.artint.2021.103499.
ieee: K. Chatterjee, W. Dvořák, M. H. Henzinger, and A. Svozil, “Algorithms and
conditional lower bounds for planning problems,” Artificial Intelligence,
vol. 297, no. 8. Elsevier, 2021.
ista: Chatterjee K, Dvořák W, Henzinger MH, Svozil A. 2021. Algorithms and conditional
lower bounds for planning problems. Artificial Intelligence. 297(8), 103499.
mla: Chatterjee, Krishnendu, et al. “Algorithms and Conditional Lower Bounds for
Planning Problems.” Artificial Intelligence, vol. 297, no. 8, 103499, Elsevier,
2021, doi:10.1016/j.artint.2021.103499.
short: K. Chatterjee, W. Dvořák, M.H. Henzinger, A. Svozil, Artificial Intelligence
297 (2021).
date_created: 2021-03-28T22:01:40Z
date_published: 2021-03-16T00:00:00Z
date_updated: 2023-09-26T10:41:42Z
day: '16'
department:
- _id: KrCh
doi: 10.1016/j.artint.2021.103499
external_id:
arxiv:
- '1804.07031'
isi:
- '000657537500003'
intvolume: ' 297'
isi: 1
issue: '8'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1804.07031
month: '03'
oa: 1
oa_version: Preprint
publication: Artificial Intelligence
publication_identifier:
issn:
- 0004-3702
publication_status: published
publisher: Elsevier
quality_controlled: '1'
related_material:
record:
- id: '35'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Algorithms and conditional lower bounds for planning problems
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 297
year: '2021'
...