Not logged in.
Quick Search - Contribution
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 | |
| Authors |
|
| Presentation Type | paper |
| Item Subtype | Original Work |
| Refereed | Yes |
| Status | Published in final form |
| Language |
|
| 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 | http://www.cs.nmsu.edu/~wyeoh/OPTMAS2016/docs/OPTMAS_2016_paper_4.pdf |
| Other Identification Number | merlin-id:13342 |
| PDF File |
Download from ZORA
|
| Export |
BibTeX
EP3 XML (ZORA)
|