Loading...
Loading...

Go to the content (press return)

Decomposing utility functions in bounded max-sum for distributed constraint optimization

Author
Rollon, E.; Larrosa, J.
Type of activity
Presentation of work at congresses
Name of edition
4th Global Congres on Intelligent Systems
Date of publication
2014
Presentation's date
2013-03-03
Book of congress proceedings
2013 Fourth Global Congress on Intelligent Systems, GCIS 2013: 3-4 December 2013, Hong Kong, China: proceedings
First page
30
Last page
33
DOI
10.1109/GCIS.2013.11
Project funding
RESTRICCIONES BLANDAS CON PESOS: CASOS CENTRALIZADO Y DISTRIBUIDO
Abstract
Bounded Max-Sum is a message-passing algorithm for solving Distributes Constraint Optimization Problems (DCOP) able to compute solutions with a guaranteed approximation ratio. In this paper we show that the introduction of an intermediate step that decomposes functions may significantly improve its accuracy. This is especially relevant in critical applications (e.g. automatic surveillance, disaster response scenarios) where the accuracy of solutions is of vital importance.
Keywords
Approximate algorithms, Decomposition, Distributed constraint optimization problems
Group of research
LOGPROG - Logic and Programming

Participants