---
OA_place: publisher
OA_type: gold
_id: '18308'
abstract:
- lang: eng
text: We study in this paper the problem of maintaining a solution to k-median and
k-means clustering in a fully dynamic setting. To do so, we present an algorithm
to efficiently maintain a coreset, a compressed version of the dataset, that allows
easy computation of a clustering solution at query time. Our coreset algorithm
has near-optimal update time of Õ(k) in general metric spaces, which reduces to
Õ(d) in the Euclidean space ℝ^d. The query time is O(k²) in general metrics, and
O(kd) in ℝ^d. To maintain a constant-factor approximation for k-median and k-means
clustering in Euclidean space, this directly leads to an algorithm with update
time Õ(d), and query time Õ(kd + k²). To maintain a O(polylog k)-approximation,
the query time is reduced to Õ(kd).
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 (MoDynStruct Grant agreement No. 101019564) and the Austrian Science Fund
(FWF) grant DOI 10.55776/Z422, grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775
with additional funding from the netidee SCIENCE Stiftung, 2020–2024.\r\nDavid Saulpic:
Work partially done while at ISTA. Received funding from the European Union’s\r\nHorizon
2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement
No 101034413. This work was partially funded by the grant ANR-19-CE48-0016 from
the French National Research Agency (ANR)."
alternative_title:
- LIPIcs
article_number: '100'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Max Dupré
full_name: La Tour, Max Dupré
last_name: La Tour
- 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
citation:
ama: 'La Tour MD, Henzinger M, Saulpic D. Fully dynamic k-means coreset in near-optimal
update time. In: 32nd Annual European Symposium on Algorithms. Vol 308.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.ESA.2024.100'
apa: 'La Tour, M. D., Henzinger, M., & Saulpic, D. (2024). Fully dynamic k-means
coreset in near-optimal update time. In 32nd Annual European Symposium on Algorithms
(Vol. 308). London, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.ESA.2024.100'
chicago: La Tour, Max Dupré, Monika Henzinger, and David Saulpic. “Fully Dynamic
K-Means Coreset in near-Optimal Update Time.” In 32nd Annual European Symposium
on Algorithms, Vol. 308. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2024. https://doi.org/10.4230/LIPIcs.ESA.2024.100.
ieee: M. D. La Tour, M. Henzinger, and D. Saulpic, “Fully dynamic k-means coreset
in near-optimal update time,” in 32nd Annual European Symposium on Algorithms,
London, United Kingdom, 2024, vol. 308.
ista: 'La Tour MD, Henzinger M, Saulpic D. 2024. Fully dynamic k-means coreset in
near-optimal update time. 32nd Annual European Symposium on Algorithms. ESA: European
Symposium on Algorithms, LIPIcs, vol. 308, 100.'
mla: La Tour, Max Dupré, et al. “Fully Dynamic K-Means Coreset in near-Optimal Update
Time.” 32nd Annual European Symposium on Algorithms, vol. 308, 100, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.ESA.2024.100.
short: M.D. La Tour, M. Henzinger, D. Saulpic, in:, 32nd Annual European Symposium
on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
conference:
end_date: 2024-09-04
location: London, United Kingdom
name: 'ESA: European Symposium on Algorithms'
start_date: 2024-09-02
corr_author: '1'
das_tickbox: '0'
date_created: 2024-10-13T22:01:50Z
date_published: 2024-09-23T00:00:00Z
date_updated: 2026-10-21T08:04:40Z
day: '23'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ESA.2024.100
ec_funded: 1
external_id:
arxiv:
- '2406.19926'
isi:
- '001545622400100'
file:
- access_level: open_access
checksum: 8e8c0b13049f11bb0133dfac22e32718
content_type: application/pdf
creator: dernst
date_created: 2024-10-21T09:41:48Z
date_updated: 2024-10-21T09:41:48Z
file_id: '18454'
file_name: 2024_LIPICs_DuprelaTour.pdf
file_size: 873561
relation: main_file
success: 1
file_date_updated: 2024-10-21T09:41:48Z
fulldoi: https://doi.org/10.4230/LIPIcs.ESA.2024.100
has_accepted_license: '1'
intvolume: ' 308'
isi: 1
language:
- iso: eng
month: '09'
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: Efficient algorithms
- _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: 32nd Annual European Symposium on Algorithms
publication_identifier:
isbn:
- '9783959773386'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: Fully dynamic k-means coreset in near-optimal update time
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: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 308
year: '2024'
...
---
OA_place: publisher
OA_type: gold
_id: '18309'
abstract:
- lang: eng
text: 'The problem of designing connectivity oracles supporting vertex failures
is one of the basic data structures problems for undirected graphs. It is already
well understood: previous works [Duan-Pettie STOC''10; Long-Saranurak FOCS''22]
achieve query time linear in the number of failed vertices, and it is conditionally
optimal as long as we require preprocessing time polynomial in the size of the
graph and update time polynomial in the number of failed vertices. We revisit
this problem in the paradigm of algorithms with predictions: we ask if the query
time can be improved if the set of failed vertices can be predicted beforehand
up to a small number of errors. More specifically, we design a data structure
that, given a graph G = (V,E) and a set of vertices predicted to fail D̂ ⊆ V of
size d = |D̂|, preprocesses it in time Õ(d|E|) and then can receive an update
given as the symmetric difference between the predicted and the actual set of
failed vertices D̂△D = (D̂ ⧵ D) ∪ (D ⧵ D̂) of size η = |D̂△D|, process it in time
Õ(η⁴), and after that answer connectivity queries in G ⧵ D in time O(η). Viewed
from another perspective, our data structure provides an improvement over the
state of the art for the fully dynamic subgraph connectivity problem in the sensitivity
setting [Henzinger-Neumann ESA''16]. We argue that the preprocessing time and
query time of our data structure are conditionally optimal under standard fine-grained
complexity assumptions.'
acknowledgement: "Part of this work was done when Evangelos Kosinas was at University
of Ioannina and Adam Polak was at Max Planck Institute of Informatics.\r\n"
alternative_title:
- LIPIcs
article_number: '72'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Bingbing
full_name: Hu, Bingbing
last_name: Hu
- first_name: Evangelos
full_name: Kosinas, Evangelos
id: 4c7f9625-dbbc-11ee-9d86-bdcc2db5a949
last_name: Kosinas
- first_name: Adam
full_name: Polak, Adam
last_name: Polak
citation:
ama: 'Hu B, Kosinas E, Polak A. Connectivity oracles for predictable vertex failures.
In: 32nd Annual European Symposium on Algorithms. Vol 308. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.ESA.2024.72'
apa: 'Hu, B., Kosinas, E., & Polak, A. (2024). Connectivity oracles for predictable
vertex failures. In 32nd Annual European Symposium on Algorithms (Vol.
308). London, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.ESA.2024.72'
chicago: Hu, Bingbing, Evangelos Kosinas, and Adam Polak. “Connectivity Oracles
for Predictable Vertex Failures.” In 32nd Annual European Symposium on Algorithms,
Vol. 308. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.ESA.2024.72.
ieee: B. Hu, E. Kosinas, and A. Polak, “Connectivity oracles for predictable vertex
failures,” in 32nd Annual European Symposium on Algorithms, London, United
Kingdom, 2024, vol. 308.
ista: 'Hu B, Kosinas E, Polak A. 2024. Connectivity oracles for predictable vertex
failures. 32nd Annual European Symposium on Algorithms. ESA: European Symposium
on Algorithms, LIPIcs, vol. 308, 72.'
mla: Hu, Bingbing, et al. “Connectivity Oracles for Predictable Vertex Failures.”
32nd Annual European Symposium on Algorithms, vol. 308, 72, Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.ESA.2024.72.
short: B. Hu, E. Kosinas, A. Polak, in:, 32nd Annual European Symposium on Algorithms,
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
conference:
end_date: 2024-09-04
location: London, United Kingdom
name: 'ESA: European Symposium on Algorithms'
start_date: 2024-09-02
corr_author: '1'
das_tickbox: '0'
date_created: 2024-10-13T22:01:50Z
date_published: 2024-09-01T00:00:00Z
date_updated: 2026-10-21T08:04:56Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ESA.2024.72
external_id:
arxiv:
- '2312.08489'
isi:
- '001545622400072'
file:
- access_level: open_access
checksum: ab1f2f9161549a8763eda15db40e022c
content_type: application/pdf
creator: dernst
date_created: 2024-10-21T10:03:48Z
date_updated: 2024-10-21T10:03:48Z
file_id: '18455'
file_name: 2024_LIPICs_Hu.pdf
file_size: 853914
relation: main_file
success: 1
file_date_updated: 2024-10-21T10:03:48Z
fulldoi: https://doi.org/10.4230/LIPIcs.ESA.2024.72
has_accepted_license: '1'
intvolume: ' 308'
isi: 1
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
publication: 32nd Annual European Symposium on Algorithms
publication_identifier:
isbn:
- '9783959773386'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: Connectivity oracles for predictable vertex failures
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: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 308
year: '2024'
...
---
_id: '18115'
abstract:
- lang: eng
text: "We study the data selection problem, whose aim is to select a small representative
subset of data that can be used to efficiently train a machine learning model.
We present a new data selection approach based on k-means clustering and sensitivity
sampling. Assuming access to an embedding representation of the data with respect
to which the model loss is Holder continuous, our approach provably allows selecting
a set of “typical” k+1/ε2 elements whose average loss corresponds to the average
loss of the whole dataset, up to a multiplicative (1±ε)\r\n factor and an additive
ελΦk, where Φk represents the k-means cost for the input embeddings and λ is the
Holder constant. We furthermore demonstrate the performance and scalability of
our approach on fine-tuning foundation models and show that it outperforms state-of-the-art
methods. We also show how it can be applied on linear regression, leading to a
new sampling strategy that surprisingly matches the performance of leverage score
sampling, while being conceptually simpler and more scalable."
acknowledgement: "Monika Henzinger: 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) and the Austrian Science Fund (FWF) grant
DOI 10.55776/Z422, grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with
additional funding from the netidee SCIENCE Stiftung, 2020–2024. This work was partially
done while David Saulpic was at the Institute for Science and Technology, Austria
(ISTA). David Sauplic has received funding from the European Union’s Horizon 2020
research and innovation programme under the\r\nMarie Sklodowska-Curie grant agreement
No 101034413. Work was done while David Woodruff was visiting Google Research."
alternative_title:
- PMLR
article_processing_charge: No
arxiv: 1
author:
- first_name: Kyriakos
full_name: Axiotis, Kyriakos
last_name: Axiotis
- first_name: Vincent
full_name: Cohen-Addad, Vincent
last_name: Cohen-Addad
- 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: Sammy
full_name: Jerome, Sammy
last_name: Jerome
- first_name: Vahab
full_name: Mirrokni, Vahab
last_name: Mirrokni
- first_name: David
full_name: Saulpic, David
id: f8e48cf0-b0ff-11ed-b0e9-b4c35598f964
last_name: Saulpic
- first_name: David P.
full_name: Woodruff, David P.
last_name: Woodruff
- first_name: Michael
full_name: Wunder, Michael
last_name: Wunder
citation:
ama: 'Axiotis K, Cohen-Addad V, Henzinger M, et al. Data-efficient learning via
clustering-based sensitivity sampling: Foundation models and beyond. In: Proceedings
of the 41st International Conference on Machine Learning. Vol 235. ML Research
Press; 2024:2086-2107.'
apa: 'Axiotis, K., Cohen-Addad, V., Henzinger, M., Jerome, S., Mirrokni, V., Saulpic,
D., … Wunder, M. (2024). Data-efficient learning via clustering-based sensitivity
sampling: Foundation models and beyond. In Proceedings of the 41st International
Conference on Machine Learning (Vol. 235, pp. 2086–2107). Vienna, Austria:
ML Research Press.'
chicago: 'Axiotis, Kyriakos, Vincent Cohen-Addad, Monika Henzinger, Sammy Jerome,
Vahab Mirrokni, David Saulpic, David P. Woodruff, and Michael Wunder. “Data-Efficient
Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond.”
In Proceedings of the 41st International Conference on Machine Learning,
235:2086–2107. ML Research Press, 2024.'
ieee: 'K. Axiotis et al., “Data-efficient learning via clustering-based sensitivity
sampling: Foundation models and beyond,” in Proceedings of the 41st International
Conference on Machine Learning, Vienna, Austria, 2024, vol. 235, pp. 2086–2107.'
ista: 'Axiotis K, Cohen-Addad V, Henzinger M, Jerome S, Mirrokni V, Saulpic D, Woodruff
DP, Wunder M. 2024. Data-efficient learning via clustering-based sensitivity sampling:
Foundation models and beyond. Proceedings of the 41st International Conference
on Machine Learning. ICML: International Conference on Machine Learning, PMLR,
vol. 235, 2086–2107.'
mla: 'Axiotis, Kyriakos, et al. “Data-Efficient Learning via Clustering-Based Sensitivity
Sampling: Foundation Models and Beyond.” Proceedings of the 41st International
Conference on Machine Learning, vol. 235, ML Research Press, 2024, pp. 2086–107.'
short: K. Axiotis, V. Cohen-Addad, M. Henzinger, S. Jerome, V. Mirrokni, D. Saulpic,
D.P. Woodruff, M. Wunder, in:, Proceedings of the 41st International Conference
on Machine Learning, ML Research Press, 2024, pp. 2086–2107.
conference:
end_date: 2024-07-27
location: Vienna, Austria
name: 'ICML: International Conference on Machine Learning'
start_date: 2024-07-21
das_tickbox: '0'
date_created: 2024-09-22T22:01:44Z
date_published: 2024-09-01T00:00:00Z
date_updated: 2026-10-21T08:03:43Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
ec_funded: 1
external_id:
arxiv:
- '2402.17327'
intvolume: ' 235'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2402.17327
month: '09'
oa: 1
oa_version: Published Version
page: 2086-2107
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: Efficient algorithms
- _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: Proceedings of the 41st International Conference on Machine Learning
publication_identifier:
eissn:
- 2640-3498
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: 'Data-efficient learning via clustering-based sensitivity sampling: Foundation
models and beyond'
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 235
year: '2024'
...
---
OA_place: repository
OA_type: free access
_id: '18503'
abstract:
- lang: eng
text: "In 1996, Karger [Kar96] gave a startling randomized algorithm that finds
a minimum-cut in a (weighted) graph in time O(m log3 n) which he termed near-linear
time meaning linear (in the size of the input) times a polylogarthmic factor.
In this paper, we give the first deterministic algorithm which runs in near-linear
time for weighted graphs.\r\nPreviously, the breakthrough results of Kawarabayashi
and Thorup [KT19] gave a near-linear time algorithm for simple graphs (which was
improved to have running time O(m log2 n log log n) in [HRW20].) The main technique
here is a clustering procedure that perfectly preserves minimum cuts. Recently,
Li [Li21] gave an m1+o(1) deterministic minimum-cut algorithm for weighted graphs;
this form of running time has been termed “almost-linear”. Li uses almost-linear
time deterministic expander decompositions which do not perfectly preserve minimum
cuts, but he can use these clusterings to, in a sense, “derandomize” the methods
of Karger.\r\nIn terms of techniques, we provide a structural theorem that says
there exists a sparse clustering that preserves minimum cuts in a weighted graph
with o(1) error. In addition, we construct it deterministically in near linear
time. This was done exactly for simple graphs in [KT19, HRW20] and with polylogarithmic
error for weighted graphs in [Li21]. Extending the techniques in [KT19, HRW20]
to weighted graphs presents significant challenges, and moreover, the algorithm
can only polylogarithmically approximately preserve minimum cuts. A remaining
challenge is to reduce the polylogarithmic-approximate clusterings to 1 + o(1/
log n)-approximate so that they can be applied recursively as in [Li21] over O(log
n) many levels. This is an additional challenge that requires building on properties
of tree-packings in the presence of a wide range of edge weights to, for example,
find sources for local flow computations which identify minimum cuts that cross
clusters."
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. 101019564 “The Design of Modern Fully Dynamic Data Structures (MoDyn-Struct)”
and the Austrian Science Fund (FWF) project Z 422-N, project “Static and Dynamic
Hierarchical Graph Decompositions”, I 5982-N, and project “Fast Algorithms for a
Reactive Network Layer (ReactNet)”, P33775-N, with additional funding from the netidee
SCIENCE Stiftung, 2020–2024.
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: Jason
full_name: Li, Jason
last_name: Li
- first_name: Satish
full_name: Rao, Satish
last_name: Rao
- first_name: Di
full_name: Wang, Di
last_name: Wang
citation:
ama: 'Henzinger M, Li J, Rao S, Wang D. Deterministic near-linear time minimum cut
in weighted graphs. In: 35th Annual ACM-SIAM Symposium on Discrete Algorithms.
Society for Industrial and Applied Mathematics; 2024:3089-3139. doi:10.1137/1.9781611977912.111'
apa: 'Henzinger, M., Li, J., Rao, S., & Wang, D. (2024). Deterministic near-linear
time minimum cut in weighted graphs. In 35th Annual ACM-SIAM Symposium on Discrete
Algorithms (pp. 3089–3139). Alexandria, VA, United States: Society for Industrial
and Applied Mathematics. https://doi.org/10.1137/1.9781611977912.111'
chicago: Henzinger, Monika, Jason Li, Satish Rao, and Di Wang. “Deterministic Near-Linear
Time Minimum Cut in Weighted Graphs.” In 35th Annual ACM-SIAM Symposium on
Discrete Algorithms, 3089–3139. Society for Industrial and Applied Mathematics,
2024. https://doi.org/10.1137/1.9781611977912.111.
ieee: M. Henzinger, J. Li, S. Rao, and D. Wang, “Deterministic near-linear time
minimum cut in weighted graphs,” in 35th Annual ACM-SIAM Symposium on Discrete
Algorithms, Alexandria, VA, United States, 2024, pp. 3089–3139.
ista: 'Henzinger M, Li J, Rao S, Wang D. 2024. Deterministic near-linear time minimum
cut in weighted graphs. 35th Annual ACM-SIAM Symposium on Discrete Algorithms.
SODA: Symposium on Discrete Algorithms, 3089–3139.'
mla: Henzinger, Monika, et al. “Deterministic Near-Linear Time Minimum Cut in Weighted
Graphs.” 35th Annual ACM-SIAM Symposium on Discrete Algorithms, Society
for Industrial and Applied Mathematics, 2024, pp. 3089–139, doi:10.1137/1.9781611977912.111.
short: M. Henzinger, J. Li, S. Rao, D. Wang, in:, 35th Annual ACM-SIAM Symposium
on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2024,
pp. 3089–3139.
conference:
end_date: 2024-01-10
location: Alexandria, VA, United States
name: 'SODA: Symposium on Discrete Algorithms'
start_date: 2024-01-07
corr_author: '1'
das_tickbox: '0'
date_created: 2024-11-04T10:54:21Z
date_published: 2024-01-04T00:00:00Z
date_updated: 2026-10-21T08:05:18Z
day: '04'
department:
- _id: MoHe
doi: 10.1137/1.9781611977912.111
ec_funded: 1
external_id:
arxiv:
- '2401.05627'
fulldoi: https://doi.org/10.1137/1.9781611977912.111
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2401.05627
month: '01'
oa: 1
oa_version: Preprint
page: 3089-3139
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: Efficient algorithms
- _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: 35th Annual ACM-SIAM Symposium on Discrete Algorithms
publication_identifier:
eisbn:
- '9781611977912'
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: yes
title: Deterministic near-linear time minimum cut in weighted graphs
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
year: '2024'
...
---
_id: '18116'
abstract:
- lang: eng
text: 'As a staple of data analysis and unsupervised learning, the problem of private
clustering has been widely studied, under various privacy models. Centralized
differential privacy is the first of them, and the problem has also been studied
for the local and the shuffle variation. In each case, the goal is to design an
algorithm that computes privately a clustering, with the smallest possible error.
The study of each variation gave rise to new algorithm: the landscape of private
clustering algorithm is therefore quite intricate. In this paper, we show that
a 20 year-old algorithm can be slightly modified to work for any of those models.
This provides a unified picture: while matching almost all previously known results,
it allows us to improve some of them, and extend to a new privacy model, the continual
observation setting, where the input is changing over time and the algorithm must
output a new solution at each time step.'
acknowledgement: 'Monika Henzinger: 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) and the Austrian Science Fund (FWF) grant
DOI 10.55776/Z422, grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with
additional funding from the netidee SCIENCE Stiftung, 2020–2024.This work was partially
done while David Saulpic was at the Institute for Science and Technology, Austria
(ISTA). David Sauplic has received funding from the European Union’s Horizon 2020
research and innovation programme under the Marie Sklodowska-Curie grant agreement
No 101034413.'
alternative_title:
- PMLR
article_processing_charge: No
arxiv: 1
author:
- first_name: Max Dupré
full_name: La Tour, Max Dupré
last_name: La Tour
- 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
citation:
ama: 'La Tour MD, Henzinger M, Saulpic D. Making old things new: A unified algorithm
for differentially private clustering. In: Proceedings of the 41st International
Conference on Machine Learning. Vol 235. ML Research Press; 2024:12046-12086.'
apa: 'La Tour, M. D., Henzinger, M., & Saulpic, D. (2024). Making old things
new: A unified algorithm for differentially private clustering. In Proceedings
of the 41st International Conference on Machine Learning (Vol. 235, pp. 12046–12086).
Vienna, Austria: ML Research Press.'
chicago: 'La Tour, Max Dupré, Monika Henzinger, and David Saulpic. “Making Old Things
New: A Unified Algorithm for Differentially Private Clustering.” In Proceedings
of the 41st International Conference on Machine Learning, 235:12046–86. ML
Research Press, 2024.'
ieee: 'M. D. La Tour, M. Henzinger, and D. Saulpic, “Making old things new: A unified
algorithm for differentially private clustering,” in Proceedings of the 41st
International Conference on Machine Learning, Vienna, Austria, 2024, vol.
235, pp. 12046–12086.'
ista: 'La Tour MD, Henzinger M, Saulpic D. 2024. Making old things new: A unified
algorithm for differentially private clustering. Proceedings of the 41st International
Conference on Machine Learning. ICML: International Conference on Machine Learning,
PMLR, vol. 235, 12046–12086.'
mla: 'La Tour, Max Dupré, et al. “Making Old Things New: A Unified Algorithm for
Differentially Private Clustering.” Proceedings of the 41st International Conference
on Machine Learning, vol. 235, ML Research Press, 2024, pp. 12046–86.'
short: M.D. La Tour, M. Henzinger, D. Saulpic, in:, Proceedings of the 41st International
Conference on Machine Learning, ML Research Press, 2024, pp. 12046–12086.
conference:
end_date: 2024-07-27
location: Vienna, Austria
name: 'ICML: International Conference on Machine Learning'
start_date: 2024-07-21
corr_author: '1'
das_tickbox: '0'
date_created: 2024-09-22T22:01:44Z
date_published: 2024-09-01T00:00:00Z
date_updated: 2026-10-21T08:04:04Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
ec_funded: 1
external_id:
arxiv:
- '2406.11649'
intvolume: ' 235'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2406.11649
month: '09'
oa: 1
oa_version: Published Version
page: 12046-12086
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: Efficient algorithms
- _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: Proceedings of the 41st International Conference on Machine Learning
publication_identifier:
eissn:
- 2640-3498
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: 'Making old things new: A unified algorithm for differentially private clustering'
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 235
year: '2024'
...
---
_id: '15253'
abstract:
- lang: eng
text: "We study the problem of maintaining a differentially private decaying sum
under continual observation. We give a unifying framework and an efficient algorithm
for this problem for any sufficiently smooth function. Our algorithm is the first
differentially private algorithm that does not have a multiplicative error for
polynomially decaying weights. Our algorithm improves on all prior works on differentially
private decaying sums under continual observation and recovers exactly the additive
error for the special case of continual counting from Henzinger et al. (SODA 2023)
as a corollary.\r\nOur algorithm is a variant of the matrix mechanism whose error
depends on the γ2 and γF norm of the underlying matrix. We give a constructive
proof for an almost exact upper bound on the γ2 and γF norm and an almost tight
lower bound on the γ2 norm for a large class of lower-triangular matrices. This
is the first non-trivial lower bound for lower-triangular matrices whose non-zero
entries are not all the same. It includes matrices for all continual decaying
sums problems, resulting in an upper bound on the additive error of any differentially
private decaying sums algorithm under continual observation.\r\nWe also explore
some implications of our result in discrepancy theory and operator algebra. Given
the importance of the γ2 norm in computer science and the extensive work in mathematics,
we believe our result will have further applications."
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.101019564 “The Design of Modern Fully Dynamic Data Structures (MoDynStruct)”
and the AustrianScience Fund (FWF) project Z 422-N, project “Static and Dynamic
Hierarchical Graph Decompositions”, I 5982-N, andproject “Fast Algorithms for a
Reactive Network Layer (ReactNet)”, P 33775-N, with additional funding from the
netideeSCIENCE Stiftung, 2020–2024. JU’s research was funded by the Decanal Research Grant. We thank the anonymousreviewers
for their useful feedback and pointing us to the results in Matousek et al
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: Jalaj
full_name: Upadhyay, Jalaj
last_name: Upadhyay
- first_name: Sarvagya
full_name: Upadhyay, Sarvagya
last_name: Upadhyay
citation:
ama: 'Henzinger M, Upadhyay J, Upadhyay S. A unifying framework for differentially
private sums under continual observation. In: Proceedings of the 2024 Annual
ACM-SIAM Symposium on Discrete Algorithms. Vol 2024. Society for Industrial
and Applied Mathematics; 2024:995-1018. doi:10.1137/1.9781611977912.38'
apa: 'Henzinger, M., Upadhyay, J., & Upadhyay, S. (2024). A unifying framework
for differentially private sums under continual observation. In Proceedings
of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (Vol. 2024, pp.
995–1018). Alexandria, VA, United States: Society for Industrial and Applied Mathematics.
https://doi.org/10.1137/1.9781611977912.38'
chicago: Henzinger, Monika, Jalaj Upadhyay, and Sarvagya Upadhyay. “A Unifying Framework
for Differentially Private Sums under Continual Observation.” In Proceedings
of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms, 2024:995–1018.
Society for Industrial and Applied Mathematics, 2024. https://doi.org/10.1137/1.9781611977912.38.
ieee: M. Henzinger, J. Upadhyay, and S. Upadhyay, “A unifying framework for differentially
private sums under continual observation,” in Proceedings of the 2024 Annual
ACM-SIAM Symposium on Discrete Algorithms, Alexandria, VA, United States,
2024, vol. 2024, pp. 995–1018.
ista: 'Henzinger M, Upadhyay J, Upadhyay S. 2024. A unifying framework for differentially
private sums under continual observation. Proceedings of the 2024 Annual ACM-SIAM
Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms vol.
2024, 995–1018.'
mla: Henzinger, Monika, et al. “A Unifying Framework for Differentially Private
Sums under Continual Observation.” Proceedings of the 2024 Annual ACM-SIAM
Symposium on Discrete Algorithms, vol. 2024, Society for Industrial and Applied
Mathematics, 2024, pp. 995–1018, doi:10.1137/1.9781611977912.38.
short: M. Henzinger, J. Upadhyay, S. Upadhyay, in:, Proceedings of the 2024 Annual
ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied
Mathematics, 2024, pp. 995–1018.
conference:
end_date: 2024-01-10
location: Alexandria, VA, United States
name: 'SODA: Symposium on Discrete Algorithms'
start_date: 2024-01-07
corr_author: '1'
das_tickbox: '0'
date_created: 2024-03-31T22:01:13Z
date_published: 2024-01-04T00:00:00Z
date_updated: 2026-10-21T08:03:24Z
day: '04'
department:
- _id: MoHe
doi: 10.1137/1.9781611977912.38
ec_funded: 1
external_id:
arxiv:
- '2307.08970'
fulldoi: https://doi.org/10.1137/1.9781611977912.38
intvolume: ' 2024'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2307.08970
month: '01'
oa: 1
oa_version: Preprint
page: 995-1018
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: Efficient algorithms
- _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: Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms
publication_identifier:
eisbn:
- '9781611977912'
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: A unifying framework for differentially private sums under continual observation
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 2024
year: '2024'
...
---
OA_place: publisher
OA_type: gold
_id: '18928'
abstract:
- lang: eng
text: "Algorithms with predictions is a new research direction that leverages machine
learned predictions for algorithm design. So far a plethora of recent works have
incorporated predictions to improve on worst-case bounds for online problems.
In this paper, we initiate the study of complexity of dynamic data structures
with predictions, including dynamic graph algorithms. Unlike online algorithms,
the goal in dynamic data structures is to maintain the solution efficiently with
every update.\r\nWe investigate three natural models of prediction: (1) δ-accurate
predictions where each predicted request matches the true request with probability
δ, (2) list-accurate predictions where a true request comes from a list of possible
requests, and (3) bounded delay predictions where the true requests are a permutation
of the predicted requests. We give general reductions among the prediction models,
showing that bounded delay is the strongest prediction model, followed by list-accurate,
and δ-accurate.\r\nFurther, we identify two broad problem classes based on lower
bounds due to the Online Matrix Vector (OMv) conjecture. Specifically, we show
that locally correctable dynamic problems have strong conditional lower bounds
for list-accurate predictions that are equivalent to the non-prediction setting,
unless list-accurate predictions are perfect. Moreover, we show that locally reducible
dynamic problems have time complexity that degrades gracefully with the quality
of bounded delay predictions. We categorize problems with known OMv lower bounds
accordingly and give several upper bounds in the delay model that show that our
lower bounds are almost tight.\r\nWe note that concurrent work by v.d.Brand et
al. [SODA '24] and Liu and Srinivas [arXiv:2307.08890] independently study dynamic
graph algorithms with predictions, but their work is mostly focused on showing
upper bounds."
acknowledgement: "Henzinger, Monika: 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) and the Austrian Science Fund (FWF) project
Z 422-N, project I 5982-N, and project P 33775-N, with additional funding from the
netidee SCIENCE Stiftung, 2020-2024.\r\nSaha, Barna: This project is partially supported
by NSF grants 1652303, 1909046, 2112533, and HDR TRIPODS Phase II grant 2217058.\r\nWe
would like to thank Andrea Lincoln for many helpful discussions and insightful comments."
alternative_title:
- LIPIcs
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: Barna
full_name: Saha, Barna
last_name: Saha
- first_name: Martin P.
full_name: Seybold, Martin P.
last_name: Seybold
- first_name: Christopher
full_name: Ye, Christopher
last_name: Ye
citation:
ama: 'Henzinger M, Saha B, Seybold MP, Ye C. On the complexity of algorithms with
predictions for dynamic graph problems. In: 15th Innovations in Theoretical
Computer Science Conference. Vol 287. Schloss Dagstuhl - Leibniz-Zentrum für
Informatik; 2024:62:1-62:25. doi:10.4230/LIPIcs.ITCS.2024.62'
apa: 'Henzinger, M., Saha, B., Seybold, M. P., & Ye, C. (2024). On the complexity
of algorithms with predictions for dynamic graph problems. In 15th Innovations
in Theoretical Computer Science Conference (Vol. 287, p. 62:1-62:25). Berkeley,
CA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ITCS.2024.62'
chicago: Henzinger, Monika, Barna Saha, Martin P. Seybold, and Christopher Ye. “On
the Complexity of Algorithms with Predictions for Dynamic Graph Problems.” In
15th Innovations in Theoretical Computer Science Conference, 287:62:1-62:25.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.ITCS.2024.62.
ieee: M. Henzinger, B. Saha, M. P. Seybold, and C. Ye, “On the complexity of algorithms
with predictions for dynamic graph problems,” in 15th Innovations in Theoretical
Computer Science Conference, Berkeley, CA, United States, 2024, vol. 287,
p. 62:1-62:25.
ista: 'Henzinger M, Saha B, Seybold MP, Ye C. 2024. On the complexity of algorithms
with predictions for dynamic graph problems. 15th Innovations in Theoretical Computer
Science Conference. ITCS: Innovations in Theoretical Computer Science, LIPIcs,
vol. 287, 62:1-62:25.'
mla: Henzinger, Monika, et al. “On the Complexity of Algorithms with Predictions
for Dynamic Graph Problems.” 15th Innovations in Theoretical Computer Science
Conference, vol. 287, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024,
p. 62:1-62:25, doi:10.4230/LIPIcs.ITCS.2024.62.
short: M. Henzinger, B. Saha, M.P. Seybold, C. Ye, in:, 15th Innovations in Theoretical
Computer Science Conference, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2024, p. 62:1-62:25.
conference:
end_date: 2024-02-02
location: Berkeley, CA, United States
name: 'ITCS: Innovations in Theoretical Computer Science'
start_date: 2024-01-30
corr_author: '1'
das_tickbox: '0'
date_created: 2025-01-27T15:33:42Z
date_published: 2024-01-24T00:00:00Z
date_updated: 2026-10-21T08:07:36Z
day: '24'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ITCS.2024.62
ec_funded: 1
external_id:
arxiv:
- '2307.16771'
isi:
- '001300389400062'
file:
- access_level: open_access
checksum: 15085a5b3697a408b92a4a7a27293927
content_type: application/pdf
creator: dernst
date_created: 2025-01-27T15:33:24Z
date_updated: 2025-01-27T15:33:24Z
file_id: '18929'
file_name: 2024_LIPICs_HenzingerMo.pdf
file_size: 1084372
relation: main_file
success: 1
file_date_updated: 2025-01-27T15:33:24Z
fulldoi: https://doi.org/10.4230/LIPIcs.ITCS.2024.62
has_accepted_license: '1'
intvolume: ' 287'
isi: 1
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
page: 62:1-62:25
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: Efficient algorithms
- _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:
eissn:
- 1868-8969
isbn:
- '9783959773096'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: On the complexity of algorithms with predictions for dynamic graph problems
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: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 287
year: '2024'
...
---
OA_place: publisher
OA_type: hybrid
_id: '18906'
abstract:
- lang: eng
text: "Expander decompositions of graphs have significantly advanced the understanding
of many classical graph problems and led to numerous fundamental theoretical results.
However, their adoption in practice has been hindered due to their inherent intricacies
and large hidden factors in their asymptotic running times. Here, we introduce
the first practically efficient algorithm for computing expander decompositions
and their hierarchies and demonstrate its effectiveness and utility by incorporating
it as the core component in a novel solver for the normalized cut graph clustering
objective.\r\nOur extensive experiments on a variety of large graphs show that
our expander-based algorithm outperforms state-of-the-art solvers for normalized
cut with respect to solution quality by a large margin on a variety of graph classes
such as citation, e-mail, and social networks or web graphs while remaining competitive
in running time."
acknowledgement: "Monika Henzinger: This project has received funding from the European
Research\r\nCouncil (ERC) under the European Union’s Horizon 2020 research and innovation
programme (Grant agreement No. 101019564) and the Austrian Science Fund (FWF) grant
DOI 10.55776/Z422, grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with
additional funding from the netidee SCIENCE Stiftung, 2020–2024.\r\nHarald Räcke,
Robin Münk: This project has received funding from the Deutsche Forschungsgemeinschaft
(DFG, German Research Foundation) – 498605858 and 470029389."
article_processing_charge: Yes (in subscription journal)
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: Robin
full_name: Münk, Robin
last_name: Münk
- first_name: Harald
full_name: Räcke, Harald
last_name: Räcke
- first_name: Maximilian
full_name: Vötsch, Maximilian
last_name: Vötsch
citation:
ama: 'Hanauer K, Henzinger M, Münk R, Räcke H, Vötsch M. Expander hierarchies for
normalized cuts on graphs. In: Proceedings of the 30th ACM SIGKDD Conference
on Knowledge Discovery and Data Mining. ACM; 2024:1016-1027. doi:10.1145/3637528.3671978'
apa: 'Hanauer, K., Henzinger, M., Münk, R., Räcke, H., & Vötsch, M. (2024).
Expander hierarchies for normalized cuts on graphs. In Proceedings of the 30th
ACM SIGKDD Conference on Knowledge Discovery and Data Mining (pp. 1016–1027).
Barcelona, Spain: ACM. https://doi.org/10.1145/3637528.3671978'
chicago: Hanauer, Kathrin, Monika Henzinger, Robin Münk, Harald Räcke, and Maximilian
Vötsch. “Expander Hierarchies for Normalized Cuts on Graphs.” In Proceedings
of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining,
1016–27. ACM, 2024. https://doi.org/10.1145/3637528.3671978.
ieee: K. Hanauer, M. Henzinger, R. Münk, H. Räcke, and M. Vötsch, “Expander hierarchies
for normalized cuts on graphs,” in Proceedings of the 30th ACM SIGKDD Conference
on Knowledge Discovery and Data Mining, Barcelona, Spain, 2024, pp. 1016–1027.
ista: 'Hanauer K, Henzinger M, Münk R, Räcke H, Vötsch M. 2024. Expander hierarchies
for normalized cuts on graphs. Proceedings of the 30th ACM SIGKDD Conference on
Knowledge Discovery and Data Mining. KDD: Knowledge Discovery and Data Mining,
1016–1027.'
mla: Hanauer, Kathrin, et al. “Expander Hierarchies for Normalized Cuts on Graphs.”
Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data
Mining, ACM, 2024, pp. 1016–27, doi:10.1145/3637528.3671978.
short: K. Hanauer, M. Henzinger, R. Münk, H. Räcke, M. Vötsch, in:, Proceedings
of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, ACM,
2024, pp. 1016–1027.
conference:
end_date: 2024-08-29
location: Barcelona, Spain
name: 'KDD: Knowledge Discovery and Data Mining'
start_date: 2024-08-05
das_tickbox: '0'
date_created: 2025-01-27T13:20:26Z
date_published: 2024-09-01T00:00:00Z
date_updated: 2026-10-21T08:06:58Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.1145/3637528.3671978
ec_funded: 1
external_id:
isi:
- '001324524201013'
file:
- access_level: open_access
checksum: 1265d5cf6aa5f94157631651723c4a2b
content_type: application/pdf
creator: dernst
date_created: 2025-01-27T13:25:23Z
date_updated: 2025-01-27T13:25:23Z
file_id: '18907'
file_name: 2024_ACMKDD_Hanauer.pdf
file_size: 1450331
relation: main_file
success: 1
file_date_updated: 2025-01-27T13:25:23Z
fulldoi: https://doi.org/10.1145/3637528.3671978
has_accepted_license: '1'
isi: 1
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
page: 1016-1027
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: Efficient algorithms
- _id: bda196b2-d553-11ed-ba76-8e8ee6c21103
grant_number: I05982
name: Static and Dynamic Hierarchical Graph Decompositions
publication: Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery
and Data Mining
publication_identifier:
isbn:
- '9798400704901'
publication_status: published
publisher: ACM
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: yes
title: Expander hierarchies for normalized cuts on graphs
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
year: '2024'
...
---
OA_place: publisher
OA_type: hybrid
_id: '17188'
abstract:
- lang: eng
text: "In a delegation problem, a principal P with commitment power tries to pick
one out of \U0001D45B options.\r\nEach option is drawn independently from a known
distribution. Instead of inspecting the options\r\nherself, P delegates the information
acquisition to a rational and self-interested agent A. After\r\ninspection, A
proposes one of the options, and P can accept or reject.\r\nDelegation is a classic
setting in economic information design with many prominent applications,\r\nbut
the computational problems are only poorly understood. In this paper, we study
a natural\r\nonline variant of delegation, in which the agent searches through
the options in an online fashion.\r\nFor each option, he has to irrevocably decide
if he wants to propose the current option or discard\r\nit, before seeing information
on the next option(s). How can we design algorithms for P that\r\napproximate
the utility of her best option in hindsight?\r\nWe show that in general P can
obtain a Θ(1∕\U0001D45B)-approximation and extend this result to ratios\r\nof
Θ(\U0001D458∕\U0001D45B) in case (1) A has a lookahead of \U0001D458 rounds, or
(2) A can propose up to \U0001D458 different\r\noptions. We provide fine-grained
bounds independent of \U0001D45B based on three parameters. If the ratio\r\nof
maximum and minimum utility for A is bounded by a factor \U0001D6FC, we obtain
an Ω(loglog \U0001D6FC∕ log \U0001D6FC)-\r\napproximation algorithm, and we show
that this is best possible. Additionally, if P cannot\r\ndistinguish options with
the same value for herself, we show that ratios polynomial in 1∕\U0001D6FC cannot\r\nbe
avoided. If there are at most \U0001D6FD different utility values for A, we show
a Θ(1∕\U0001D6FD)-approximation.\r\nIf the utilities of P and A for each option
are related by a factor \U0001D6FE, we obtain an Ω(1∕ log \U0001D6FE)-\r\napproximation,
where \U0001D442(log log \U0001D6FE∕ log \U0001D6FE) is best possible."
acknowledgement: Hahn gratefully acknowledges the support of GIF grant I-1419-118.4/2017.
Hoefer gratefully acknowledges the support of GIF grant I-1419-118.4/2017, DFG Research
Unit ADYN (project number 411362735), and DFG grant Ho 3831/9-1 (project number
514505843).
article_number: '104171'
article_processing_charge: Yes (in subscription journal)
article_type: original
arxiv: 1
author:
- first_name: Pirmin
full_name: Braun, Pirmin
last_name: Braun
- first_name: Niklas
full_name: Hahn, Niklas
id: 0a01c7b2-b823-11ed-9928-cc3f874f9ffd
last_name: Hahn
- first_name: Martin
full_name: Hoefer, Martin
last_name: Hoefer
- first_name: Conrad
full_name: Schecker, Conrad
last_name: Schecker
citation:
ama: Braun P, Hahn N, Hoefer M, Schecker C. Delegated online search. Artificial
Intelligence. 2024;334. doi:10.1016/j.artint.2024.104171
apa: Braun, P., Hahn, N., Hoefer, M., & Schecker, C. (2024). Delegated online
search. Artificial Intelligence. Elsevier. https://doi.org/10.1016/j.artint.2024.104171
chicago: Braun, Pirmin, Niklas Hahn, Martin Hoefer, and Conrad Schecker. “Delegated
Online Search.” Artificial Intelligence. Elsevier, 2024. https://doi.org/10.1016/j.artint.2024.104171.
ieee: P. Braun, N. Hahn, M. Hoefer, and C. Schecker, “Delegated online search,”
Artificial Intelligence, vol. 334. Elsevier, 2024.
ista: Braun P, Hahn N, Hoefer M, Schecker C. 2024. Delegated online search. Artificial
Intelligence. 334, 104171.
mla: Braun, Pirmin, et al. “Delegated Online Search.” Artificial Intelligence,
vol. 334, 104171, Elsevier, 2024, doi:10.1016/j.artint.2024.104171.
short: P. Braun, N. Hahn, M. Hoefer, C. Schecker, Artificial Intelligence 334 (2024).
corr_author: '1'
das_tickbox: '1'
dataavailabilitystatement: "No data was used for the research described in the article.\r\n"
date_created: 2024-06-30T22:01:05Z
date_published: 2024-09-01T00:00:00Z
date_updated: 2026-10-21T08:06:15Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.1016/j.artint.2024.104171
external_id:
arxiv:
- '2203.01084'
isi:
- '001260448100001'
file:
- access_level: open_access
checksum: f02a56bc7ea88f41fcc68968e4ceddf3
content_type: application/pdf
creator: dernst
date_created: 2025-01-09T10:45:24Z
date_updated: 2025-01-09T10:45:24Z
file_id: '18806'
file_name: 2024_ArtificialIntelligence_Braun.pdf
file_size: 772226
relation: main_file
success: 1
file_date_updated: 2025-01-09T10:45:24Z
fulldoi: https://doi.org/10.1016/j.artint.2024.104171
has_accepted_license: '1'
intvolume: ' 334'
isi: 1
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
publication: Artificial Intelligence
publication_identifier:
issn:
- 0004-3702
publication_status: published
publisher: Elsevier
quality_controlled: '1'
researchdata_availability: not applicable
scopus_import: '1'
status: public
supplementarymaterial: no
title: Delegated online search
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 334
year: '2024'
...
---
OA_type: closed access
_id: '18922'
abstract:
- lang: eng
text: 'Let G be a directed graph with m edges and n vertices. We present a deterministic
linear-time algorithm for computing the 3-edge-connected components of G. This
is a significant improvement over the previous best bound by Georgiadis et al.
[SODA 2023], which is Õ(m√{m}) and randomized. Our result is based on a novel
characterization of 2-edge cuts in directed graphs and on a new technique that
exploits the concept of divergent spanning trees and 2-connectivity-light graphs,
and requires a careful modification of the minset-poset technique of Gabow [TALG
2016]. As a side result, our new technique yields also an oracle for providing
in constant time a minimum edge-cut for any two vertices that are not 3-edge-connected.
The oracle uses space O(n) and can be built in O(mlog n) time: given two query
vertices, it determines in constant time whether they are 3-edge-connected, or
provides a k-edge cut, with k≤ 2, that separates them.'
acknowledgement: "Giuseppe F. Italiano was partially supported by the Italian Ministry
of\r\nUniversity and Reseach under PRIN Project n. 2022TS4Y3N - EXPAND: scalable
algorithms for EXPloratory Analyses of heterogeneous and dynamic Networked Data.\r\n"
article_processing_charge: No
author:
- first_name: Loukas
full_name: Georgiadis, Loukas
last_name: Georgiadis
- first_name: Giuseppe F.
full_name: Italiano, Giuseppe F.
last_name: Italiano
- first_name: Evangelos
full_name: Kosinas, Evangelos
id: 4c7f9625-dbbc-11ee-9d86-bdcc2db5a949
last_name: Kosinas
citation:
ama: 'Georgiadis L, Italiano GF, Kosinas E. Computing the 3-edge-connected components
of directed graphs in linear time. In: 65th Annual Symposium on Foundations
of Computer Science. IEEE; 2024:62-85. doi:10.1109/focs61266.2024.00015'
apa: 'Georgiadis, L., Italiano, G. F., & Kosinas, E. (2024). Computing the 3-edge-connected
components of directed graphs in linear time. In 65th Annual Symposium on Foundations
of Computer Science (pp. 62–85). Chicago, IL, United States: IEEE. https://doi.org/10.1109/focs61266.2024.00015'
chicago: Georgiadis, Loukas, Giuseppe F. Italiano, and Evangelos Kosinas. “Computing
the 3-Edge-Connected Components of Directed Graphs in Linear Time.” In 65th
Annual Symposium on Foundations of Computer Science, 62–85. IEEE, 2024. https://doi.org/10.1109/focs61266.2024.00015.
ieee: L. Georgiadis, G. F. Italiano, and E. Kosinas, “Computing the 3-edge-connected
components of directed graphs in linear time,” in 65th Annual Symposium on
Foundations of Computer Science, Chicago, IL, United States, 2024, pp. 62–85.
ista: 'Georgiadis L, Italiano GF, Kosinas E. 2024. Computing the 3-edge-connected
components of directed graphs in linear time. 65th Annual Symposium on Foundations
of Computer Science. FOCS: Foundations of Computer Science, 62–85.'
mla: Georgiadis, Loukas, et al. “Computing the 3-Edge-Connected Components of Directed
Graphs in Linear Time.” 65th Annual Symposium on Foundations of Computer Science,
IEEE, 2024, pp. 62–85, doi:10.1109/focs61266.2024.00015.
short: L. Georgiadis, G.F. Italiano, E. Kosinas, in:, 65th Annual Symposium on Foundations
of Computer Science, IEEE, 2024, pp. 62–85.
conference:
end_date: 2024-10-30
location: Chicago, IL, United States
name: 'FOCS: Foundations of Computer Science'
start_date: 2024-10-27
corr_author: '1'
das_tickbox: '0'
date_created: 2025-01-27T14:50:23Z
date_published: 2024-10-01T00:00:00Z
date_updated: 2026-10-21T08:07:18Z
day: '01'
department:
- _id: MoHe
doi: 10.1109/focs61266.2024.00015
external_id:
isi:
- '001419526400005'
fulldoi: https://doi.org/10.1109/focs61266.2024.00015
isi: 1
language:
- iso: eng
month: '10'
oa_version: None
page: 62-85
publication: 65th Annual Symposium on Foundations of Computer Science
publication_identifier:
isbn:
- '9798331516741'
publication_status: published
publisher: IEEE
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: Computing the 3-edge-connected components of directed graphs in linear time
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
year: '2024'
...
---
_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 M, 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., 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, 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. 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 M, 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, 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. 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
corr_author: '1'
date_created: 2023-03-26T22:01:07Z
date_published: 2023-03-01T00:00:00Z
date_updated: 2025-09-09T12:22:44Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.STACS.2023.36
ec_funded: 1
external_id:
arxiv:
- '2301.01744'
isi:
- '001532693100036'
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
fulldoi: https://doi.org/10.4230/LIPIcs.STACS.2023.36
has_accepted_license: '1'
intvolume: ' 254'
isi: 1
language:
- iso: eng
month: '03'
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: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
grant_number: P33775
name: Fast Algorithms for a Reactive Network Layer
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: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 254
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 M, 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., 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, 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. 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 M, Jin B, Peng R, Williamson DP. 2023. A combinatorial cut-toggling
algorithm for solving Laplacian linear systems. Algorithmica. 85, 2680–3716.
mla: Henzinger, Monika, 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. 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: 2025-04-15T06:24:05Z
day: '01'
department:
- _id: MoHe
doi: 10.1007/s00453-023-01154-8
ec_funded: 1
external_id:
arxiv:
- '2010.16316'
isi:
- '001041254900002'
fulldoi: https://doi.org/10.1007/s00453-023-01154-8
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
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 M. 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. (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 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. 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 M. 2023. Efficient data structures for incremental exact
and approximate maximum flow. 50th International Colloquium on Automata, Languages,
and Programming. ICALP: Automata, Languages and Programming, LIPIcs, vol. 261,
69.'
mla: Goranci, Gramoz, and Monika 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. 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: Automata, Languages and Programming'
start_date: 2023-07-10
corr_author: '1'
date_created: 2023-08-20T22:01:14Z
date_published: 2023-07-01T00:00:00Z
date_updated: 2025-06-04T07:19:37Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ICALP.2023.69
ec_funded: 1
external_id:
arxiv:
- '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
fulldoi: https://doi.org/10.4230/LIPIcs.ICALP.2023.69
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 M, 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., 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, 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. 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 M, 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: Automata, Languages and Programming, LIPIcs, vol. 261,
74.'
mla: Henzinger, Monika, 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. 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: Automata, Languages and Programming'
start_date: 2023-07-10
corr_author: '1'
date_created: 2023-08-20T22:01:14Z
date_published: 2023-07-01T00:00:00Z
date_updated: 2025-07-10T11:50:45Z
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
fulldoi: https://doi.org/10.4230/LIPIcs.ICALP.2023.74
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: 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: '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
arxiv: 1
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 M, 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., & 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 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. 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 M, 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. 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
corr_author: '1'
date_created: 2023-10-29T23:01:17Z
date_published: 2023-07-30T00:00:00Z
date_updated: 2026-06-18T17:35:42Z
day: '30'
ddc:
- '000'
department:
- _id: MoHe
ec_funded: 1
external_id:
arxiv:
- '2202.11205'
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: Efficient algorithms
- _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 M, 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., 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 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. 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 M, 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. 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-09-09T13:19:49Z
day: '01'
department:
- _id: MoHe
doi: 10.1137/21M1428649
ec_funded: 1
external_id:
isi:
- '001116719500002'
fulldoi: https://doi.org/10.1137/21M1428649
intvolume: ' 52'
isi: 1
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: Efficient algorithms
- _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: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 52
year: '2023'
...
---
_id: '14768'
abstract:
- lang: eng
text: 'In all state-of-the-art sketching and coreset techniques for clustering,
as well as in the best known fixed-parameter tractable approximation algorithms,
randomness plays a key role. For the classic k-median and k-means problems, there
are no known deterministic dimensionality reduction procedure or coreset construction
that avoid an exponential dependency on the input dimension d, the precision parameter
$\varepsilon^{-1}$ or k. Furthermore, there is no coreset construction that succeeds
with probability $1-1/n$ and whose size does not depend on the number of input
points, n. This has led researchers in the area to ask what is the power of randomness
for clustering sketches [Feldman WIREs Data Mining Knowl. Discov’20].Similarly,
the best approximation ratio achievable deterministically without a complexity
exponential in the dimension are $1+\sqrt{2}$ for k-median [Cohen-Addad, Esfandiari,
Mirrokni, Narayanan, STOC’22] and 6.12903 for k-means [Grandoni, Ostrovsky, Rabani,
Schulman, Venkat, Inf. Process. Lett.’22]. Those are the best results, even when
allowing a complexity FPT in the number of clusters k: this stands in sharp contrast
with the $(1+\varepsilon)$-approximation achievable in that case, when allowing
randomization.In this paper, we provide deterministic sketches constructions for
clustering, whose size bounds are close to the best-known randomized ones. We
show how to compute a dimension reduction onto $\varepsilon^{-O(1)} \log k$ dimensions
in time $k^{O\left(\varepsilon^{-O(1)}+\log \log k\right)}$ poly $(n d)$, and
how to build a coreset of size $O\left(k^{2} \log ^{3} k \varepsilon^{-O(1)}\right)$
in time $2^{\varepsilon^{O(1)} k \log ^{3} k}+k^{O\left(\varepsilon^{-O(1)}+\log
\log k\right)}$ poly $(n d)$. In the case where k is small, this answers an open
question of [Feldman WIDM’20] and [Munteanu and Schwiegelshohn, Künstliche Intell.
’18] on whether it is possible to efficiently compute coresets deterministically.We
also construct a deterministic algorithm for computing $(1+$ $\varepsilon)$-approximation
to k-median and k-means in high dimensional Euclidean spaces in time $2^{k^{2}
\log ^{3} k / \varepsilon^{O(1)}}$ poly $(n d)$, close to the best randomized
complexity of $2^{(k / \varepsilon)^{O(1)}}$ nd (see [Kumar, Sabharwal, Sen, JACM
10] and [Bhattacharya, Jaiswal, Kumar, TCS’18]).Furthermore, our new insights
on sketches also yield a randomized coreset construction that uses uniform sampling,
that immediately improves over the recent results of [Braverman et al. FOCS ’22]
by a factor k.'
acknowledgement: "D. Sauplic has received funding from the European Union’s Horizon
2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement
No 101034413, and Grant agreement No. 101019564 “The Design of Modern Fully Dynamic
Data Structures (MoDynStruct)”.\r\nC. Schwiegelshohn acknowledges the support of
the Independent Research Fund Denmark (DFF) under a Sapere Aude Research Leader
grant No 1051-00106B."
article_processing_charge: No
arxiv: 1
author:
- first_name: Vincent
full_name: Cohen-Addad, Vincent
last_name: Cohen-Addad
- first_name: David
full_name: Saulpic, David
id: f8e48cf0-b0ff-11ed-b0e9-b4c35598f964
last_name: Saulpic
- first_name: Chris
full_name: Schwiegelshohn, Chris
last_name: Schwiegelshohn
citation:
ama: 'Cohen-Addad V, Saulpic D, Schwiegelshohn C. Deterministic clustering in high
dimensional spaces: Sketches and approximation. In: 2023 IEEE 64th Annual Symposium
on Foundations of Computer Science. IEEE; 2023:1105-1130. doi:10.1109/focs57990.2023.00066'
apa: 'Cohen-Addad, V., Saulpic, D., & Schwiegelshohn, C. (2023). Deterministic
clustering in high dimensional spaces: Sketches and approximation. In 2023
IEEE 64th Annual Symposium on Foundations of Computer Science (pp. 1105–1130).
Santa Cruz, CA, United States: IEEE. https://doi.org/10.1109/focs57990.2023.00066'
chicago: 'Cohen-Addad, Vincent, David Saulpic, and Chris Schwiegelshohn. “Deterministic
Clustering in High Dimensional Spaces: Sketches and Approximation.” In 2023
IEEE 64th Annual Symposium on Foundations of Computer Science, 1105–30. IEEE,
2023. https://doi.org/10.1109/focs57990.2023.00066.'
ieee: 'V. Cohen-Addad, D. Saulpic, and C. Schwiegelshohn, “Deterministic clustering
in high dimensional spaces: Sketches and approximation,” in 2023 IEEE 64th
Annual Symposium on Foundations of Computer Science, Santa Cruz, CA, United
States, 2023, pp. 1105–1130.'
ista: 'Cohen-Addad V, Saulpic D, Schwiegelshohn C. 2023. Deterministic clustering
in high dimensional spaces: Sketches and approximation. 2023 IEEE 64th Annual
Symposium on Foundations of Computer Science. FOCS: Foundations of Computer Science,
1105–1130.'
mla: 'Cohen-Addad, Vincent, et al. “Deterministic Clustering in High Dimensional
Spaces: Sketches and Approximation.” 2023 IEEE 64th Annual Symposium on Foundations
of Computer Science, IEEE, 2023, pp. 1105–30, doi:10.1109/focs57990.2023.00066.'
short: V. Cohen-Addad, D. Saulpic, C. Schwiegelshohn, in:, 2023 IEEE 64th Annual
Symposium on Foundations of Computer Science, IEEE, 2023, pp. 1105–1130.
conference:
end_date: 2023-11-09
location: Santa Cruz, CA, United States
name: 'FOCS: Foundations of Computer Science'
start_date: 2023-11-06
date_created: 2024-01-09T16:20:09Z
date_published: 2023-12-22T00:00:00Z
date_updated: 2025-09-09T14:17:59Z
day: '22'
department:
- _id: MoHe
doi: 10.1109/focs57990.2023.00066
ec_funded: 1
external_id:
arxiv:
- '2310.04076'
isi:
- '001137125900060'
fulldoi: https://doi.org/10.1109/focs57990.2023.00066
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2310.04076
month: '12'
oa: 1
oa_version: Preprint
page: 1105-1130
project:
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
call_identifier: H2020
grant_number: '101034413'
name: 'IST-BRIDGE: International postdoctoral program'
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
call_identifier: H2020
grant_number: '101019564'
name: The design and evaluation of modern fully dynamic data structures
publication: 2023 IEEE 64th Annual Symposium on Foundations of Computer Science
publication_identifier:
eisbn:
- '9798350318944'
publication_status: published
publisher: IEEE
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Deterministic clustering in high dimensional spaces: Sketches and approximation'
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
year: '2023'
...
---
_id: '15364'
abstract:
- lang: eng
text: "Clustering is a fundamental problem in unsupervised machine learning with
many applications in data analysis. Popular clustering algorithms such as Lloyd's
algorithm and k-means++ can make Ω(ndk) time when clustering n points in a d-dimensional
space (represented by an n×d matrix X) into k clusters. On massive datasets with
moderate to large k, the multiplicative \r\nk factor can become very expensive.
We introduce a simple randomized clustering algorithm that provably runs in expected
time O(nnz(X)+nlogn) for arbitrary k. Here nnz(X) is the total number of non-zero
entries in the input dataset X, which is upper bounded by nd and can be significantly
smaller for sparse datasets. We prove that our algorithm achieves approximation
ratio ˜O(k4) on any input dataset for the k-means objective, and our experiments
show that the quality of the clusters found by our algorithm is usually much better
than this worst-case bound. We use our algorithm for k-means clustering and for
coreset construction; our experiments show that it gives a new tradeoff between
running time and cluster quality compared to previous state-of-the-art methods
for these tasks. Our theoretical analysis is based on novel results of independent
interest. We show that the approximation ratio achieved after a random one-dimensional
projection can be lifted to the original points and that k-means++ seeding can
be implemented in expected time O(nlogn) in one dimension."
acknowledgement: "Moses Charikar was supported by a Simons Investigator award. Lunjia
Hu was supported by Moses Charikar’s and Omer Reingold’s Simons Investigators awards,
Omer Reingold’s NSF Award IIS-1908774, and the Simons Foundation Collaboration on
the Theory of Algorithmic Fairness. Part of this work was done while Erik Waingarten
was a postdoc at Stanford University, supported by an NSF postdoctoral fellowship
and by Moses Charikar’s Simons\r\nInvestigator Award. This project has received
funding from the European Research Council (ERC) under the European Union’s Horizon
2020 research and innovation programme\r\n(Grant agreement No. 101019564 “The Design
of Modern Fully Dynamic Data\r\nStructures (MoDynStruct)” and the Austrian Science
Fund (FWF) project Z 422-N, 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."
alternative_title:
- Advances in Neural Information Processing Systems
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Moses
full_name: Charikar, Moses
last_name: Charikar
- first_name: Lunjia
full_name: Hu, Lunjia
last_name: Hu
- 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: Maximilian
full_name: Vötsch, Maximilian
last_name: Vötsch
- first_name: Erik
full_name: Waingarten, Erik
last_name: Waingarten
citation:
ama: 'Charikar M, Hu L, Henzinger M, Vötsch M, Waingarten E. Simple, scalable and
effective clustering via one-dimensional projections. In: 37th Conference on
Neural Information Processing Systems. Vol 36. Neural Information Processing
Systems Foundation; 2023.'
apa: 'Charikar, M., Hu, L., Henzinger, M., Vötsch, M., & Waingarten, E. (2023).
Simple, scalable and effective clustering via one-dimensional projections. In
37th Conference on Neural Information Processing Systems (Vol. 36). New
Orleans, LA, United States: Neural Information Processing Systems Foundation.'
chicago: Charikar, Moses, Lunjia Hu, Monika Henzinger, Maximilian Vötsch, and Erik
Waingarten. “Simple, Scalable and Effective Clustering via One-Dimensional Projections.”
In 37th Conference on Neural Information Processing Systems, Vol. 36. Neural
Information Processing Systems Foundation, 2023.
ieee: M. Charikar, L. Hu, M. Henzinger, M. Vötsch, and E. Waingarten, “Simple, scalable
and effective clustering via one-dimensional projections,” in 37th Conference
on Neural Information Processing Systems, New Orleans, LA, United States,
2023, vol. 36.
ista: 'Charikar M, Hu L, Henzinger M, Vötsch M, Waingarten E. 2023. Simple, scalable
and effective clustering via one-dimensional projections. 37th Conference on Neural
Information Processing Systems. NeurIPS: Neural Information Processing Systems,
Advances in Neural Information Processing Systems, vol. 36.'
mla: Charikar, Moses, et al. “Simple, Scalable and Effective Clustering via One-Dimensional
Projections.” 37th Conference on Neural Information Processing Systems,
vol. 36, Neural Information Processing Systems Foundation, 2023.
short: M. Charikar, L. Hu, M. Henzinger, M. Vötsch, E. Waingarten, in:, 37th Conference
on Neural Information Processing Systems, Neural Information Processing Systems
Foundation, 2023.
conference:
end_date: 2023-12-16
location: New Orleans, LA, United States
name: 'NeurIPS: Neural Information Processing Systems'
start_date: 2023-12-10
das_tickbox: '1'
date_created: 2024-05-05T22:01:05Z
date_published: 2023-12-15T00:00:00Z
date_updated: 2026-07-07T06:37:54Z
day: '15'
ddc:
- '000'
department:
- _id: MoHe
ec_funded: 1
external_id:
arxiv:
- '2310.16752'
file:
- access_level: open_access
checksum: d169a147a2adf55878e0a99e36a9d468
content_type: application/pdf
creator: dernst
date_created: 2024-05-22T07:34:00Z
date_updated: 2024-05-22T07:34:00Z
file_id: '15416'
file_name: 2023_Neurips_Charikar.pdf
file_size: 1445159
relation: main_file
success: 1
file_date_updated: 2024-05-22T07:34:00Z
has_accepted_license: '1'
intvolume: ' 36'
language:
- iso: eng
month: '12'
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: Efficient algorithms
- _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: 37th Conference on Neural Information Processing Systems
publication_identifier:
issn:
- 1049-5258
publication_status: published
publisher: Neural Information Processing Systems Foundation
quality_controlled: '1'
scopus_import: '1'
status: public
title: Simple, scalable and effective clustering via one-dimensional projections
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: 36
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 M. 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. (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 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. 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 M. 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 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. 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: 2026-10-21T08:03:01Z
day: '22'
department:
- _id: MoHe
doi: 10.1007/978-3-031-32726-1_32
ec_funded: 1
external_id:
arxiv:
- '2301.09217'
isi:
- '001281059600032'
fulldoi: https://doi.org/10.1007/978-3-031-32726-1_32
intvolume: ' 13904'
isi: 1
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'
related_material:
record:
- id: '15121'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Multiplicative auction algorithm for approximate maximum weight bipartite matching
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 13904
year: '2023'
...