@InProceedings{davin05a,
  author =	 {John Davin and Pragnesh Jay Modi},
  title =	 {Impact of Problem Centralization in Distributed
                  Constraint Optimization Algorithms},
  booktitle =	 {Proceedings of the Fourth International Joint
                  Conference on Autonomous Agents and MultiAgent
                  Systems},
  crossref =	 {aamas05},
  pages =	 {1057--1066},
  year =	 2005,
  abstract =	 {Recent progress in Distributed Constraint
                  Optimization Problems (DCOP) has led to a range of
                  algorithms now available which differ in their
                  amount of problem centralization. Problem
                  centralization can have a significant impact on the
                  amount of computation required by an agent but
                  unfortunately the dominant evaluation metric of
                  ``number of cycles'' fails to account for this
                  cost. We analyze the relative performance of two
                  recent algorithms for DCOP: OptAPO, which performs
                  partial centralization, and Adopt, which maintains
                  distribution of the DCOP. Previous comparison of
                  Adopt and OptAPO has found that OptAPO requires
                  fewer cycles than Adopt. We extend the cycles metric
                  to define ``Cycle-Based Runtime (CBR)'' to account
                  for both the amount of computation required in each
                  cycle and the communication latency between
                  cycles. Using the CBR metric, we show that Adopt
                  outperforms OptAPO under a range of communication
                  latencies. We also ask: What level of centralization
                  is most suitable for a given communication latency?
                  We use CBR to create performance curves for three
                  algorithms that vary in degree of centralization,
                  namely Adopt, OptAPO, and centralized Branch and
                  Bound search.},
  keywords =     {multiagent distributed-search dcop},
  url = 	 {http://jmvidal.cse.sc.edu/library/davin05a.pdf},
  googleid = 	 {m23paRkdgGIJ:scholar.google.com/},
  cluster = 	 {7097705007724195227}
}