Latency-Aware 2-Opt Monotonic Local Search for Distributed Constraint Optimization

Ben Rachmut, Roie Zivan, William Yeoh · 2025

Read Latency-Aware 2-Opt Monotonic Local Search for Distributed Constraint Optimization by Ben Rachmut, Roie Zivan, William Yeoh (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-08737.txt.

Description

Ben Rachmut, Roie Zivan, and William Yeoh improve how groups of software agents settle shared constraints when their messages can be delayed, in a 2025 paper. Such delays are normal in real networks, and many classic algorithms assume instant delivery.

Existing delay-proof local search methods can only promise a weak form of optimality, where no single agent can improve alone. The authors' method, LAMDLS-2, has agents pair up and swap assignments together. That lifts the guarantee to pairs: no two agents can jointly do better. The method never backslides and tolerates arbitrary delays. In tests it reached the same quality as a benchmark method but faster, across delay patterns. It suits systems from sensor networks to scheduling.

Catalog record

CREATORBen Rachmut, Roie Zivan, William Yeoh
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE47 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-08737

Browse the full library · About the Tower of Babel