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

arXiv: https://arxiv.org/abs/2504.08737 · HTML: https://mlsanity.com/paper/2504.08737/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 2 of its 27 references that are in the map.
- First posted on arXiv 21 Feb 2025.

## Builds on (most cited first, 2 of 2)

- [Distributed Constraint Optimization Problems and Applications: A Survey](https://mlsanity.com/paper/1602.06347/) (2016)
- [BnB-ADOPT: An Asynchronous Branch-and-Bound DCOP Algorithm](https://mlsanity.com/paper/1401.3490/) (2014)

## Abstract (arXiv)

Researchers recently extended Distributed Constraint Optimization Problems (DCOPs) to Communication-Aware DCOPs so that they are applicable in scenarios in which messages can be arbitrarily delayed. Distributed asynchronous local search and inference algorithms designed for CA-DCOPs are less vulnerable to message latency than their counterparts for regular DCOPs. However, unlike local search algorithms for (regular) DCOPs that converge to k-opt solutions (with k > 1), that is, they converge to solutions that cannot be improved by a group of k agents), local search CA-DCOP algorithms are limited to 1-opt solutions only. In this paper, we introduce Latency-Aware Monotonic Distributed Local Search-2 (LAMDLS-2), where agents form pairs and coordinate bilateral assignment replacements. LAMDLS-2 is monotonic, converges to a 2-opt solution, and is also robust to message latency, making it suitable for CA-DCOPs. Our results indicate that LAMDLS-2 converges faster than MGM-2, a benchmark algorithm, to a similar 2-opt solution, in various message latency scenarios.