---
_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
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: 2024-02-26T10:12:19Z
day: '24'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ITCS.2024.55
ec_funded: 1
external_id:
arxiv:
- '2303.02491'
file:
- access_level: open_access
checksum: b89716aae6a5599f187897e39de1e53a
content_type: application/pdf
creator: dernst
date_created: 2024-02-26T10:10:48Z
date_updated: 2024-02-26T10:10:48Z
file_id: '15030'
file_name: 2024_LIPICs_Goranci.pdf
file_size: 1054754
relation: main_file
success: 1
file_date_updated: 2024-02-26T10:10:48Z
has_accepted_license: '1'
intvolume: ' 287'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '01'
oa: 1
oa_version: Published Version
project:
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
call_identifier: H2020
grant_number: '101019564'
name: The design and evaluation of modern fully dynamic data structures
- _id: 34def286-11ca-11ed-8bc3-da5948e1613c
grant_number: Z00422
name: Wittgenstein Award - Monika Henzinger
- _id: bda196b2-d553-11ed-ba76-8e8ee6c21103
grant_number: I05982
name: Static and Dynamic Hierarchical Graph Decompositions
- _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
grant_number: 'P33775 '
name: Fast Algorithms for a Reactive Network Layer
publication: 15th Innovations in Theoretical Computer Science Conference
publication_identifier:
isbn:
- '9783959773096'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Electrical flows for polylogarithmic competitive oblivious routing
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 287
year: '2024'
...
---
_id: '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
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: 2024-02-26T09:51:31Z
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: '15121'
abstract:
- lang: eng
text: We present an auction algorithm using multiplicative instead of constant weight
updates to compute a (1-E)-approximate maximum weight matching (MWM) in a bipartite
graph with n vertices and m edges in time 0(mE-1), beating the running time of
the fastest known approximation algorithm of Duan and Pettie [JACM ’14] that runs
in 0(mE-1 log E-1). Our algorithm is very simple and it can be extended to give
a dynamic data structure that maintains a (1-E)-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 0(mE-1), where m is the sum of the number of initially existing
and inserted edges.
acknowledgement: The first author thanks Chandra Chekuri for useful discussions about
this paper. This work was done in part at the University of Vienna. 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.
article_processing_charge: No
article_type: original
author:
- first_name: Da Wei
full_name: Zheng, Da Wei
last_name: Zheng
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
citation:
ama: Zheng DW, Henzinger MH. Multiplicative auction algorithm for approximate maximum
weight bipartite matching. Mathematical Programming. 2024. doi:10.1007/s10107-024-02066-3
apa: Zheng, D. W., & Henzinger, M. H. (2024). Multiplicative auction algorithm
for approximate maximum weight bipartite matching. Mathematical Programming.
Springer Nature. https://doi.org/10.1007/s10107-024-02066-3
chicago: Zheng, Da Wei, and Monika H Henzinger. “Multiplicative Auction Algorithm
for Approximate Maximum Weight Bipartite Matching.” Mathematical Programming.
Springer Nature, 2024. https://doi.org/10.1007/s10107-024-02066-3.
ieee: D. W. Zheng and M. H. Henzinger, “Multiplicative auction algorithm for approximate
maximum weight bipartite matching,” Mathematical Programming. Springer
Nature, 2024.
ista: Zheng DW, Henzinger MH. 2024. Multiplicative auction algorithm for approximate
maximum weight bipartite matching. Mathematical Programming.
mla: Zheng, Da Wei, and Monika H. Henzinger. “Multiplicative Auction Algorithm for
Approximate Maximum Weight Bipartite Matching.” Mathematical Programming,
Springer Nature, 2024, doi:10.1007/s10107-024-02066-3.
short: D.W. Zheng, M.H. Henzinger, Mathematical Programming (2024).
date_created: 2024-03-17T23:00:58Z
date_published: 2024-03-06T00:00:00Z
date_updated: 2024-03-19T08:32:32Z
day: '06'
department:
- _id: MoHe
doi: 10.1007/s10107-024-02066-3
ec_funded: 1
external_id:
arxiv:
- '2301.09217'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2301.09217
month: '03'
oa: 1
oa_version: Preprint
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: Mathematical Programming
publication_identifier:
eissn:
- 1436-4646
issn:
- 0025-5610
publication_status: epub_ahead
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '13236'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Multiplicative auction algorithm for approximate maximum weight bipartite matching
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2024'
...
---
_id: '15093'
abstract:
- lang: eng
text: We present a dynamic data structure for maintaining the persistent homology
of a time series of real numbers. The data structure supports local operations,
including the insertion and deletion of an item and the cutting and concatenating
of lists, each in time O(log n + k), in which n counts the critical items and
k the changes in the augmented persistence diagram. To achieve this, we design
a tailor-made tree structure with an unconventional representation, referred to
as banana tree, which may be useful in its own right.
acknowledgement: The first and second authors are funded by the European Research Council under the
European Union’s Horizon 2020 research and innovation programme, ERC grant no. 788183,“Alpha
Shape Theory Extended (Alpha)”, by the Wittgenstein Prize, FWF grant no. Z 342-N31,
and by the DFG Collaborative Research Center TRR 109, FWF grant no. I 02979-N35.The
third author received funding by the European Research Council under the European
Union’s Horizon 2020research and innovation programme, ERC grant no. 101019564, “The Design of Modern Fully Dynamic DataStructures
(MoDynStruct)”, and by the Austrian Science Fund through the Wittgenstein Prize
with FWF grant no. Z 422-N, and also by FWF grant no. I 5982-N, and by FWF grant
no. P 33775-N, with additional funding from the netidee SCIENCE Stiftung, 2020–2024. The
fourth author is funded by the Vienna Graduate School on Computational Optimization,
FWF project no. W1260-N35.
article_processing_charge: No
author:
- first_name: Sebastiano
full_name: Cultrera di Montesano, Sebastiano
id: 34D2A09C-F248-11E8-B48F-1D18A9856A87
last_name: Cultrera di Montesano
orcid: 0000-0001-6249-0832
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- 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: Lara
full_name: Ost, Lara
last_name: Ost
citation:
ama: 'Cultrera di Montesano S, Edelsbrunner H, Henzinger MH, Ost L. Dynamically
maintaining the persistent homology of time series. In: Woodruff DP, ed. Proceedings
of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society
for Industrial and Applied Mathematics; 2024:243-295. doi:10.1137/1.9781611977912.11'
apa: 'Cultrera di Montesano, S., Edelsbrunner, H., Henzinger, M. H., & Ost,
L. (2024). Dynamically maintaining the persistent homology of time series. In
D. P. Woodruff (Ed.), Proceedings of the 2024 Annual ACM-SIAM Symposium on
Discrete Algorithms (SODA) (pp. 243–295). Alexandria, VA, USA: Society for
Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611977912.11'
chicago: Cultrera di Montesano, Sebastiano, Herbert Edelsbrunner, Monika H Henzinger,
and Lara Ost. “Dynamically Maintaining the Persistent Homology of Time Series.”
In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms
(SODA), edited by David P. Woodruff, 243–95. Society for Industrial and Applied
Mathematics, 2024. https://doi.org/10.1137/1.9781611977912.11.
ieee: S. Cultrera di Montesano, H. Edelsbrunner, M. H. Henzinger, and L. Ost, “Dynamically
maintaining the persistent homology of time series,” in Proceedings of the
2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Alexandria,
VA, USA, 2024, pp. 243–295.
ista: 'Cultrera di Montesano S, Edelsbrunner H, Henzinger MH, Ost L. 2024. Dynamically
maintaining the persistent homology of time series. Proceedings of the 2024 Annual
ACM-SIAM Symposium on Discrete Algorithms (SODA). SODA: Symposium on Discrete
Algorigthms, 243–295.'
mla: Cultrera di Montesano, Sebastiano, et al. “Dynamically Maintaining the Persistent
Homology of Time Series.” Proceedings of the 2024 Annual ACM-SIAM Symposium
on Discrete Algorithms (SODA), edited by David P. Woodruff, Society for Industrial
and Applied Mathematics, 2024, pp. 243–95, doi:10.1137/1.9781611977912.11.
short: S. Cultrera di Montesano, H. Edelsbrunner, M.H. Henzinger, L. Ost, in:, D.P.
Woodruff (Ed.), Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA), Society for Industrial and Applied Mathematics, 2024, pp. 243–295.
conference:
end_date: 2024-01-10
location: Alexandria, VA, USA
name: 'SODA: Symposium on Discrete Algorigthms'
start_date: 2024-01-07
date_created: 2024-03-08T10:27:39Z
date_published: 2024-01-04T00:00:00Z
date_updated: 2024-03-20T09:36:56Z
day: '04'
department:
- _id: HeEd
- _id: MoHe
doi: 10.1137/1.9781611977912.11
ec_funded: 1
editor:
- first_name: David P.
full_name: Woodruff, David P.
last_name: Woodruff
external_id:
arxiv:
- '2311.01115'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2311.01115
month: '01'
oa: 1
oa_version: Preprint
page: 243 - 295
project:
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '788183'
name: Alpha Shape Theory Extended
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: The Wittgenstein Prize
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
call_identifier: H2020
grant_number: '101019564'
name: The design and evaluation of modern fully dynamic data structures
- _id: 34def286-11ca-11ed-8bc3-da5948e1613c
grant_number: Z00422
name: Wittgenstein Award - Monika Henzinger
- _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
grant_number: 'P33775 '
name: Fast Algorithms for a Reactive Network Layer
publication: Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms
(SODA)
publication_identifier:
eisbn:
- '9781611977912'
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
related_material:
record:
- id: '15094'
relation: dissertation_contains
status: public
status: public
title: Dynamically maintaining the persistent homology of time series
type: conference
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
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
author:
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Stefan
full_name: Neumann, Stefan
last_name: Neumann
- first_name: Harald
full_name: Räcke, Harald
last_name: Räcke
- first_name: Stefan
full_name: Schmid, Stefan
last_name: Schmid
citation:
ama: 'Henzinger MH, Neumann S, Räcke H, Schmid S. Dynamic maintenance of monotone
dynamic programs and applications. In: 40th International Symposium on Theoretical
Aspects of Computer Science. Vol 254. Schloss Dagstuhl - Leibniz-Zentrum für
Informatik; 2023. doi:10.4230/LIPIcs.STACS.2023.36'
apa: 'Henzinger, M. H., Neumann, S., Räcke, H., & Schmid, S. (2023). Dynamic
maintenance of monotone dynamic programs and applications. In 40th International
Symposium on Theoretical Aspects of Computer Science (Vol. 254). Hamburg,
Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.STACS.2023.36'
chicago: Henzinger, Monika H, Stefan Neumann, Harald Räcke, and Stefan Schmid. “Dynamic
Maintenance of Monotone Dynamic Programs and Applications.” In 40th International
Symposium on Theoretical Aspects of Computer Science, Vol. 254. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2023. https://doi.org/10.4230/LIPIcs.STACS.2023.36.
ieee: M. H. Henzinger, S. Neumann, H. Räcke, and S. Schmid, “Dynamic maintenance
of monotone dynamic programs and applications,” in 40th International Symposium
on Theoretical Aspects of Computer Science, Hamburg, Germany, 2023, vol. 254.
ista: 'Henzinger MH, Neumann S, Räcke H, Schmid S. 2023. Dynamic maintenance of
monotone dynamic programs and applications. 40th International Symposium on Theoretical
Aspects of Computer Science. STACS: Symposium on Theoretical Aspects of Computer
Science, LIPIcs, vol. 254, 36.'
mla: Henzinger, Monika H., et al. “Dynamic Maintenance of Monotone Dynamic Programs
and Applications.” 40th International Symposium on Theoretical Aspects of Computer
Science, vol. 254, 36, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2023, doi:10.4230/LIPIcs.STACS.2023.36.
short: M.H. Henzinger, S. Neumann, H. Räcke, S. Schmid, in:, 40th International
Symposium on Theoretical Aspects of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2023.
conference:
end_date: 2023-03-09
location: Hamburg, Germany
name: 'STACS: Symposium on Theoretical Aspects of Computer Science'
start_date: 2023-03-07
date_created: 2023-03-26T22:01:07Z
date_published: 2023-03-01T00:00:00Z
date_updated: 2023-03-27T06:46:27Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.STACS.2023.36
external_id:
arxiv:
- '2301.01744'
file:
- access_level: open_access
checksum: 22141ab8bc55188e2dfff665e5daecbd
content_type: application/pdf
creator: dernst
date_created: 2023-03-27T06:37:22Z
date_updated: 2023-03-27T06:37:22Z
file_id: '12769'
file_name: 2023_LIPICS_HenzingerM.pdf
file_size: 872706
relation: main_file
success: 1
file_date_updated: 2023-03-27T06:37:22Z
has_accepted_license: '1'
intvolume: ' 254'
language:
- iso: eng
month: '03'
oa: 1
oa_version: Published Version
publication: 40th International Symposium on Theoretical Aspects of Computer Science
publication_identifier:
isbn:
- '9783959772662'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Dynamic maintenance of monotone dynamic programs and applications
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 254
year: '2023'
...
---
_id: '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
author:
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Paul
full_name: Liu, Paul
last_name: Liu
- first_name: Jan
full_name: Vondrák, Jan
last_name: Vondrák
- first_name: Da Wei
full_name: Zheng, Da Wei
last_name: Zheng
citation:
ama: 'Henzinger MH, Liu P, Vondrák J, Zheng DW. Faster submodular maximization for
several classes of matroids. In: 50th International Colloquium on Automata,
Languages, and Programming. Vol 261. Schloss Dagstuhl - Leibniz-Zentrum für
Informatik; 2023. doi:10.4230/LIPIcs.ICALP.2023.74'
apa: 'Henzinger, M. H., Liu, P., Vondrák, J., & Zheng, D. W. (2023). Faster
submodular maximization for several classes of matroids. In 50th International
Colloquium on Automata, Languages, and Programming (Vol. 261). Paderborn,
Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2023.74'
chicago: Henzinger, Monika H, Paul Liu, Jan Vondrák, and Da Wei Zheng. “Faster Submodular
Maximization for Several Classes of Matroids.” In 50th International Colloquium
on Automata, Languages, and Programming, Vol. 261. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2023. https://doi.org/10.4230/LIPIcs.ICALP.2023.74.
ieee: M. H. Henzinger, P. Liu, J. Vondrák, and D. W. Zheng, “Faster submodular maximization
for several classes of matroids,” in 50th International Colloquium on Automata,
Languages, and Programming, Paderborn, Germany, 2023, vol. 261.
ista: 'Henzinger MH, Liu P, Vondrák J, Zheng DW. 2023. Faster submodular maximization
for several classes of matroids. 50th International Colloquium on Automata, Languages,
and Programming. ICALP: International Colloquium on Automata, Languages, and Programming,
LIPIcs, vol. 261, 74.'
mla: Henzinger, Monika H., et al. “Faster Submodular Maximization for Several Classes
of Matroids.” 50th International Colloquium on Automata, Languages, and Programming,
vol. 261, 74, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:10.4230/LIPIcs.ICALP.2023.74.
short: M.H. Henzinger, P. Liu, J. Vondrák, D.W. Zheng, in:, 50th International Colloquium
on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für
Informatik, 2023.
conference:
end_date: 2023-07-14
location: Paderborn, Germany
name: 'ICALP: International Colloquium on Automata, Languages, and Programming'
start_date: 2023-07-10
date_created: 2023-08-20T22:01:14Z
date_published: 2023-07-01T00:00:00Z
date_updated: 2023-08-21T07:05:47Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ICALP.2023.74
ec_funded: 1
external_id:
arxiv:
- '2305.00122'
file:
- access_level: open_access
checksum: a5eef225014e003efbfbe4830fdd23cb
content_type: application/pdf
creator: dernst
date_created: 2023-08-21T07:04:36Z
date_updated: 2023-08-21T07:04:36Z
file_id: '14090'
file_name: 2023_LIPIcsICALP_HenzingerM.pdf
file_size: 930943
relation: main_file
success: 1
file_date_updated: 2023-08-21T07:04:36Z
has_accepted_license: '1'
intvolume: ' 261'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
project:
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
call_identifier: H2020
grant_number: '101019564'
name: The design and evaluation of modern fully dynamic data structures
- _id: bda196b2-d553-11ed-ba76-8e8ee6c21103
grant_number: I05982
name: Static and Dynamic Hierarchical Graph Decompositions
- _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
grant_number: 'P33775 '
name: Fast Algorithms for a Reactive Network Layer
publication: 50th International Colloquium on Automata, Languages, and Programming
publication_identifier:
isbn:
- '9783959772785'
issn:
- '18688969'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Faster submodular maximization for several classes of matroids
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 261
year: '2023'
...
---
_id: '14462'
abstract:
- lang: eng
text: "We study fine-grained error bounds for differentially private algorithms
for counting under continual observation. Our main insight is that the matrix
mechanism when using lower-triangular matrices can be used in the continual observation
model. More specifically, we give an explicit factorization for the counting matrix
Mcount and upper bound the error explicitly. We also give a fine-grained analysis,
specifying the exact constant in the upper bound. Our analysis is based on upper
and lower bounds of the completely bounded norm (cb-norm) of Mcount\r\n. Along
the way, we improve the best-known bound of 28 years by Mathias (SIAM Journal
on Matrix Analysis and Applications, 1993) on the cb-norm of Mcount for a large
range of the dimension of Mcount. Furthermore, we are the first to give concrete
error bounds for various problems under continual observation such as binary counting,
maintaining a histogram, releasing an approximately cut-preserving synthetic graph,
many graph-based statistics, and substring and episode counting. Finally, we note
that our result can be used to get a fine-grained error bound for non-interactive
local learning and the first lower bounds on the additive error for (ϵ,δ)-differentially-private
counting under continual observation. Subsequent to this work, Henzinger et al.
(SODA, 2023) showed that our factorization also achieves fine-grained mean-squared
error."
acknowledgement: "This project has received funding from the European Research Council
(ERC) under the European Union’s Horizon 2020 research and innovation programme
(Grant agreement No.\r\n101019564 “The Design of Modern Fully Dynamic Data Structures
(MoDynStruct)” and from the Austrian Science Fund (FWF) project Z 422-N, and project
“Fast Algorithms for a Reactive Network Layer (ReactNet)”, P 33775-N, with additional
funding from the netidee SCIENCE Stiftung, 2020–2024. 2020–2024. JU’s research was
funded by Decanal Research Grant. A part of this work was done when JU was visiting
Indian Statistical Institute, Delhi. The authors would like to thank Rajat Bhatia,
Aleksandar Nikolov, Shanta Laisharam, Vern Paulsen, Ryan Rogers, Abhradeep Thakurta,
and Sarvagya Upadhyay for useful discussions."
alternative_title:
- PMLR
article_processing_charge: No
author:
- first_name: Hendrik
full_name: Fichtenberger, Hendrik
last_name: Fichtenberger
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Jalaj
full_name: Upadhyay, Jalaj
last_name: Upadhyay
citation:
ama: 'Fichtenberger H, Henzinger MH, Upadhyay J. Constant matters: Fine-grained
error bound on differentially private continual observation. In: Proceedings
of the 40th International Conference on Machine Learning. Vol 202. ML Research
Press; 2023:10072-10092.'
apa: 'Fichtenberger, H., Henzinger, M. H., & Upadhyay, J. (2023). Constant matters:
Fine-grained error bound on differentially private continual observation. In Proceedings
of the 40th International Conference on Machine Learning (Vol. 202, pp. 10072–10092).
Honolulu, Hawaii, HI, United States: ML Research Press.'
chicago: 'Fichtenberger, Hendrik, Monika H Henzinger, and Jalaj Upadhyay. “Constant
Matters: Fine-Grained Error Bound on Differentially Private Continual Observation.”
In Proceedings of the 40th International Conference on Machine Learning,
202:10072–92. ML Research Press, 2023.'
ieee: 'H. Fichtenberger, M. H. Henzinger, and J. Upadhyay, “Constant matters: Fine-grained
error bound on differentially private continual observation,” in Proceedings
of the 40th International Conference on Machine Learning, Honolulu, Hawaii,
HI, United States, 2023, vol. 202, pp. 10072–10092.'
ista: 'Fichtenberger H, Henzinger MH, Upadhyay J. 2023. Constant matters: Fine-grained
error bound on differentially private continual observation. Proceedings of the
40th International Conference on Machine Learning. ICML: International Conference
on Machine Learning, PMLR, vol. 202, 10072–10092.'
mla: 'Fichtenberger, Hendrik, et al. “Constant Matters: Fine-Grained Error Bound
on Differentially Private Continual Observation.” Proceedings of the 40th International
Conference on Machine Learning, vol. 202, ML Research Press, 2023, pp. 10072–92.'
short: H. Fichtenberger, M.H. Henzinger, J. Upadhyay, in:, Proceedings of the 40th
International Conference on Machine Learning, ML Research Press, 2023, pp. 10072–10092.
conference:
end_date: 2023-07-29
location: Honolulu, Hawaii, HI, United States
name: 'ICML: International Conference on Machine Learning'
start_date: 2023-07-23
date_created: 2023-10-29T23:01:17Z
date_published: 2023-07-30T00:00:00Z
date_updated: 2023-10-31T09:54:05Z
day: '30'
department:
- _id: MoHe
ec_funded: 1
intvolume: ' 202'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://proceedings.mlr.press/v202/fichtenberger23a/fichtenberger23a.pdf
month: '07'
oa: 1
oa_version: Published Version
page: 10072-10092
project:
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
call_identifier: H2020
grant_number: '101019564'
name: The design and evaluation of modern fully dynamic data structures
- _id: 34def286-11ca-11ed-8bc3-da5948e1613c
grant_number: Z00422
name: Wittgenstein Award - Monika Henzinger
- _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
grant_number: 'P33775 '
name: Fast Algorithms for a Reactive Network Layer
publication: Proceedings of the 40th International Conference on Machine Learning
publication_identifier:
eissn:
- 2640-3498
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Constant matters: Fine-grained error bound on differentially private continual
observation'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 202
year: '2023'
...
---
_id: '14558'
abstract:
- lang: eng
text: "n the dynamic minimum set cover problem, the challenge is to minimize the
update time while guaranteeing a close-to-optimal min{O(log n), f} approximation
factor. (Throughout, n, m, f , and C are parameters denoting the maximum number
of elements, the number of sets, the frequency, and the cost range.) In the high-frequency
range, when f = Ω(log n) , this was achieved by a deterministic O(log n) -approximation
algorithm with O(f log n) amortized update time by Gupta et al. [Online and dynamic
algorithms for set cover, in Proceedings STOC 2017, ACM, pp. 537–550]. In this
paper we consider the low-frequency range, when f = O(log n) , and obtain deterministic
algorithms with a (1 + ∈)f -approximation ratio and the following guarantees on
the update time. (1) O ((f/∈)-log(Cn)) amortized update time: Prior to our work,
the best approximation ratio guaranteed by deterministic algorithms was O(f2)
of Bhattacharya, Henzinger, and Italiano [Design of dynamic algorithms via primal-dual
method, in Proceedings ICALP 2015, Springer, pp. 206–218]. In contrast, the only
result with O(f) -approximation was that of Abboud et al. [Dynamic set cover:
Improved algorithms and lower bounds, in Proceedings STOC 2019, ACM, pp. 114–125],
who designed a randomized (1+∈)f -approximation algorithm with amortized update
time. (2) O(f2/∈3 + (f/∈2).logC) amortized update time: This result improves the
above update time bound for most values of f\r\n in the low-frequency range, i.e.,
f=o(log n) . It is also the first result that is independent of m\r\n and n. It
subsumes the constant amortized update time of Bhattacharya and Kulkarni [Deterministically
maintaining a (2 + ∈) -approximate minimum vertex cover in O(1/∈2) amortized update
time, in Proceedings SODA 2019, SIAM, pp. 1872–1885] for unweighted dynamic vertex
cover (i.e., when f = 2 and C = 1). (3) O((f/∈3).log2(Cn)) worst-case update time:
No nontrivial worst-case update time was previously known for the dynamic set
cover problem. Our bound subsumes and improves by a logarithmic factor the O(log3n/poly
(∈)) \r\n worst-case update time for the unweighted dynamic vertex cover problem
(i.e., when f = 2\r\n and C =1) of Bhattacharya, Henzinger, and Nanongkai [Fully
dynamic approximate maximum matching and minimum vertex cover in O(log3)n worst
case update time, in Proceedings SODA 2017, SIAM, pp. 470–489]. We achieve our
results via the primal-dual approach, by maintaining a fractional packing solution
as a dual certificate. Prior work in dynamic algorithms that employs the primal-dual
approach uses a local update scheme that maintains relaxed complementary slackness
conditions for every set. For our first result we use instead a global update
scheme that does not always maintain complementary slackness conditions. For our
second result we combine the global and the local update schema. To achieve our
third result we use a hierarchy of background schedulers. It is an interesting
open question whether this background scheduler technique can also be used to
transform algorithms with amortized running time bounds into algorithms with worst-case
running time bounds."
acknowledgement: "This project has received funding from the European Research Council
(ERC) under the European Union's Horizon 2020 research and innovation programme
(grants 715672 and\r\n101019564 ``The Design of Modern Fully Dynamic Data Structures
(MoDynStruct)\"\") and from the Engineering and Physical Sciences Research Council,
UK (EPSRC) under grant EP/S03353X/1. The second author was also supported by the
Austrian Science Fund (FWF) project ``Fast Algorithms for a Reactive Network Layer
(ReactNet),\"\" P 33775-N, with additional funding from the netidee SCIENCE Stiftung,
2020--2024, project ``Static and Dynamic Hierarchical Graph Decompositions,\"\"I
5982-N, and project Z 422-N. The third author was also supported by the Swedish
Research Council (Reg. No. 2015-04659). The fourth author was also supported by
the Science and Technology Development Fund (FDCT), Macau SAR (file 0014/2022/AFJ,
0085/2022/A, 0143/2020/A3, and SKL-IOTSC-2021-2023)."
article_processing_charge: No
article_type: original
author:
- first_name: Sayan
full_name: Bhattacharya, Sayan
last_name: Bhattacharya
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Danupon
full_name: Nanongkai, Danupon
last_name: Nanongkai
- first_name: Xiaowei
full_name: Wu, Xiaowei
last_name: Wu
citation:
ama: Bhattacharya S, Henzinger MH, Nanongkai D, Wu X. Deterministic near-optimal
approximation algorithms for dynamic set cover. SIAM Journal on Computing.
2023;52(5):1132-1192. doi:10.1137/21M1428649
apa: Bhattacharya, S., Henzinger, M. H., Nanongkai, D., & Wu, X. (2023). Deterministic
near-optimal approximation algorithms for dynamic set cover. SIAM Journal on
Computing. Society for Industrial and Applied Mathematics. https://doi.org/10.1137/21M1428649
chicago: Bhattacharya, Sayan, Monika H Henzinger, Danupon Nanongkai, and Xiaowei
Wu. “Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover.”
SIAM Journal on Computing. Society for Industrial and Applied Mathematics,
2023. https://doi.org/10.1137/21M1428649.
ieee: S. Bhattacharya, M. H. Henzinger, D. Nanongkai, and X. Wu, “Deterministic
near-optimal approximation algorithms for dynamic set cover,” SIAM Journal
on Computing, vol. 52, no. 5. Society for Industrial and Applied Mathematics,
pp. 1132–1192, 2023.
ista: Bhattacharya S, Henzinger MH, Nanongkai D, Wu X. 2023. Deterministic near-optimal
approximation algorithms for dynamic set cover. SIAM Journal on Computing. 52(5),
1132–1192.
mla: Bhattacharya, Sayan, et al. “Deterministic Near-Optimal Approximation Algorithms
for Dynamic Set Cover.” SIAM Journal on Computing, vol. 52, no. 5, Society
for Industrial and Applied Mathematics, 2023, pp. 1132–92, doi:10.1137/21M1428649.
short: S. Bhattacharya, M.H. Henzinger, D. Nanongkai, X. Wu, SIAM Journal on Computing
52 (2023) 1132–1192.
date_created: 2023-11-19T23:00:56Z
date_published: 2023-10-01T00:00:00Z
date_updated: 2023-11-20T08:21:07Z
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: '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
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: Symposium on 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: Symposium on 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: 2024-01-16T07:28:06Z
day: '22'
department:
- _id: MoHe
doi: 10.1109/focs57990.2023.00066
ec_funded: 1
external_id:
arxiv:
- '2310.04076'
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
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
author:
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Billy
full_name: Jin, Billy
last_name: Jin
- first_name: Richard
full_name: Peng, Richard
last_name: Peng
- first_name: David P.
full_name: Williamson, David P.
last_name: Williamson
citation:
ama: Henzinger MH, Jin B, Peng R, Williamson DP. A combinatorial cut-toggling algorithm
for solving Laplacian linear systems. Algorithmica. 2023;85:2680-3716.
doi:10.1007/s00453-023-01154-8
apa: Henzinger, M. H., Jin, B., Peng, R., & Williamson, D. P. (2023). A combinatorial
cut-toggling algorithm for solving Laplacian linear systems. Algorithmica.
Springer Nature. https://doi.org/10.1007/s00453-023-01154-8
chicago: Henzinger, Monika H, Billy Jin, Richard Peng, and David P. Williamson.
“A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems.”
Algorithmica. Springer Nature, 2023. https://doi.org/10.1007/s00453-023-01154-8.
ieee: M. H. Henzinger, B. Jin, R. Peng, and D. P. Williamson, “A combinatorial cut-toggling
algorithm for solving Laplacian linear systems,” Algorithmica, vol. 85.
Springer Nature, pp. 2680–3716, 2023.
ista: Henzinger MH, Jin B, Peng R, Williamson DP. 2023. A combinatorial cut-toggling
algorithm for solving Laplacian linear systems. Algorithmica. 85, 2680–3716.
mla: Henzinger, Monika H., et al. “A Combinatorial Cut-Toggling Algorithm for Solving
Laplacian Linear Systems.” Algorithmica, vol. 85, Springer Nature, 2023,
pp. 2680–3716, doi:10.1007/s00453-023-01154-8.
short: M.H. Henzinger, B. Jin, R. Peng, D.P. Williamson, Algorithmica 85 (2023)
2680–3716.
date_created: 2023-08-13T22:01:13Z
date_published: 2023-12-01T00:00:00Z
date_updated: 2024-01-30T12:33:10Z
day: '01'
department:
- _id: MoHe
doi: 10.1007/s00453-023-01154-8
ec_funded: 1
external_id:
arxiv:
- '2010.16316'
isi:
- '001041254900002'
intvolume: ' 85'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2010.16316
month: '12'
oa: 1
oa_version: Preprint
page: 2680-3716
project:
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
call_identifier: H2020
grant_number: '101019564'
name: The design and evaluation of modern fully dynamic data structures
- _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
grant_number: 'P33775 '
name: Fast Algorithms for a Reactive Network Layer
publication: Algorithmica
publication_identifier:
eissn:
- 1432-0541
issn:
- 0178-4617
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: A combinatorial cut-toggling algorithm for solving Laplacian linear systems
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 85
year: '2023'
...
---
_id: '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
author:
- first_name: Da Wei
full_name: Zheng, Da Wei
last_name: Zheng
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
citation:
ama: 'Zheng DW, Henzinger MH. Multiplicative auction algorithm for approximate maximum
weight bipartite matching. In: International Conference on Integer Programming
and Combinatorial Optimization. Vol 13904. Springer Nature; 2023:453-465.
doi:10.1007/978-3-031-32726-1_32'
apa: 'Zheng, D. W., & Henzinger, M. H. (2023). Multiplicative auction algorithm
for approximate maximum weight bipartite matching. In International Conference
on Integer Programming and Combinatorial Optimization (Vol. 13904, pp. 453–465).
Madison, WI, United States: Springer Nature. https://doi.org/10.1007/978-3-031-32726-1_32'
chicago: Zheng, Da Wei, and Monika H Henzinger. “Multiplicative Auction Algorithm
for Approximate Maximum Weight Bipartite Matching.” In International Conference
on Integer Programming and Combinatorial Optimization, 13904:453–65. Springer
Nature, 2023. https://doi.org/10.1007/978-3-031-32726-1_32.
ieee: D. W. Zheng and M. H. Henzinger, “Multiplicative auction algorithm for approximate
maximum weight bipartite matching,” in International Conference on Integer
Programming and Combinatorial Optimization, Madison, WI, United States, 2023,
vol. 13904, pp. 453–465.
ista: 'Zheng DW, Henzinger MH. 2023. Multiplicative auction algorithm for approximate
maximum weight bipartite matching. International Conference on Integer Programming
and Combinatorial Optimization. IPCO: Integer Programming and Combinatorial Optimization,
LNCS, vol. 13904, 453–465.'
mla: Zheng, Da Wei, and Monika H. Henzinger. “Multiplicative Auction Algorithm for Approximate
Maximum Weight Bipartite Matching.” International Conference on Integer Programming
and Combinatorial Optimization, vol. 13904, Springer Nature, 2023, pp. 453–65,
doi:10.1007/978-3-031-32726-1_32.
short: D.W. Zheng, M.H. Henzinger, in:, International Conference on Integer Programming
and Combinatorial Optimization, Springer Nature, 2023, pp. 453–465.
conference:
end_date: 2023-06-23
location: Madison, WI, United States
name: 'IPCO: Integer Programming and Combinatorial Optimization'
start_date: 2023-06-21
date_created: 2023-07-16T22:01:11Z
date_published: 2023-05-22T00:00:00Z
date_updated: 2024-03-19T08:32:32Z
day: '22'
department:
- _id: MoHe
doi: 10.1007/978-3-031-32726-1_32
ec_funded: 1
external_id:
arxiv:
- '2301.09217'
intvolume: ' 13904'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2301.09217
month: '05'
oa: 1
oa_version: Preprint
page: 453-465
project:
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
call_identifier: H2020
grant_number: '101019564'
name: The design and evaluation of modern fully dynamic data structures
- _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
grant_number: 'P33775 '
name: Fast Algorithms for a Reactive Network Layer
publication: International Conference on Integer Programming and Combinatorial Optimization
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783031327254'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 13904
year: '2023'
...