Constant Cost of the Computation-Unit in Efficiency Graphs for DCOP Solvers

Author

Silaghi, Marius C. ; Lass, Robert N. ; Sultanik, Evan A. ; Regli, William C. ; Matsui, Toshihiro ; Yokoo, Makoto

Author_Institution

Florida Tech, Melbourne, FL

Volume

2

fYear

2008

fDate

9-12 Dec. 2008

Firstpage

380

Lastpage

384

Abstract

We show how to ensure a constant cost for the computation-unit in graphs depicting the number of (sequential) computation-units at different (distributed) problem sizes. We report empirical evaluation with ADOPT revealing that the computation cost associated with constraint check (commonly used - and assumed constant - in ENCCCs evaluations) actually varies with the problem size, by orders of magnitude. We therefore propose better computation-units based on a basket of weighted constraint-checks and contexts processing operations.

Keywords

computational complexity; constraint theory; distributed algorithms; graph theory; optimisation; ADOPT; DCOP solver; distributed constraint optimization algorithm; empirical evaluation; graph computation-unit cost; time complexity; weighted constraint-check; Clocks; Computational efficiency; Cost function; Delay; Distributed computing; Intelligent agent; Logic; Particle measurements; Proposals; Random number generation; distributed constraint reasoning; metrics;

fLanguage

English

Publisher

ieee

Conference_Titel

Web Intelligence and Intelligent Agent Technology, 2008. WI-IAT '08. IEEE/WIC/ACM International Conference on

Conference_Location

Sydney, NSW

Print_ISBN

978-0-7695-3496-1

Type

conf

DOI

10.1109/WIIAT.2008.427

Filename

4740652