---
OA_place: publisher
OA_type: hybrid
_id: '17236'
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.\r\nWe 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.\r\nWe also revisit Sherman's chaining
    algorithm, and present a simpler version together with a new analysis."
article_processing_charge: Yes (via OA deal)
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. In: <i>Proceedings of the 36th ACM Symposium on Parallelism
    in Algorithms and Architectures</i>. Association for Computing Machinery; 2024:403-414.
    doi:<a href="https://doi.org/10.1145/3626183.3659969">10.1145/3626183.3659969</a>'
  apa: 'Kolmogorov, V. (2024). A simpler and parallelizable O(√log n)-approximation
    algorithm for sparsest cut. In <i>Proceedings of the 36th ACM Symposium on Parallelism
    in Algorithms and Architectures</i> (pp. 403–414). Nantes, France: Association
    for Computing Machinery. <a href="https://doi.org/10.1145/3626183.3659969">https://doi.org/10.1145/3626183.3659969</a>'
  chicago: Kolmogorov, Vladimir. “A Simpler and Parallelizable O(√log n)-Approximation
    Algorithm for Sparsest Cut.” In <i>Proceedings of the 36th ACM Symposium on Parallelism
    in Algorithms and Architectures</i>, 403–14. Association for Computing Machinery,
    2024. <a href="https://doi.org/10.1145/3626183.3659969">https://doi.org/10.1145/3626183.3659969</a>.
  ieee: V. Kolmogorov, “A simpler and parallelizable O(√log n)-approximation algorithm
    for sparsest cut,” in <i>Proceedings of the 36th ACM Symposium on Parallelism
    in Algorithms and Architectures</i>, Nantes, France, 2024, pp. 403–414.
  ista: 'Kolmogorov V. 2024. A simpler and parallelizable O(√log n)-approximation
    algorithm for sparsest cut. Proceedings of the 36th ACM Symposium on Parallelism
    in Algorithms and Architectures. SPAA: Symposium on Parallelism in Algorithms
    and Architectures, 403–414.'
  mla: Kolmogorov, Vladimir. “A Simpler and Parallelizable O(√log n)-Approximation
    Algorithm for Sparsest Cut.” <i>Proceedings of the 36th ACM Symposium on Parallelism
    in Algorithms and Architectures</i>, Association for Computing Machinery, 2024,
    pp. 403–14, doi:<a href="https://doi.org/10.1145/3626183.3659969">10.1145/3626183.3659969</a>.
  short: V. Kolmogorov, in:, Proceedings of the 36th ACM Symposium on Parallelism
    in Algorithms and Architectures, Association for Computing Machinery, 2024, pp.
    403–414.
conference:
  end_date: 2024-06-21
  location: Nantes, France
  name: 'SPAA: Symposium on Parallelism in Algorithms and Architectures'
  start_date: 2024-06-17
corr_author: '1'
date_created: 2024-07-14T22:01:11Z
date_published: 2024-06-17T00:00:00Z
date_updated: 2026-01-21T09:46:25Z
day: '17'
ddc:
- '510'
department:
- _id: VlKo
doi: 10.1145/3626183.3659969
external_id:
  arxiv:
  - '2307.00115'
  isi:
  - '001253331900044'
file:
- access_level: open_access
  checksum: 6ca18ac8508719dbd5d5735f4c991af2
  content_type: application/pdf
  creator: dernst
  date_created: 2024-07-16T06:38:08Z
  date_updated: 2024-07-16T06:38:08Z
  file_id: '17245'
  file_name: 2024_SPAA_Kolmogorov.pdf
  file_size: 1116166
  relation: main_file
  success: 1
file_date_updated: 2024-07-16T06:38:08Z
fulldoi: https://doi.org/10.1145/3626183.3659969
has_accepted_license: '1'
isi: 1
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 403-414
publication: Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and
  Architectures
publication_identifier:
  isbn:
  - '9798400704161'
  issn:
  - 1548-6109
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
related_material:
  record:
  - id: '21007'
    relation: extended_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: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
year: '2024'
...