Not logged in.

Contribution Details

Type Conference or Workshop Paper
Scope Discipline-based scholarship
Published in Proceedings Yes
Title Improving Approximate Algorithms for DCOPs Using Ranks
Organization Unit
  • Andreas Flückiger
  • Coralia-Mihaela Verman
  • Abraham Bernstein
Presentation Type paper
Item Subtype Original Work
Refereed Yes
Status Published in final form
  • English
Event Title International Workshop on Optimisation in Multi-Agent Systems
Event Type workshop
Event Location Singapore
Event Start Date May 10 - 2016
Event End Date May 10 - 2016
Publisher s.n.
Abstract Text Distributed Constraint Optimization Problems (DCOPs) have long been studied for problems that need scaling and are inherently distributed. As complete algorithms are exponential, approximate algorithms such as the Distributed Stochastic Algorithm (DSA) and Distributed Simulated Annealing (DSAN) have been proposed to reach solutions fast. Combining DSA with the PageRank algorithm has been studied before as a method to increase convergence speed, but without significant improvements in terms of solution quality when comparing with DSA. We propose a modification in terms of the rank calculation and we introduce three new algorithms, based on DSA and DSAN, to find approximate solutions to DCOPs. Our experiments with graph coloring problems and randomized DCOPs show good results in terms of solution quality in particular for the new DSAN based algorithms. They surpass the classical DSA and DSAN in the longer term, and are only outperformed in a few cases, by the new DSA based algorithm.
Free access at Official URL
Official URL
Other Identification Number merlin-id:13342
PDF File Download from ZORA
Export BibTeX