{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,30]],"date-time":"2026-01-30T06:27:46Z","timestamp":1769754466250,"version":"3.49.0"},"reference-count":0,"publisher":"AI Access Foundation","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["jair"],"abstract":"<jats:p>Distributed constraint optimization (DCOP) problems are a popular way of formulating and solving agent-coordination problems. A DCOP problem is a problem where several agents coordinate their values such that the sum of the resulting constraint costs is minimal. It is often desirable to solve DCOP problems with memory-bounded and asynchronous algorithms. We introduce Branch-and-Bound ADOPT (BnB-ADOPT), a memory-bounded asynchronous DCOP search algorithm that uses the message-passing and communication framework of ADOPT (Modi, Shen, Tambe, &amp; Yokoo, 2005), a well known memory-bounded asynchronous DCOP search algorithm, but changes the search strategy of ADOPT from best-first search to depth-first branch-and-bound search. Our experimental results show that BnB-ADOPT finds cost-minimal solutions up to one order of magnitude faster than ADOPT for a variety of large DCOP problems and is as fast as NCBB, a memory-bounded synchronous DCOP search algorithm, for most of these DCOP problems. Additionally, it is often desirable to find bounded-error solutions for DCOP problems within a reasonable amount of time since finding cost-minimal solutions is NP-hard. The existing bounded-error approximation mechanism allows users only to specify an absolute error bound on the solution cost but a relative error bound is often more intuitive. Thus, we present two new bounded-error approximation mechanisms that allow for relative error bounds and implement them on top of BnB-ADOPT.<\/jats:p>","DOI":"10.1613\/jair.2849","type":"journal-article","created":{"date-parts":[[2018,7,17]],"date-time":"2018-07-17T10:35:57Z","timestamp":1531823757000},"page":"85-133","source":"Crossref","is-referenced-by-count":63,"title":["BnB-ADOPT: An Asynchronous Branch-and-Bound DCOP Algorithm"],"prefix":"10.1613","volume":"38","author":[{"given":"W.","family":"Yeoh","sequence":"first","affiliation":[]},{"given":"A.","family":"Felner","sequence":"additional","affiliation":[]},{"given":"S.","family":"Koenig","sequence":"additional","affiliation":[]}],"member":"16860","published-online":{"date-parts":[[2010,5,23]]},"container-title":["Journal of Artificial Intelligence Research"],"original-title":[],"link":[{"URL":"https:\/\/jair.org\/index.php\/jair\/article\/download\/10650\/25460","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/jair.org\/index.php\/jair\/article\/download\/10650\/25461","content-type":"application\/postscript","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/jair.org\/index.php\/jair\/article\/download\/10650\/25460","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,20]],"date-time":"2019-10-20T18:29:51Z","timestamp":1571596191000},"score":1,"resource":{"primary":{"URL":"https:\/\/jair.org\/index.php\/jair\/article\/view\/10650"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,5,23]]},"references-count":0,"URL":"https:\/\/doi.org\/10.1613\/jair.2849","relation":{},"ISSN":["1076-9757"],"issn-type":[{"value":"1076-9757","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,5,23]]}}}