Pseudo-tree-based algorithm for approximate distributed constraint optimization with quality bounds

Tenda Okimoto; Yongjoon Joe; Atsushi Iwasaki; Makoto Yokoo

Pseudo-tree-based algorithm for approximate distributed constraint optimization with quality bounds

Tenda Okimoto, Yongjoon Joe, Atsushi Iwasaki, Makoto Yokoo

Intelligence Science

Research output: Contribution to conference › Paper › peer-review

Abstract

Most incomplete DCOP algorithms generally do not provide any guarantees on the quality of the solutions. In this paper, we introduce a new incomplete DCOP algorithm that can provide the upper bounds of the absolute/relative errors of the solution, which can be obtained a priori/a posteriori, respectively. The evaluation results illustrate that this algorithm can obtain better quality solutions and bounds compared to existing bounded incomplete DCOP algorithms, while the run time of this algorithm is much shorter.

Original language	English
Pages	1199-1200
Number of pages	2
Publication status	Published - 2011
Event	10th International Conference on Autonomous Agents and Multiagent Systems 2011, AAMAS 2011 - Taipei, Taiwan, Province of China Duration: May 2 2011 → May 6 2011

Other

Other	10th International Conference on Autonomous Agents and Multiagent Systems 2011, AAMAS 2011
Country/Territory	Taiwan, Province of China
City	Taipei
Period	5/2/11 → 5/6/11

All Science Journal Classification (ASJC) codes

Artificial Intelligence

Cite this

Pseudo-tree-based algorithm for approximate distributed constraint optimization with quality bounds. / Okimoto, Tenda; Joe, Yongjoon; Iwasaki, Atsushi et al.
2011. 1199-1200 Paper presented at 10th International Conference on Autonomous Agents and Multiagent Systems 2011, AAMAS 2011, Taipei, Taiwan, Province of China.

Research output: Contribution to conference › Paper › peer-review

@conference{0b7c6392b33145759b96405a0fb4bfc8,

title = "Pseudo-tree-based algorithm for approximate distributed constraint optimization with quality bounds",

abstract = "Most incomplete DCOP algorithms generally do not provide any guarantees on the quality of the solutions. In this paper, we introduce a new incomplete DCOP algorithm that can provide the upper bounds of the absolute/relative errors of the solution, which can be obtained a priori/a posteriori, respectively. The evaluation results illustrate that this algorithm can obtain better quality solutions and bounds compared to existing bounded incomplete DCOP algorithms, while the run time of this algorithm is much shorter.",

author = "Tenda Okimoto and Yongjoon Joe and Atsushi Iwasaki and Makoto Yokoo",

year = "2011",

language = "English",

pages = "1199--1200",

note = "10th International Conference on Autonomous Agents and Multiagent Systems 2011, AAMAS 2011 ; Conference date: 02-05-2011 Through 06-05-2011",

}

TY - CONF

T1 - Pseudo-tree-based algorithm for approximate distributed constraint optimization with quality bounds

AU - Okimoto, Tenda

AU - Joe, Yongjoon

AU - Iwasaki, Atsushi

AU - Yokoo, Makoto

PY - 2011

Y1 - 2011

N2 - Most incomplete DCOP algorithms generally do not provide any guarantees on the quality of the solutions. In this paper, we introduce a new incomplete DCOP algorithm that can provide the upper bounds of the absolute/relative errors of the solution, which can be obtained a priori/a posteriori, respectively. The evaluation results illustrate that this algorithm can obtain better quality solutions and bounds compared to existing bounded incomplete DCOP algorithms, while the run time of this algorithm is much shorter.

AB - Most incomplete DCOP algorithms generally do not provide any guarantees on the quality of the solutions. In this paper, we introduce a new incomplete DCOP algorithm that can provide the upper bounds of the absolute/relative errors of the solution, which can be obtained a priori/a posteriori, respectively. The evaluation results illustrate that this algorithm can obtain better quality solutions and bounds compared to existing bounded incomplete DCOP algorithms, while the run time of this algorithm is much shorter.

UR - http://www.scopus.com/inward/record.url?scp=84899458759&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84899458759&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:84899458759

SP - 1199

EP - 1200

T2 - 10th International Conference on Autonomous Agents and Multiagent Systems 2011, AAMAS 2011

Y2 - 2 May 2011 through 6 May 2011

ER -

Pseudo-tree-based algorithm for approximate distributed constraint optimization with quality bounds

Abstract

Other

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this