Fast Dynamic Programming in Trees in the MPC Model

dc.contributorAalto Universityen
dc.contributor.authorGupta, Chetanen_US
dc.contributor.authorLatypov, Rustamen_US
dc.contributor.authorMaus, Yannicen_US
dc.contributor.authorPai, Shreyasen_US
dc.contributor.authorSärkkä, Simoen_US
dc.contributor.authorStudený, Janen_US
dc.contributor.authorSuomela, Jukkaen_US
dc.contributor.authorUitto, Jaraen_US
dc.contributor.authorVahidi, Hosseinen_US
dc.contributor.departmentDepartment of Computer Scienceen_US
dc.contributor.departmentGraz University of Technologyen_US
dc.contributor.departmentHelsinki Institute for Information Technology (HIIT)en_US
dc.contributor.departmentComputer Science Professorsen_US
dc.contributor.departmentDepartment of Electrical Engineering and Automationen
dc.descriptionFunding Information: We are grateful to Alkida Balliu, Darya Melnyk, and Dennis Olivetti for several fruitful discussions, and to the anonymous reviewers for their helpful feedback on prior versions of this work. This work was supported in part by the Academy of Finland, Grants 321901 (Gupta and Vahidi) and 334238 (Latypov and Pai). Publisher Copyright: © 2023 Owner/Author.
dc.description.abstractWe 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 widely-believed 2-cycle 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 low-diameter 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.en
dc.description.versionPeer revieweden
dc.identifier.citationGupta , C , Latypov , R , Maus , Y , Pai , S , Särkkä , S , Studený , J , Suomela , J , Uitto , J & Vahidi , H 2023 , Fast Dynamic Programming in Trees in the MPC Model . in SPAA 2023 - Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures . ACM , pp. 443-453 , Annual ACM Symposium on Parallelism in Algorithms and Architectures , Orlando , Florida , United States , 17/06/2023 .
dc.identifier.otherPURE UUID: f8c6d87d-41ac-443e-a369-dca2e756a4a0en_US
dc.identifier.otherPURE ITEMURL:
dc.identifier.otherPURE LINK:
dc.identifier.otherPURE FILEURL:
dc.relation.ispartofAnnual ACM Symposium on Parallelism in Algorithms and Architecturesen
dc.relation.ispartofseriesSPAA 2023 - Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architecturesen
dc.subject.keyworddynamic programmingen_US
dc.subject.keywordgraphical modelsen_US
dc.subject.keywordlocally checkable labelingen_US
dc.subject.keywordmassively parallel modelen_US
dc.subject.keywordstatistical inferenceen_US
dc.titleFast Dynamic Programming in Trees in the MPC Modelen
dc.typeConference article in proceedingsfi