---
_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
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'
...