---
_id: '14769'
abstract:
- lang: eng
text: 'For a set of points in Rd, the Euclidean k-means problems consists of finding
k centers such that the sum of distances squared from each data point to its closest
center is minimized. Coresets are one the main tools developed recently to solve
this problem in a big data context. They allow to compress the initial dataset
while preserving its structure: running any algorithm on the coreset provides
a guarantee almost equivalent to running it on the full data. In this work, we
study coresets in a fully-dynamic setting: points are added and deleted with the
goal to efficiently maintain a coreset with which a k-means solution can be computed.
Based on an algorithm from Henzinger and Kale [ESA''20], we present an efficient
and practical implementation of a fully dynamic coreset algorithm, that improves
the running time by up to a factor of 20 compared to our non-optimized implementation
of the algorithm by Henzinger and Kale, without sacrificing more than 7% on the
quality of the k-means solution.'
acknowledgement: This project has received funding from the Euro-pean Research Council (ERC) under the EuropeanUnion’s Horizon 2020 research and innovation programme (Grant agreement No. 101019564 “The De-sign of Modern Fully Dynamic Data Structures (Mo-DynStruct)” and the Austrian Science Fund (FWF)project
Z 422-N, project “Static and Dynamic Hierar-chical Graph Decompositions”, I 5982-N, and project“Fast Algorithms for a Reactive Network Layer (Re-actNet)”,
P 33775-N, with additional funding from thenetidee SCIENCE Stiftung, 2020–2024.D. Sauplic has received funding from the Euro-pean Union’s Horizon 2020 research and innovation
programme under the Marie Sklodowska-Curie grant agreementNo 101034413.
article_processing_charge: No
arxiv: 1
author:
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: David
full_name: Saulpic, David
id: f8e48cf0-b0ff-11ed-b0e9-b4c35598f964
last_name: Saulpic
- first_name: Leonhard
full_name: Sidl, Leonhard
id: 8b563fd0-b441-11ee-9101-a3891c61efa6
last_name: Sidl
citation:
ama: 'Henzinger MH, Saulpic D, Sidl L. Experimental evaluation of fully dynamic
k-means via coresets. In: 2024 Proceedings of the Symposium on Algorithm Engineering
and Experiments. Society for Industrial & Applied Mathematics; 2024:220-233.
doi:10.1137/1.9781611977929.17'
apa: 'Henzinger, M. H., Saulpic, D., & Sidl, L. (2024). Experimental evaluation
of fully dynamic k-means via coresets. In 2024 Proceedings of the Symposium
on Algorithm Engineering and Experiments (pp. 220–233). Alexandria, VA, United
States: Society for Industrial & Applied Mathematics. https://doi.org/10.1137/1.9781611977929.17'
chicago: Henzinger, Monika H, David Saulpic, and Leonhard Sidl. “Experimental Evaluation
of Fully Dynamic K-Means via Coresets.” In 2024 Proceedings of the Symposium
on Algorithm Engineering and Experiments, 220–33. Society for Industrial &
Applied Mathematics, 2024. https://doi.org/10.1137/1.9781611977929.17.
ieee: M. H. Henzinger, D. Saulpic, and L. Sidl, “Experimental evaluation of fully
dynamic k-means via coresets,” in 2024 Proceedings of the Symposium on Algorithm
Engineering and Experiments, Alexandria, VA, United States, 2024, pp. 220–233.
ista: 'Henzinger MH, Saulpic D, Sidl L. 2024. Experimental evaluation of fully dynamic
k-means via coresets. 2024 Proceedings of the Symposium on Algorithm Engineering
and Experiments. ALENEX: Workshop on Algorithm Engineering and Experiments, 220–233.'
mla: Henzinger, Monika H., et al. “Experimental Evaluation of Fully Dynamic K-Means
via Coresets.” 2024 Proceedings of the Symposium on Algorithm Engineering and
Experiments, Society for Industrial & Applied Mathematics, 2024, pp. 220–33,
doi:10.1137/1.9781611977929.17.
short: M.H. Henzinger, D. Saulpic, L. Sidl, in:, 2024 Proceedings of the Symposium
on Algorithm Engineering and Experiments, Society for Industrial & Applied
Mathematics, 2024, pp. 220–233.
conference:
end_date: 2024-01-08
location: Alexandria, VA, United States
name: 'ALENEX: Workshop on Algorithm Engineering and Experiments'
start_date: 2024-01-07
date_created: 2024-01-09T16:22:47Z
date_published: 2024-01-04T00:00:00Z
date_updated: 2025-07-15T12:51:52Z
day: '04'
department:
- _id: MoHe
doi: 10.1137/1.9781611977929.17
ec_funded: 1
external_id:
arxiv:
- '2310.18034'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2310.18034
month: '01'
oa: 1
oa_version: Preprint
page: 220-233
project:
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
call_identifier: H2020
grant_number: '101019564'
name: The design and evaluation of modern fully dynamic data structures
- _id: 34def286-11ca-11ed-8bc3-da5948e1613c
grant_number: Z00422
name: Wittgenstein Award - Monika Henzinger
- _id: bda196b2-d553-11ed-ba76-8e8ee6c21103
grant_number: I05982
name: Static and Dynamic Hierarchical Graph Decompositions
- _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
grant_number: 'P33775 '
name: Fast Algorithms for a Reactive Network Layer
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
call_identifier: H2020
grant_number: '101034413'
name: 'IST-BRIDGE: International postdoctoral program'
publication: 2024 Proceedings of the Symposium on Algorithm Engineering and Experiments
publication_identifier:
eisbn:
- '9781611977929'
publication_status: published
publisher: Society for Industrial & Applied Mathematics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Experimental evaluation of fully dynamic k-means via coresets
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2024'
...
---
_id: '15008'
abstract:
- lang: eng
text: "Oblivious routing is a well-studied paradigm that uses static precomputed
routing tables for selecting routing paths within a network. Existing oblivious
routing schemes with polylogarithmic competitive ratio for general networks are
tree-based, in the sense that routing is performed according to a convex combination
of trees. However, this restriction to trees leads to a construction that has
time quadratic in the size of the network and does not parallelize well. \r\nIn
this paper we study oblivious routing schemes based on electrical routing. In
particular, we show that general networks with n vertices and m edges admit a
routing scheme that has competitive ratio O(log² n) and consists of a convex combination
of only O(√m) electrical routings. This immediately leads to an improved construction
algorithm with time Õ(m^{3/2}) that can also be implemented in parallel with
Õ(√m) depth."
acknowledgement: "Monika Henzinger and A. R. Sricharan: This project has received
funding from the European Research Council (ERC) under the European Union’s Horizon
2020 research and innovation\r\nprogramme (Grant agreement No. 101019564) and the
Austrian Science Fund (FWF) project Z\r\n422-N, project I 5982-N, and project P
33775-N, with additional funding from the netidee SCIENCE Stiftung, 2020–2024.\r\nHarald
Räcke: Research supported by German Research Foundation (DFG), grant 470029389\r\n(FlexNets),
2021-2024.\r\nSushant Sachdeva: SS’s work is supported by an Natural Sciences and
Engineering Research Council of Canada (NSERC) Discovery Grant RGPIN-2018-06398
and a Sloan Research Fellowship."
alternative_title:
- LIPIcs
article_number: '55'
article_processing_charge: No
arxiv: 1
author:
- first_name: Gramoz
full_name: Goranci, Gramoz
last_name: Goranci
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Harald
full_name: Räcke, Harald
last_name: Räcke
- first_name: Sushant
full_name: Sachdeva, Sushant
last_name: Sachdeva
- first_name: A. R.
full_name: Sricharan, A. R.
last_name: Sricharan
citation:
ama: 'Goranci G, Henzinger MH, Räcke H, Sachdeva S, Sricharan AR. Electrical flows
for polylogarithmic competitive oblivious routing. In: 15th Innovations in
Theoretical Computer Science Conference. Vol 287. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik; 2024. doi:10.4230/LIPIcs.ITCS.2024.55'
apa: 'Goranci, G., Henzinger, M. H., Räcke, H., Sachdeva, S., & Sricharan, A.
R. (2024). Electrical flows for polylogarithmic competitive oblivious routing.
In 15th Innovations in Theoretical Computer Science Conference (Vol. 287).
Berkeley, CA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.ITCS.2024.55'
chicago: Goranci, Gramoz, Monika H Henzinger, Harald Räcke, Sushant Sachdeva, and
A. R. Sricharan. “Electrical Flows for Polylogarithmic Competitive Oblivious Routing.”
In 15th Innovations in Theoretical Computer Science Conference, Vol. 287.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.ITCS.2024.55.
ieee: G. Goranci, M. H. Henzinger, H. Räcke, S. Sachdeva, and A. R. Sricharan, “Electrical
flows for polylogarithmic competitive oblivious routing,” in 15th Innovations
in Theoretical Computer Science Conference, Berkeley, CA, United States, 2024,
vol. 287.
ista: 'Goranci G, Henzinger MH, Räcke H, Sachdeva S, Sricharan AR. 2024. Electrical
flows for polylogarithmic competitive oblivious routing. 15th Innovations in Theoretical
Computer Science Conference. ITCS: Innovations in Theoretical Computer Science
Conference, LIPIcs, vol. 287, 55.'
mla: Goranci, Gramoz, et al. “Electrical Flows for Polylogarithmic Competitive Oblivious
Routing.” 15th Innovations in Theoretical Computer Science Conference,
vol. 287, 55, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.ITCS.2024.55.
short: G. Goranci, M.H. Henzinger, H. Räcke, S. Sachdeva, A.R. Sricharan, in:, 15th
Innovations in Theoretical Computer Science Conference, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2024.
conference:
end_date: 2024-02-02
location: Berkeley, CA, United States
name: 'ITCS: Innovations in Theoretical Computer Science Conference'
start_date: 2024-01-30
date_created: 2024-02-18T23:01:02Z
date_published: 2024-01-24T00:00:00Z
date_updated: 2025-07-15T12:51:53Z
day: '24'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ITCS.2024.55
ec_funded: 1
external_id:
arxiv:
- '2303.02491'
file:
- access_level: open_access
checksum: b89716aae6a5599f187897e39de1e53a
content_type: application/pdf
creator: dernst
date_created: 2024-02-26T10:10:48Z
date_updated: 2024-02-26T10:10:48Z
file_id: '15030'
file_name: 2024_LIPICs_Goranci.pdf
file_size: 1054754
relation: main_file
success: 1
file_date_updated: 2024-02-26T10:10:48Z
has_accepted_license: '1'
intvolume: ' 287'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
project:
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
call_identifier: H2020
grant_number: '101019564'
name: The design and evaluation of modern fully dynamic data structures
- _id: 34def286-11ca-11ed-8bc3-da5948e1613c
grant_number: Z00422
name: Wittgenstein Award - Monika Henzinger
- _id: bda196b2-d553-11ed-ba76-8e8ee6c21103
grant_number: I05982
name: Static and Dynamic Hierarchical Graph Decompositions
- _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
grant_number: 'P33775 '
name: Fast Algorithms for a Reactive Network Layer
publication: 15th Innovations in Theoretical Computer Science Conference
publication_identifier:
isbn:
- '9783959773096'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Electrical flows for polylogarithmic competitive oblivious routing
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 287
year: '2024'
...
---
_id: '14558'
abstract:
- lang: eng
text: "n the dynamic minimum set cover problem, the challenge is to minimize the
update time while guaranteeing a close-to-optimal min{O(log n), f} approximation
factor. (Throughout, n, m, f , and C are parameters denoting the maximum number
of elements, the number of sets, the frequency, and the cost range.) In the high-frequency
range, when f = Ω(log n) , this was achieved by a deterministic O(log n) -approximation
algorithm with O(f log n) amortized update time by Gupta et al. [Online and dynamic
algorithms for set cover, in Proceedings STOC 2017, ACM, pp. 537–550]. In this
paper we consider the low-frequency range, when f = O(log n) , and obtain deterministic
algorithms with a (1 + ∈)f -approximation ratio and the following guarantees on
the update time. (1) O ((f/∈)-log(Cn)) amortized update time: Prior to our work,
the best approximation ratio guaranteed by deterministic algorithms was O(f2)
of Bhattacharya, Henzinger, and Italiano [Design of dynamic algorithms via primal-dual
method, in Proceedings ICALP 2015, Springer, pp. 206–218]. In contrast, the only
result with O(f) -approximation was that of Abboud et al. [Dynamic set cover:
Improved algorithms and lower bounds, in Proceedings STOC 2019, ACM, pp. 114–125],
who designed a randomized (1+∈)f -approximation algorithm with amortized update
time. (2) O(f2/∈3 + (f/∈2).logC) amortized update time: This result improves the
above update time bound for most values of f\r\n in the low-frequency range, i.e.,
f=o(log n) . It is also the first result that is independent of m\r\n and n. It
subsumes the constant amortized update time of Bhattacharya and Kulkarni [Deterministically
maintaining a (2 + ∈) -approximate minimum vertex cover in O(1/∈2) amortized update
time, in Proceedings SODA 2019, SIAM, pp. 1872–1885] for unweighted dynamic vertex
cover (i.e., when f = 2 and C = 1). (3) O((f/∈3).log2(Cn)) worst-case update time:
No nontrivial worst-case update time was previously known for the dynamic set
cover problem. Our bound subsumes and improves by a logarithmic factor the O(log3n/poly
(∈)) \r\n worst-case update time for the unweighted dynamic vertex cover problem
(i.e., when f = 2\r\n and C =1) of Bhattacharya, Henzinger, and Nanongkai [Fully
dynamic approximate maximum matching and minimum vertex cover in O(log3)n worst
case update time, in Proceedings SODA 2017, SIAM, pp. 470–489]. We achieve our
results via the primal-dual approach, by maintaining a fractional packing solution
as a dual certificate. Prior work in dynamic algorithms that employs the primal-dual
approach uses a local update scheme that maintains relaxed complementary slackness
conditions for every set. For our first result we use instead a global update
scheme that does not always maintain complementary slackness conditions. For our
second result we combine the global and the local update schema. To achieve our
third result we use a hierarchy of background schedulers. It is an interesting
open question whether this background scheduler technique can also be used to
transform algorithms with amortized running time bounds into algorithms with worst-case
running time bounds."
acknowledgement: "This project has received funding from the European Research Council
(ERC) under the European Union's Horizon 2020 research and innovation programme
(grants 715672 and\r\n101019564 ``The Design of Modern Fully Dynamic Data Structures
(MoDynStruct)\"\") and from the Engineering and Physical Sciences Research Council,
UK (EPSRC) under grant EP/S03353X/1. The second author was also supported by the
Austrian Science Fund (FWF) project ``Fast Algorithms for a Reactive Network Layer
(ReactNet),\"\" P 33775-N, with additional funding from the netidee SCIENCE Stiftung,
2020--2024, project ``Static and Dynamic Hierarchical Graph Decompositions,\"\"I
5982-N, and project Z 422-N. The third author was also supported by the Swedish
Research Council (Reg. No. 2015-04659). The fourth author was also supported by
the Science and Technology Development Fund (FDCT), Macau SAR (file 0014/2022/AFJ,
0085/2022/A, 0143/2020/A3, and SKL-IOTSC-2021-2023)."
article_processing_charge: No
article_type: original
author:
- first_name: Sayan
full_name: Bhattacharya, Sayan
last_name: Bhattacharya
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Danupon
full_name: Nanongkai, Danupon
last_name: Nanongkai
- first_name: Xiaowei
full_name: Wu, Xiaowei
last_name: Wu
citation:
ama: Bhattacharya S, Henzinger MH, Nanongkai D, Wu X. Deterministic near-optimal
approximation algorithms for dynamic set cover. SIAM Journal on Computing.
2023;52(5):1132-1192. doi:10.1137/21M1428649
apa: Bhattacharya, S., Henzinger, M. H., Nanongkai, D., & Wu, X. (2023). Deterministic
near-optimal approximation algorithms for dynamic set cover. SIAM Journal on
Computing. Society for Industrial and Applied Mathematics. https://doi.org/10.1137/21M1428649
chicago: Bhattacharya, Sayan, Monika H Henzinger, Danupon Nanongkai, and Xiaowei
Wu. “Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover.”
SIAM Journal on Computing. Society for Industrial and Applied Mathematics,
2023. https://doi.org/10.1137/21M1428649.
ieee: S. Bhattacharya, M. H. Henzinger, D. Nanongkai, and X. Wu, “Deterministic
near-optimal approximation algorithms for dynamic set cover,” SIAM Journal
on Computing, vol. 52, no. 5. Society for Industrial and Applied Mathematics,
pp. 1132–1192, 2023.
ista: Bhattacharya S, Henzinger MH, Nanongkai D, Wu X. 2023. Deterministic near-optimal
approximation algorithms for dynamic set cover. SIAM Journal on Computing. 52(5),
1132–1192.
mla: Bhattacharya, Sayan, et al. “Deterministic Near-Optimal Approximation Algorithms
for Dynamic Set Cover.” SIAM Journal on Computing, vol. 52, no. 5, Society
for Industrial and Applied Mathematics, 2023, pp. 1132–92, doi:10.1137/21M1428649.
short: S. Bhattacharya, M.H. Henzinger, D. Nanongkai, X. Wu, SIAM Journal on Computing
52 (2023) 1132–1192.
date_created: 2023-11-19T23:00:56Z
date_published: 2023-10-01T00:00:00Z
date_updated: 2025-07-15T12:51:52Z
day: '01'
department:
- _id: MoHe
doi: 10.1137/21M1428649
ec_funded: 1
intvolume: ' 52'
issue: '5'
language:
- iso: eng
month: '10'
oa_version: None
page: 1132-1192
project:
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
call_identifier: H2020
grant_number: '101019564'
name: The design and evaluation of modern fully dynamic data structures
- _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
grant_number: 'P33775 '
name: Fast Algorithms for a Reactive Network Layer
- _id: 34def286-11ca-11ed-8bc3-da5948e1613c
grant_number: Z00422
name: Wittgenstein Award - Monika Henzinger
- _id: bda196b2-d553-11ed-ba76-8e8ee6c21103
grant_number: I05982
name: Static and Dynamic Hierarchical Graph Decompositions
publication: SIAM Journal on Computing
publication_identifier:
eissn:
- 1095-7111
issn:
- 0097-5397
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Deterministic near-optimal approximation algorithms for dynamic set cover
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 52
year: '2023'
...
---
_id: '14085'
abstract:
- lang: eng
text: We show an (1+ϵ)-approximation algorithm for maintaining maximum s-t flow
under m edge insertions in m1/2+o(1)ϵ−1/2 amortized update time for directed,
unweighted graphs. This constitutes the first sublinear dynamic maximum flow algorithm
in general sparse graphs with arbitrarily good approximation guarantee.
acknowledgement: "This project has received funding from the European Research Council
(ERC) under the European Union’s Horizon 2020 research and innovation programme
(Grant agreement No.\r\n101019564 “The Design of Modern Fully Dynamic Data Structures
(MoDynStruct)” and from the\r\nAustrian Science Fund (FWF) project “Static and Dynamic
Hierarchical Graph Decompositions”,\r\nI 5982-N, and project “Fast Algorithms for
a Reactive Network Layer (ReactNet)”, P 33775-N, with additional funding from the
netidee SCIENCE Stiftung, 2020–2024.\r\nThis work was done in part while Gramoz
Goranci was at Institute for Theoretical Studies, ETH Zurich, Switzerland. There,
he was supported by Dr. Max Rössler, the Walter Haefner Foundation and the ETH Zürich
Foundation. We also thank Richard Peng, Thatchaphol Saranurak, Sebastian Forster
and Sushant Sachdeva for helpful discussions, and the anonymous reviewers for their
insightful comments."
alternative_title:
- LIPIcs
article_number: '69'
article_processing_charge: Yes
author:
- first_name: Gramoz
full_name: Goranci, Gramoz
last_name: Goranci
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
citation:
ama: 'Goranci G, Henzinger MH. Efficient data structures for incremental exact and
approximate maximum flow. In: 50th International Colloquium on Automata, Languages,
and Programming. Vol 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
2023. doi:10.4230/LIPIcs.ICALP.2023.69'
apa: 'Goranci, G., & Henzinger, M. H. (2023). Efficient data structures for
incremental exact and approximate maximum flow. In 50th International Colloquium
on Automata, Languages, and Programming (Vol. 261). Paderborn, Germany: Schloss
Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2023.69'
chicago: Goranci, Gramoz, and Monika H Henzinger. “Efficient Data Structures for
Incremental Exact and Approximate Maximum Flow.” In 50th International Colloquium
on Automata, Languages, and Programming, Vol. 261. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2023. https://doi.org/10.4230/LIPIcs.ICALP.2023.69.
ieee: G. Goranci and M. H. Henzinger, “Efficient data structures for incremental
exact and approximate maximum flow,” in 50th International Colloquium on Automata,
Languages, and Programming, Paderborn, Germany, 2023, vol. 261.
ista: 'Goranci G, Henzinger MH. 2023. Efficient data structures for incremental
exact and approximate maximum flow. 50th International Colloquium on Automata,
Languages, and Programming. ICALP: International Colloquium on Automata, Languages,
and Programming, LIPIcs, vol. 261, 69.'
mla: Goranci, Gramoz, and Monika H. Henzinger. “Efficient Data Structures for Incremental
Exact and Approximate Maximum Flow.” 50th International Colloquium on Automata,
Languages, and Programming, vol. 261, 69, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2023, doi:10.4230/LIPIcs.ICALP.2023.69.
short: G. Goranci, M.H. Henzinger, in:, 50th International Colloquium on Automata,
Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2023.
conference:
end_date: 2023-07-14
location: Paderborn, Germany
name: 'ICALP: International Colloquium on Automata, Languages, and Programming'
start_date: 2023-07-10
date_created: 2023-08-20T22:01:14Z
date_published: 2023-07-01T00:00:00Z
date_updated: 2023-08-21T07:00:49Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ICALP.2023.69
ec_funded: 1
external_id:
unknown:
- '2211.09606'
file:
- access_level: open_access
checksum: 074177e815a1656de5d4071c7a3dffa6
content_type: application/pdf
creator: dernst
date_created: 2023-08-21T06:59:05Z
date_updated: 2023-08-21T06:59:05Z
file_id: '14089'
file_name: 2023_LIPIcsICALP_Goranci.pdf
file_size: 875910
relation: main_file
success: 1
file_date_updated: 2023-08-21T06:59:05Z
has_accepted_license: '1'
intvolume: ' 261'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
project:
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
call_identifier: H2020
grant_number: '101019564'
name: The design and evaluation of modern fully dynamic data structures
- _id: bda196b2-d553-11ed-ba76-8e8ee6c21103
grant_number: I05982
name: Static and Dynamic Hierarchical Graph Decompositions
- _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
grant_number: 'P33775 '
name: Fast Algorithms for a Reactive Network Layer
publication: 50th International Colloquium on Automata, Languages, and Programming
publication_identifier:
isbn:
- '9783959772785'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Efficient data structures for incremental exact and approximate maximum flow
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 261
year: '2023'
...
---
_id: '14086'
abstract:
- lang: eng
text: "The maximization of submodular functions have found widespread application
in areas such as machine learning, combinatorial optimization, and economics,
where practitioners often wish to enforce various constraints; the matroid constraint
has been investigated extensively due to its algorithmic properties and expressive
power. Though tight approximation algorithms for general matroid constraints exist
in theory, the running times of such algorithms typically scale quadratically,
and are not practical for truly large scale settings. Recent progress has focused
on fast algorithms for important classes of matroids given in explicit form. Currently,
nearly-linear time algorithms only exist for graphic and partition matroids [Alina
Ene and Huy L. Nguyen, 2019]. In this work, we develop algorithms for monotone
submodular maximization constrained by graphic, transversal matroids, or laminar
matroids in time near-linear in the size of their representation. Our algorithms
achieve an optimal approximation of 1-1/e-ε and both generalize and accelerate
the results of Ene and Nguyen [Alina Ene and Huy L. Nguyen, 2019]. In fact, the
running time of our algorithm cannot be improved within the fast continuous greedy
framework of Badanidiyuru and Vondrák [Ashwinkumar Badanidiyuru and Jan Vondrák,
2014].\r\nTo achieve near-linear running time, we make use of dynamic data structures
that maintain bases with approximate maximum cardinality and weight under certain
element updates. These data structures need to support a weight decrease operation
and a novel Freeze operation that allows the algorithm to freeze elements (i.e.
force to be contained) in its basis regardless of future data structure operations.
For the laminar matroid, we present a new dynamic data structure using the top
tree interface of Alstrup, Holm, de Lichtenberg, and Thorup [Stephen Alstrup et
al., 2005] that maintains the maximum weight basis under insertions and deletions
of elements in O(log n) time. This data structure needs to support certain subtree
query and path update operations that are performed every insertion and deletion
that are non-trivial to handle in conjunction. For the transversal matroid the
Freeze operation corresponds to requiring the data structure to keep a certain
set S of vertices matched, a property that we call S-stability. While there is
a large body of work on dynamic matching algorithms, none are S-stable and maintain
an approximate maximum weight matching under vertex updates. We give the first
such algorithm for bipartite graphs with total running time linear (up to log
factors) in the number of edges."
acknowledgement: " Monika Henzinger: This project has received funding from the European
Research Council\r\n(ERC) under the European Union’s Horizon 2020 research and innovation
programme (Grant\r\nagreement No. 101019564 “The Design of Modern Fully Dynamic
Data Structures (MoDynStruct)” and from the Austrian Science Fund (FWF) project
“Static and Dynamic Hierarchical Graph Decompositions”, I 5982-N, and project “Fast
Algorithms for a Reactive Network Layer (ReactNet)”, P 33775-N, with additional
funding from the netidee SCIENCE Stiftung, 2020–2024. Jan Vondrák: Supported by
NSF Award 2127781."
alternative_title:
- LIPIcs
article_number: '74'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Paul
full_name: Liu, Paul
last_name: Liu
- first_name: Jan
full_name: Vondrák, Jan
last_name: Vondrák
- first_name: Da Wei
full_name: Zheng, Da Wei
last_name: Zheng
citation:
ama: 'Henzinger MH, Liu P, Vondrák J, Zheng DW. Faster submodular maximization for
several classes of matroids. In: 50th International Colloquium on Automata,
Languages, and Programming. Vol 261. Schloss Dagstuhl - Leibniz-Zentrum für
Informatik; 2023. doi:10.4230/LIPIcs.ICALP.2023.74'
apa: 'Henzinger, M. H., Liu, P., Vondrák, J., & Zheng, D. W. (2023). Faster
submodular maximization for several classes of matroids. In 50th International
Colloquium on Automata, Languages, and Programming (Vol. 261). Paderborn,
Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2023.74'
chicago: Henzinger, Monika H, Paul Liu, Jan Vondrák, and Da Wei Zheng. “Faster Submodular
Maximization for Several Classes of Matroids.” In 50th International Colloquium
on Automata, Languages, and Programming, Vol. 261. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2023. https://doi.org/10.4230/LIPIcs.ICALP.2023.74.
ieee: M. H. Henzinger, P. Liu, J. Vondrák, and D. W. Zheng, “Faster submodular maximization
for several classes of matroids,” in 50th International Colloquium on Automata,
Languages, and Programming, Paderborn, Germany, 2023, vol. 261.
ista: 'Henzinger MH, Liu P, Vondrák J, Zheng DW. 2023. Faster submodular maximization
for several classes of matroids. 50th International Colloquium on Automata, Languages,
and Programming. ICALP: International Colloquium on Automata, Languages, and Programming,
LIPIcs, vol. 261, 74.'
mla: Henzinger, Monika H., et al. “Faster Submodular Maximization for Several Classes
of Matroids.” 50th International Colloquium on Automata, Languages, and Programming,
vol. 261, 74, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:10.4230/LIPIcs.ICALP.2023.74.
short: M.H. Henzinger, P. Liu, J. Vondrák, D.W. Zheng, in:, 50th International Colloquium
on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für
Informatik, 2023.
conference:
end_date: 2023-07-14
location: Paderborn, Germany
name: 'ICALP: International Colloquium on Automata, Languages, and Programming'
start_date: 2023-07-10
date_created: 2023-08-20T22:01:14Z
date_published: 2023-07-01T00:00:00Z
date_updated: 2023-08-21T07:05:47Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ICALP.2023.74
ec_funded: 1
external_id:
arxiv:
- '2305.00122'
file:
- access_level: open_access
checksum: a5eef225014e003efbfbe4830fdd23cb
content_type: application/pdf
creator: dernst
date_created: 2023-08-21T07:04:36Z
date_updated: 2023-08-21T07:04:36Z
file_id: '14090'
file_name: 2023_LIPIcsICALP_HenzingerM.pdf
file_size: 930943
relation: main_file
success: 1
file_date_updated: 2023-08-21T07:04:36Z
has_accepted_license: '1'
intvolume: ' 261'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
project:
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
call_identifier: H2020
grant_number: '101019564'
name: The design and evaluation of modern fully dynamic data structures
- _id: bda196b2-d553-11ed-ba76-8e8ee6c21103
grant_number: I05982
name: Static and Dynamic Hierarchical Graph Decompositions
- _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
grant_number: 'P33775 '
name: Fast Algorithms for a Reactive Network Layer
publication: 50th International Colloquium on Automata, Languages, and Programming
publication_identifier:
isbn:
- '9783959772785'
issn:
- '18688969'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Faster submodular maximization for several classes of matroids
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 261
year: '2023'
...