Por favor, use este identificador para citar o enlazar a este item:
http://hdl.handle.net/10261/160165
COMPARTIR / EXPORTAR:
SHARE CORE BASE | |
Visualizar otros formatos: MARC | Dublin Core | RDF | ORE | MODS | METS | DIDL | DATACITE | |
Título: | Cluster tree elimination for distributed constraint optimization with quality guarantees |
Autor: | Brito, Ismel; Meseguer, Pedro CSIC ORCID | Palabras clave: | Function filtering Distributed constraint optimizations Distributed cluster-tree elimination |
Fecha de publicación: | 2010 | Editor: | IOS Press | Citación: | Fundamenta Informaticae 102: 263- 286 (2010) | Resumen: | Some distributed constraint optimization algorithms use a linear number of messages in the number of agents, but of exponential size. This is often the main limitation for their practical applicability. Here we present some distributed algorithms for these problems when they are arranged in a tree of agents. The exact algorithm, DCTE, computes the optimal solution but requires messages of size exp(s), where s is a structural parameter. Its approximate version, DMCTE(r), requires smaller messages of size exp(r), r < s, at the cost of computing approximate solutions. It provides a cost interval that bounds the error of the approximation. Using the technique of cost function filtering, we obtain DMCTEf(r). Combining cost function filtering with bound reasoning, we propose DIMCTEf, an algorithm based on repeated executions of DMCTEf(r) with increasing r. DIMCTEf uses messages of previous iterations to decrease the size of messages in the current iteration, which allows to alleviate their high size. We provide evidences of the benefits of our approach on two benchmarks. | URI: | http://hdl.handle.net/10261/160165 | DOI: | 10.3233/FI-2010-308 | Identificadores: | doi: 10.3233/FI-2010-308 issn: 0169-2968 |
Aparece en las colecciones: | (IIIA) Artículos |
Ficheros en este ítem:
Fichero | Descripción | Tamaño | Formato | |
---|---|---|---|---|
accesoRestringido.pdf | 15,38 kB | Adobe PDF | Visualizar/Abrir |
CORE Recommender
SCOPUSTM
Citations
14
checked on 01-abr-2024
WEB OF SCIENCETM
Citations
7
checked on 25-feb-2024
Page view(s)
241
checked on 18-abr-2024
Download(s)
26
checked on 18-abr-2024
Google ScholarTM
Check
Altmetric
Altmetric
NOTA: Los ítems de Digital.CSIC están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.