TitleSaving Messages in ADOPT-based Algorithms
Publication TypeConference Paper
Year of Publication2010
AuthorsGutierrez P, Meseguer P
Conference NameAAMAS 2010 workshop: Distributed Constraint Reasoning
Conference LocationToronto, Canada

ADOPT and BnB-ADOPT are two related algorithms essential for distributed constraint optimization. They exchange a large number of messages, which is a major drawback for their practical usage. Aiming at increasing their efficiency, we present results showing that some of their messages are redundant so they can be removed without compromising their optimality and termination properties. Removing most of those redundant messages we obtain ADOPT$^+$ and BnB-ADOPT$^+$, which in practice, cause substantial reductions on communication costs with respect to the original algorithms.