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

Autor:	Evan A. Sultanik, William C. Regli, Makoto Yokoo, Robert N. Lass, Toshihiro Matsui, Marius Silaghi
Rok vydání:	2008
Předmět:	Constraint (information theory) Orders of magnitude (bit rate) Mathematical optimization Computational complexity theory Distributed algorithm Computer science Computation Algorithm design Graph theory Constant (mathematics)
Zdroj:	IAT
DOI:	10.1109/wiiat.2008.427
Popis:	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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::9280bbe1081d1447d811eeaa3ad1e427 https://doi.org/10.1109/wiiat.2008.427 Zobrazit plný text záznamu