---
OA_place: repository
OA_type: green
_id: '18855'
abstract:
- lang: eng
text: "A central problem in computational statistics is to convert a procedure for
sampling combinatorial objects into a procedure for counting those objects, and
vice versa. We consider sampling problems which come from Gibbs distributions,
which are families of probability distributions over a discrete space Ω with probability
mass function of the form μ^Ω_β(ω) ∝ e^{β H(ω)} for β in an interval [β_min, β_max]
and H(ω) ∈ {0} ∪ [1, n]. Two important parameters are the partition function,
which is the normalization factor Z(β) = ∑_{ω ∈ Ω} e^{β H(ω)}, and the vector
of pre-image counts c_x=|H^-1(x)|.\r\nWe develop black-box sampling algorithms
to estimate the counts roughly Õ(n²/ε²) samples for integer-valued distributions
and Õ(q/ε²) samples for general distributions, where q = (log Z(β_max))/Z(β_min)
\ (ignoring some second-order terms and parameters). We show this is optimal up
to logarithmic factors. We illustrate with improved algorithms for counting connected
subgraphs, independent sets, and perfect matchings. As a key subroutine, we estimate
all values of the partition function using Õ(n²/ε²) samples for integer-valued
distributions and Õ(q/ε²) samples for general distributions. This improves over
a prior algorithm of Huber (2015) which computes a single point estimate Z(β_max)
and which uses a slightly larger amount of samples. We show matching lower bounds,
demonstrating this complexity is optimal as a function of n and q up to logarithmic
terms."
acknowledgement: "We thank Heng Guo for helpful explanations of algorithms for sampling
connected subgraphs and matchings, and Maksym Serbyn for bringing to our attention
the WL algorithm and its use in physics.\r\nThis is an extended version, which includes
work under the same name from ICALP 2023, as well as the earlier work [22] appearing
in COLT 2018.\r\nV. Kolmogorov was supported by the European Research Council under
the European Unions Seventh Framework Programme (FP7/2007-2013)/ERC grant agreement
no 616160"
article_number: '3'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: David G.
full_name: Harris, David G.
last_name: Harris
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
citation:
ama: Harris DG, Kolmogorov V. Parameter estimation for Gibbs distributions. ACM
Transactions on Algorithms. 2025;21(1). doi:10.1145/3685676
apa: Harris, D. G., & Kolmogorov, V. (2025). Parameter estimation for Gibbs
distributions. ACM Transactions on Algorithms. Association for Computing
Machinery. https://doi.org/10.1145/3685676
chicago: Harris, David G., and Vladimir Kolmogorov. “Parameter Estimation for Gibbs
Distributions.” ACM Transactions on Algorithms. Association for Computing
Machinery, 2025. https://doi.org/10.1145/3685676.
ieee: D. G. Harris and V. Kolmogorov, “Parameter estimation for Gibbs distributions,”
ACM Transactions on Algorithms, vol. 21, no. 1. Association for Computing
Machinery, 2025.
ista: Harris DG, Kolmogorov V. 2025. Parameter estimation for Gibbs distributions.
ACM Transactions on Algorithms. 21(1), 3.
mla: Harris, David G., and Vladimir Kolmogorov. “Parameter Estimation for Gibbs
Distributions.” ACM Transactions on Algorithms, vol. 21, no. 1, 3, Association
for Computing Machinery, 2025, doi:10.1145/3685676.
short: D.G. Harris, V. Kolmogorov, ACM Transactions on Algorithms 21 (2025).
corr_author: '1'
date_created: 2025-01-19T23:01:52Z
date_published: 2025-01-01T00:00:00Z
date_updated: 2025-07-10T11:50:44Z
day: '01'
department:
- _id: VlKo
doi: 10.1145/3685676
ec_funded: 1
external_id:
arxiv:
- '2007.10824'
isi:
- '001399998600008'
intvolume: ' 21'
isi: 1
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2007.10824
month: '01'
oa: 1
oa_version: Preprint
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication: ACM Transactions on Algorithms
publication_identifier:
eissn:
- 1549-6333
issn:
- 1549-6325
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
related_material:
record:
- id: '14084'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Parameter estimation for Gibbs distributions
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 21
year: '2025'
...
---
OA_place: publisher
OA_type: hybrid
PlanS_conform: '1'
_id: '21007'
abstract:
- lang: eng
text: 'Currently, the best known tradeoff between approximation ratio and complexity
for the Sparsest Cut problem is achieved by the algorithm in [Sherman, FOCS 2009]:
it computes O(√(log n)/ε)-approximation using O(nε logO(1) n) maxflows for any
ε∈[Θ(1/log n),Θ(1)]. It works by solving the SDP relaxation of [Arora-Rao-Vazirani,
STOC 2004] using the Multiplicative Weights Update algorithm (MW) of [Arora-Kale,
JACM 2016]. To implement one MW step, Sherman approximately solves a multicommodity
flow problem using another application of MW. Nested MW steps are solved via a
certain "chaining" algorithm that combines results of multiple calls to the maxflow
algorithm. We present an alternative approach that avoids solving the multicommodity
flow problem and instead computes "violating paths". This simplifies Sherman''s
algorithm by removing a need for a nested application of MW, and also allows parallelization:
we show how to compute O(√(log n)/ε)-approximation via O(logO(1) n) maxflows using
O(nε) processors. We also revisit Sherman''s chaining algorithm, and present a
simpler version together with a new analysis.'
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
citation:
ama: Kolmogorov V. A simpler and parallelizable O(√log n)-approximation algorithm
for SPARSEST CUT. ACM Transactions on Algorithms. 2025;21(4):1-22. doi:10.1145/3748723
apa: Kolmogorov, V. (2025). A simpler and parallelizable O(√log n)-approximation
algorithm for SPARSEST CUT. ACM Transactions on Algorithms. Association
for Computing Machinery. https://doi.org/10.1145/3748723
chicago: Kolmogorov, Vladimir. “A Simpler and Parallelizable O(√log n)-Approximation
Algorithm for SPARSEST CUT.” ACM Transactions on Algorithms. Association
for Computing Machinery, 2025. https://doi.org/10.1145/3748723.
ieee: V. Kolmogorov, “A simpler and parallelizable O(√log n)-approximation algorithm
for SPARSEST CUT,” ACM Transactions on Algorithms, vol. 21, no. 4. Association
for Computing Machinery, pp. 1–22, 2025.
ista: Kolmogorov V. 2025. A simpler and parallelizable O(√log n)-approximation algorithm
for SPARSEST CUT. ACM Transactions on Algorithms. 21(4), 1–22.
mla: Kolmogorov, Vladimir. “A Simpler and Parallelizable O(√log n)-Approximation
Algorithm for SPARSEST CUT.” ACM Transactions on Algorithms, vol. 21, no.
4, Association for Computing Machinery, 2025, pp. 1–22, doi:10.1145/3748723.
short: V. Kolmogorov, ACM Transactions on Algorithms 21 (2025) 1–22.
corr_author: '1'
date_created: 2026-01-20T10:04:02Z
date_published: 2025-10-01T00:00:00Z
date_updated: 2026-01-21T09:46:26Z
day: '01'
ddc:
- '510'
department:
- _id: VlKo
doi: 10.1145/3748723
external_id:
arxiv:
- '2307.00115'
file:
- access_level: open_access
checksum: 4a80fdb1e3711b9a2768d2bb8f6d3b4e
content_type: application/pdf
creator: dernst
date_created: 2026-01-21T09:38:09Z
date_updated: 2026-01-21T09:38:09Z
file_id: '21031'
file_name: 2025_ACMToA_Kolmogorov.pdf
file_size: 2208302
relation: main_file
success: 1
file_date_updated: 2026-01-21T09:38:09Z
has_accepted_license: '1'
intvolume: ' 21'
issue: '4'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
page: 1-22
publication: ACM Transactions on Algorithms
publication_identifier:
eissn:
- 1549-6333
issn:
- 1549-6325
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
related_material:
record:
- id: '17236'
relation: shorter_version
status: public
scopus_import: '1'
status: public
title: A simpler and parallelizable O(√log n)-approximation algorithm for SPARSEST
CUT
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 21
year: '2025'
...
---
_id: '11662'
abstract:
- lang: eng
text: We give a fully dynamic (Las-Vegas style) algorithm with constant expected
amortized time per update that maintains a proper (Δ +1)-vertex coloring of a
graph with maximum degree at most Δ. This improves upon the previous O(log Δ)-time
algorithm by Bhattacharya et al. (SODA 2018). Our algorithm uses an approach based
on assigning random ranks to vertices and does not need to maintain a hierarchical
graph decomposition. We show that our result does not only have optimal running
time but is also optimal in the sense that already deciding whether a Δ-coloring
exists in a dynamically changing graph with maximum degree at most Δ takes Ω (log
n) time per operation.
acknowledgement: We want to thank an anonymous referee who pointed out a mistake in
our conference paper as well as suggesting a fix using an approach in References.
article_number: '16'
article_processing_charge: No
article_type: original
author:
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Pan
full_name: Peng, Pan
last_name: Peng
citation:
ama: Henzinger M, Peng P. Constant-time Dynamic (Δ +1)-Coloring. ACM Transactions
on Algorithms. 2022;18(2). doi:10.1145/3501403
apa: Henzinger, M., & Peng, P. (2022). Constant-time Dynamic (Δ +1)-Coloring.
ACM Transactions on Algorithms. Association for Computing Machinery. https://doi.org/10.1145/3501403
chicago: Henzinger, Monika, and Pan Peng. “Constant-Time Dynamic (Δ +1)-Coloring.”
ACM Transactions on Algorithms. Association for Computing Machinery, 2022.
https://doi.org/10.1145/3501403.
ieee: M. Henzinger and P. Peng, “Constant-time Dynamic (Δ +1)-Coloring,” ACM
Transactions on Algorithms, vol. 18, no. 2. Association for Computing Machinery,
2022.
ista: Henzinger M, Peng P. 2022. Constant-time Dynamic (Δ +1)-Coloring. ACM Transactions
on Algorithms. 18(2), 16.
mla: Henzinger, Monika, and Pan Peng. “Constant-Time Dynamic (Δ +1)-Coloring.” ACM
Transactions on Algorithms, vol. 18, no. 2, 16, Association for Computing
Machinery, 2022, doi:10.1145/3501403.
short: M. Henzinger, P. Peng, ACM Transactions on Algorithms 18 (2022).
date_created: 2022-07-27T10:58:53Z
date_published: 2022-03-04T00:00:00Z
date_updated: 2024-11-04T11:42:31Z
day: '04'
doi: 10.1145/3501403
extern: '1'
intvolume: ' 18'
issue: '2'
language:
- iso: eng
month: '03'
oa_version: None
publication: ACM Transactions on Algorithms
publication_identifier:
eissn:
- 1549-6333
issn:
- 1549-6325
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Constant-time Dynamic (Δ +1)-Coloring
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 18
year: '2022'
...
---
_id: '11663'
abstract:
- lang: eng
text: "Many dynamic graph algorithms have an amortized update time, rather than
a stronger worst-case guarantee. But amortized data structures are not suitable
for real-time systems, where each individual operation has to be executed quickly.
For this reason, there exist many recent randomized results that aim to provide
a guarantee stronger than amortized expected. The strongest possible guarantee
for a randomized algorithm is that it is always correct (Las Vegas) and has high-probability
worst-case update time, which gives a bound on the time for each individual operation
that holds with high probability.\r\n\r\nIn this article, we present the first
polylogarithmic high-probability worst-case time bounds for the dynamic spanner
and the dynamic maximal matching problem.\r\n\r\n(1)\r\n\r\nFor dynamic spanner,
the only known o(n) worst-case bounds were O(n3/4) high-probability worst-case
update time for maintaining a 3-spanner and O(n5/9) for maintaining a 5-spanner.
We give a O(1)k log3 (n) high-probability worst-case time bound for maintaining
a (2k-1)-spanner, which yields the first worst-case polylog update time for all
constant k. (All the results above maintain the optimal tradeoff of stretch 2k-1
and Õ(n1+1/k) edges.)\r\n\r\n(2)\r\n\r\nFor dynamic maximal matching, or dynamic
2-approximate maximum matching, no algorithm with o(n) worst-case time bound was
known and we present an algorithm with O(log 5 (n)) high-probability worst-case
time; similar worst-case bounds existed only for maintaining a matching that was
(2+ϵ)-approximate, and hence not maximal.\r\n\r\nOur results are achieved using
a new approach for converting amortized guarantees to worst-case ones for randomized
data structures by going through a third type of guarantee, which is a middle
ground between the two above: An algorithm is said to have worst-case expected
update time ɑ if for every update σ, the expected time to process σ is at most
ɑ. Although stronger than amortized expected, the worst-case expected guarantee
does not resolve the fundamental problem of amortization: A worst-case expected
update time of O(1) still allows for the possibility that every 1/f(n) updates
requires ϴ (f(n)) time to process, for arbitrarily high f(n). In this article,
we present a black-box reduction that converts any data structure with worst-case
expected update time into one with a high-probability worst-case update time:
The query time remains the same, while the update time increases by a factor of
O(log 2(n)).\r\n\r\nThus, we achieve our results in two steps:\r\n\r\n(1) First,
we show how to convert existing dynamic graph algorithms with amortized expected
polylogarithmic running times into algorithms with worst-case expected polylogarithmic
running times.\r\n\r\n(2) Then, we use our black-box reduction to achieve the
polylogarithmic high-probability worst-case time bound. All our algorithms are
Las-Vegas-type algorithms."
acknowledgement: 'The conference version of this article [10] had an error in the
analysis of the dynamic matching algorithm. In particular, Lemma 4.5 assumed an
independence between adversarial updates to the hierarchy that is in fact true,
but which requires a sophisticated proof. We are very grateful to the anonymous
reviewers of Transactions on Algorithms for pointing out this mistake in our analysis.
The mistake is fixed in Section 4.5. Almost the entire fix is a matter of analysis:
the only change to the algorithm itself is the introduction of responsible bits
in Algorithm 2. The first author would like to thank Mikkel Thorup and Alan Roytman
for a very helpful discussion of the proof of Theorem 1.1.'
article_number: '29'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Aaron
full_name: Bernstein, Aaron
last_name: Bernstein
- first_name: Sebastian
full_name: Forster, Sebastian
last_name: Forster
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
citation:
ama: Bernstein A, Forster S, Henzinger M. A deamortization approach for dynamic
spanner and dynamic maximal matching. ACM Transactions on Algorithms. 2021;17(4).
doi:10.1145/3469833
apa: Bernstein, A., Forster, S., & Henzinger, M. (2021). A deamortization approach
for dynamic spanner and dynamic maximal matching. ACM Transactions on Algorithms.
Association for Computing Machinery. https://doi.org/10.1145/3469833
chicago: Bernstein, Aaron, Sebastian Forster, and Monika Henzinger. “A Deamortization
Approach for Dynamic Spanner and Dynamic Maximal Matching.” ACM Transactions
on Algorithms. Association for Computing Machinery, 2021. https://doi.org/10.1145/3469833.
ieee: A. Bernstein, S. Forster, and M. Henzinger, “A deamortization approach for
dynamic spanner and dynamic maximal matching,” ACM Transactions on Algorithms,
vol. 17, no. 4. Association for Computing Machinery, 2021.
ista: Bernstein A, Forster S, Henzinger M. 2021. A deamortization approach for dynamic
spanner and dynamic maximal matching. ACM Transactions on Algorithms. 17(4), 29.
mla: Bernstein, Aaron, et al. “A Deamortization Approach for Dynamic Spanner and
Dynamic Maximal Matching.” ACM Transactions on Algorithms, vol. 17, no.
4, 29, Association for Computing Machinery, 2021, doi:10.1145/3469833.
short: A. Bernstein, S. Forster, M. Henzinger, ACM Transactions on Algorithms 17
(2021).
date_created: 2022-07-27T11:09:06Z
date_published: 2021-10-04T00:00:00Z
date_updated: 2024-11-06T12:05:37Z
day: '04'
doi: 10.1145/3469833
extern: '1'
external_id:
arxiv:
- '1810.10932'
intvolume: ' 17'
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1810.10932
month: '10'
oa: 1
oa_version: Preprint
publication: ACM Transactions on Algorithms
publication_identifier:
eissn:
- 1549-6333
issn:
- 1549-6325
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: A deamortization approach for dynamic spanner and dynamic maximal matching
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 17
year: '2021'
...
---
_id: '9541'
abstract:
- lang: eng
text: The Massively Parallel Computation (MPC) model is an emerging model that distills
core aspects of distributed and parallel computation, developed as a tool to solve
combinatorial (typically graph) problems in systems of many machines with limited
space. Recent work has focused on the regime in which machines have sublinear
(in n, the number of nodes in the input graph) space, with randomized algorithms
presented for the fundamental problems of Maximal Matching and Maximal Independent
Set. However, there have been no prior corresponding deterministic algorithms.
A major challenge underlying the sublinear space setting is that the local space
of each machine might be too small to store all edges incident to a single node.
This poses a considerable obstacle compared to classical models in which each
node is assumed to know and have easy access to its incident edges. To overcome
this barrier, we introduce a new graph sparsification technique that deterministically
computes a low-degree subgraph, with the additional property that solving the
problem on this subgraph provides significant progress towards solving the problem
for the original input graph. Using this framework to derandomize the well-known
algorithm of Luby [SICOMP’86], we obtain O(log Δ + log log n)-round deterministic
MPC algorithms for solving the problems of Maximal Matching and Maximal Independent
Set with O(nɛ) space on each machine for any constant ɛ > 0. These algorithms
also run in O(log Δ) rounds in the closely related model of CONGESTED CLIQUE,
improving upon the state-of-the-art bound of O(log 2Δ) rounds by Censor-Hillel
et al. [DISC’17].
acknowledgement: "Institute of Science and Technology Austria (IST Austria). Email:
peter.davies@ist.ac.at. Work partially\r\ndone at the Department of Computer Science
and Centre for Discrete Mathematics and its Applications (DIMAP),University of Warwick.
Research partially supported by the European Union’s Horizon 2020 research and innovation
programme under the Marie Skłodowska-Curie grant agreement No 754411, the Centre
for Discrete Mathematics and its Applications, a Weizmann-UK Making Connections
Grant, and EPSRC award EP/N011163/1."
article_number: '16'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Artur
full_name: Czumaj, Artur
last_name: Czumaj
- first_name: Peter
full_name: Davies, Peter
id: 11396234-BB50-11E9-B24C-90FCE5697425
last_name: Davies
orcid: 0000-0002-5646-9524
- first_name: Merav
full_name: Parter, Merav
last_name: Parter
citation:
ama: Czumaj A, Davies P, Parter M. Graph sparsification for derandomizing massively
parallel computation with low space. ACM Transactions on Algorithms. 2021;17(2).
doi:10.1145/3451992
apa: Czumaj, A., Davies, P., & Parter, M. (2021). Graph sparsification for derandomizing
massively parallel computation with low space. ACM Transactions on Algorithms.
Association for Computing Machinery. https://doi.org/10.1145/3451992
chicago: Czumaj, Artur, Peter Davies, and Merav Parter. “Graph Sparsification for
Derandomizing Massively Parallel Computation with Low Space.” ACM Transactions
on Algorithms. Association for Computing Machinery, 2021. https://doi.org/10.1145/3451992.
ieee: A. Czumaj, P. Davies, and M. Parter, “Graph sparsification for derandomizing
massively parallel computation with low space,” ACM Transactions on Algorithms,
vol. 17, no. 2. Association for Computing Machinery, 2021.
ista: Czumaj A, Davies P, Parter M. 2021. Graph sparsification for derandomizing
massively parallel computation with low space. ACM Transactions on Algorithms.
17(2), 16.
mla: Czumaj, Artur, et al. “Graph Sparsification for Derandomizing Massively Parallel
Computation with Low Space.” ACM Transactions on Algorithms, vol. 17, no.
2, 16, Association for Computing Machinery, 2021, doi:10.1145/3451992.
short: A. Czumaj, P. Davies, M. Parter, ACM Transactions on Algorithms 17 (2021).
date_created: 2021-06-10T19:31:05Z
date_published: 2021-06-01T00:00:00Z
date_updated: 2025-04-15T06:54:47Z
day: '01'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.1145/3451992
ec_funded: 1
external_id:
arxiv:
- '1912.05390'
isi:
- '000661311300006'
file:
- access_level: open_access
checksum: a21c627683890c309a68f6389302c408
content_type: application/pdf
creator: pdavies
date_created: 2021-06-10T19:33:56Z
date_updated: 2021-06-10T19:33:56Z
file_id: '9542'
file_name: MISMM-arxiv.pdf
file_size: 587404
relation: main_file
success: 1
file_date_updated: 2021-06-10T19:33:56Z
has_accepted_license: '1'
intvolume: ' 17'
isi: 1
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1912.05390
month: '06'
oa: 1
oa_version: Submitted Version
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: ACM Transactions on Algorithms
publication_identifier:
eissn:
- 1549-6333
issn:
- 1549-6325
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
related_material:
record:
- id: '7802'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Graph sparsification for derandomizing massively parallel computation with
low space
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 17
year: '2021'
...
---
_id: '11664'
abstract:
- lang: eng
text: "We present a deterministic incremental algorithm for exactly maintaining
the size of a minimum cut with O(log3 n log log2 n) amortized time per edge insertion
and O(1) query time. This result partially answers an open question posed by Thorup
(2007). It also stays in sharp contrast to a polynomial conditional lower bound
for the fully dynamic weighted minimum cut problem. Our algorithm is obtained
by combining a sparsification technique of Kawarabayashi and Thorup (2015) or
its recent improvement by Henzinger, Rao, and Wang (2017), and an exact incremental
algorithm of Henzinger (1997).\r\n\r\nWe also study space-efficient incremental
algorithms for the minimum cut problem. Concretely, we show that there exists
an O(nlog n/ε2) space Monte Carlo algorithm that can process a stream of edge
insertions starting from an empty graph, and with high probability, the algorithm
maintains a (1+ε)-approximation to the minimum cut. The algorithm has O((α (n)
log3 n)/ε 2) amortized update time and constant query time, where α (n) stands
for the inverse of Ackermann function."
acknowledgement: "We thank the two anonymous reviewers for their suggestions and comments,
which improved the\r\nquality of the article."
article_number: '17'
article_processing_charge: No
article_type: original
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: Mikkel
full_name: Thorup, Mikkel
last_name: Thorup
citation:
ama: Goranci G, Henzinger M, Thorup M. Incremental exact min-cut in polylogarithmic
amortized update time. ACM Transactions on Algorithms. 2018;14(2). doi:10.1145/3174803
apa: Goranci, G., Henzinger, M., & Thorup, M. (2018). Incremental exact min-cut
in polylogarithmic amortized update time. ACM Transactions on Algorithms.
Association for Computing Machinery. https://doi.org/10.1145/3174803
chicago: Goranci, Gramoz, Monika Henzinger, and Mikkel Thorup. “Incremental Exact
Min-Cut in Polylogarithmic Amortized Update Time.” ACM Transactions on Algorithms.
Association for Computing Machinery, 2018. https://doi.org/10.1145/3174803.
ieee: G. Goranci, M. Henzinger, and M. Thorup, “Incremental exact min-cut in polylogarithmic
amortized update time,” ACM Transactions on Algorithms, vol. 14, no. 2.
Association for Computing Machinery, 2018.
ista: Goranci G, Henzinger M, Thorup M. 2018. Incremental exact min-cut in polylogarithmic
amortized update time. ACM Transactions on Algorithms. 14(2), 17.
mla: Goranci, Gramoz, et al. “Incremental Exact Min-Cut in Polylogarithmic Amortized
Update Time.” ACM Transactions on Algorithms, vol. 14, no. 2, 17, Association
for Computing Machinery, 2018, doi:10.1145/3174803.
short: G. Goranci, M. Henzinger, M. Thorup, ACM Transactions on Algorithms 14 (2018).
date_created: 2022-07-27T11:29:39Z
date_published: 2018-04-01T00:00:00Z
date_updated: 2024-11-06T12:05:51Z
day: '01'
doi: 10.1145/3174803
extern: '1'
external_id:
arxiv:
- '1611.06500'
intvolume: ' 14'
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1611.06500
month: '04'
oa: 1
oa_version: Preprint
publication: ACM Transactions on Algorithms
publication_identifier:
eissn:
- 1549-6333
issn:
- 1549-6325
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Incremental exact min-cut in polylogarithmic amortized update time
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 14
year: '2018'
...
---
_id: '11665'
abstract:
- lang: eng
text: "We study the problem of maintaining a breadth-first spanning tree (BFS tree)
in partially dynamic distributed networks modeling a sequence of either failures
or additions of communication links (but not both). We present deterministic (1+ϵ)-approximation
algorithms whose amortized time (over some number of link changes) is sublinear
in D, the maximum diameter of the network.\r\n\r\nOur technique also leads to
a deterministic (1+ϵ)-approximate incremental algorithm for single-source shortest
paths in the sequential (usual RAM) model. Prior to our work, the state of the
art was the classic exact algorithm of Even and Shiloach (1981), which is optimal
under some assumptions (Roditty and Zwick 2011; Henzinger et al. 2015). Our result
is the first to show that, in the incremental setting, this bound can be beaten
in certain cases if some approximation is allowed."
acknowledgement: "We thank the reviewers of ICALP 2013 for pointing to related articles
and to an error in an example\r\ngiven in a previous version of this article. We
also thank one of the reviewers of Transactions on\r\nAlgorithms for very detailed
comments."
article_number: '51'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Sebastian
full_name: Krinninger, Sebastian
last_name: Krinninger
- first_name: Danupon
full_name: Nanongkai, Danupon
last_name: Nanongkai
citation:
ama: Henzinger M, Krinninger S, Nanongkai D. Sublinear-time maintenance of breadth-first
spanning trees in partially dynamic networks. ACM Transactions on Algorithms.
2017;13(4). doi:10.1145/3146550
apa: Henzinger, M., Krinninger, S., & Nanongkai, D. (2017). Sublinear-time maintenance
of breadth-first spanning trees in partially dynamic networks. ACM Transactions
on Algorithms. Association for Computing Machinery. https://doi.org/10.1145/3146550
chicago: Henzinger, Monika, Sebastian Krinninger, and Danupon Nanongkai. “Sublinear-Time
Maintenance of Breadth-First Spanning Trees in Partially Dynamic Networks.” ACM
Transactions on Algorithms. Association for Computing Machinery, 2017. https://doi.org/10.1145/3146550.
ieee: M. Henzinger, S. Krinninger, and D. Nanongkai, “Sublinear-time maintenance
of breadth-first spanning trees in partially dynamic networks,” ACM Transactions
on Algorithms, vol. 13, no. 4. Association for Computing Machinery, 2017.
ista: Henzinger M, Krinninger S, Nanongkai D. 2017. Sublinear-time maintenance of
breadth-first spanning trees in partially dynamic networks. ACM Transactions on
Algorithms. 13(4), 51.
mla: Henzinger, Monika, et al. “Sublinear-Time Maintenance of Breadth-First Spanning
Trees in Partially Dynamic Networks.” ACM Transactions on Algorithms, vol.
13, no. 4, 51, Association for Computing Machinery, 2017, doi:10.1145/3146550.
short: M. Henzinger, S. Krinninger, D. Nanongkai, ACM Transactions on Algorithms
13 (2017).
date_created: 2022-07-27T11:37:23Z
date_published: 2017-10-01T00:00:00Z
date_updated: 2024-11-06T12:06:03Z
day: '01'
doi: 10.1145/3146550
extern: '1'
external_id:
arxiv:
- '1512.08147'
intvolume: ' 13'
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1512.08147
month: '10'
oa: 1
oa_version: Preprint
publication: ACM Transactions on Algorithms
publication_identifier:
eissn:
- 1549-6333
issn:
- 1549-6325
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Sublinear-time maintenance of breadth-first spanning trees in partially dynamic
networks
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 13
year: '2017'
...