GDBA Revisited: Unleashing the Power of Guided Local Search for Distributed Constraint Optimization
Yanchen Deng, Xinrun Wang, Bo An · 2025
Read GDBA Revisited: Unleashing the Power of Guided Local Search for Distributed Constraint Optimization by Yanchen Deng, Xinrun Wang, Bo An (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-2508-06899.txt.
Description
Yanchen Deng, Xinrun Wang, and Bo An revisit a well-known local search algorithm for problems where many agents must agree under constraints, in a paper from 2025. Local search is fast but often settles for poor answers. The older algorithm, GDBA, added penalty rules to escape bad spots, yet gained little on realistic problems.
The team finds three flaws: rules that punish too eagerly, penalties that grow without bound, and updates that clash between agents. Their fix, DGLS, punishes costly constraints with care, lets penalties fade over time, and syncs updates across agents. Theory shows the penalties stay bounded. On benchmarks, the new method beat leading rivals, and on structured problems it won by wide margins at every time check.
Catalog record
| CREATOR | Yanchen Deng, Xinrun Wang, Bo An |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 41 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-06899