Projekteja vuodessa
Abstrakti
We present a deterministic algorithm for solving a wide range of dynamic programming problems in trees in O(log D) rounds in the massively parallel computation model (MPC), with O(nδ) words of local memory per machine, for any given constant 0 < δ< 1. Here D is the diameter of the tree and n is the number of nodes  we emphasize that our running time is independent of n. Our algorithm can solve many classical graph optimization problems such as maximum weight independent set, maximum weight matching, minimum weight dominating set, and minimum weight vertex cover. It can also be used to solve many accumulation tasks in which some aggregate information is propagated upwards or downwards in the tree  this includes, for example, computing the sum, minimum, or maximum of the input labels in each subtree, as well as many inference tasks commonly solved with belief propagation. Our algorithm can also solve any locally checkable labeling problem (LCLs) in trees. Our algorithm works for any reasonable representation of the input tree; for example, the tree can be represented as a list of edges or as a string with nested parentheses or tags. The running time of O(log D) rounds is also known to be necessary, assuming the widelybelieved 2cycle conjecture. Our algorithm strictly improves on two prior algorithms: Bateni, Behnezhad, Derakhshan, Hajiaghayi, and Mirrokni [ICALP'18] solve problems of these flavors in O(log n) rounds, while our algorithm is much faster in lowdiameter trees. Furthermore, their algorithm also uses randomness, while our algorithm is deterministic. Balliu, Latypov, Maus, Olivetti, and Uitto [SODA'23] solve only locally checkable labeling problems in O(log D) rounds, while our algorithm can be applied to a much broader family of problems.
Alkuperäiskieli  Englanti 

Otsikko  SPAA 2023  Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures 
Kustantaja  ACM 
Sivut  443453 
Sivumäärä  11 
ISBN (elektroninen)  9781450395458 
DOI  pysyväislinkit  
Tila  Julkaistu  17 kesäk. 2023 
OKMjulkaisutyyppi  A4 Artikkeli konferenssijulkaisussa 
Tapahtuma  Annual ACM Symposium on Parallelism in Algorithms and Architectures  Orlando, Yhdysvallat Kesto: 17 kesäk. 2023 → 19 kesäk. 2023 Konferenssinumero: 35 
Conference
Conference  Annual ACM Symposium on Parallelism in Algorithms and Architectures 

Lyhennettä  SPAA 
Maa/Alue  Yhdysvallat 
Kaupunki  Orlando 
Ajanjakso  17/06/2023 → 19/06/2023 
Sormenjälki
Sukella tutkimusaiheisiin 'Fast Dynamic Programming in Trees in the MPC Model'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.
: Massively Parallel Algorithms for LargeScale Graph Problems
Uitto, J., Cambus, M., Latypov, R. & Pai, S.
01/09/2020 → 31/08/2024
Projekti: Academy of Finland: Other research funding

: Rinnakkaisen ja hajautetun laskennan menetelmiä bayesilaisille graafisille malleille
Suomela, J., Vahidi, H., Hirvonen, J., Gupta, C. & Studeny, J.
04/09/2019 → 30/04/2023
Projekti: Academy of Finland: Other research funding