Header

UZH-Logo

Maintenance Infos

Improving Approximate Algorithms for DCOPs Using Ranks


Flückiger, Andreas; Verman, Mihaela; Bernstein, Abraham (2016). Improving Approximate Algorithms for DCOPs Using Ranks. In: International Workshop on Optimisation in Multi-Agent Systems, Singapore, 10 May 2016 - 10 May 2016.

Abstract

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.

Abstract

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.

Statistics

Downloads

16 downloads since deposited on 06 Jul 2016
9 downloads since 12 months
Detailed statistics

Additional indexing

Item Type:Conference or Workshop Item (Paper), refereed, original work
Communities & Collections:03 Faculty of Economics > Department of Informatics
Dewey Decimal Classification:000 Computer science, knowledge & systems
Language:English
Event End Date:10 May 2016
Deposited On:06 Jul 2016 13:04
Last Modified:06 Jul 2016 18:30
Publisher:s.n.
Free access at:Official URL. An embargo period may apply.
Official URL:http://www.cs.nmsu.edu/~wyeoh/OPTMAS2016/docs/OPTMAS_2016_paper_4.pdf
Other Identification Number:merlin-id:13342

Download

Download PDF  'Improving Approximate Algorithms for DCOPs Using Ranks'.
Preview
Filetype: PDF
Size: 555kB