---
title: "Generalizing ADOPT and BnB-ADOPT"
authors:
  - "Patricia Gutierrez"
  - "Pedro Meseguer"
  - "William Yeoh"
doi: "10.5591/978-1-57735-516-8/IJCAI11-100"
url: "https://ijcai.org/proceedings/2011/100"
pdf: "https://ijcai.org/proceedings/2011/0100.pdf"
venue: "Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence"
year: 2011
pages: "554-558"
track: ""
keywords:
---

# Generalizing ADOPT and BnB-ADOPT

Patricia Gutierrez, Pedro Meseguer, William Yeoh

*Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence*, pages 554-558. DOI: [10.5591/978-1-57735-516-8/IJCAI11-100](https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-100)

## Abstract

ADOPT and BnB-ADOPT are two optimal DCOP search algorithms that are similar except for their search strategies: the former uses best-first search and the latter uses depth-first branch-and-bound search. In this paper, we present a new algorithm, called ADOPT(k), that generalizes them. Its behavior depends on the k parameter. It behaves like ADOPT when k = 1, like BnB-ADOPT when k = ∞ and like a hybrid of ADOPT and BnB-ADOPT when 1 < k < ∞. We prove that ADOPT(k) is a correct and complete algorithm and experimentally show that ADOPT(k) outperforms ADOPT and BnB-ADOPT on several benchmarks across several metrics.