Skip to main content

Research Repository

Advanced Search

Decentralized combinatorial optimization.

Christie, Lee A.

Authors



Contributors

Thomas Bäck
Editor

Mike Preuss
Editor

André Deutz
Editor

Hao Wang
Editor

Carola Doerr
Editor

Michael Emmerich
Editor

Heike Trautmann
Editor

Abstract

Combinatorial optimization is a widely-studied class of computational problems with many theoretical and real-world applications. Optimization problems are typically tackled using hardware and software controlled by the user. Optimization can be competitive where problems are solved by competing agents in isolation, or by groups sharing hardware and software in a distributed manner. Blockchain technology enables decentralized applications (DApps). Optimization as a DApp would be run in a trustless manner where participation in the system is voluntary and problem-solving is incentivized with bitcoin, ether, or other fungible tokens. Using a purpose-built blockchain introduces the problem of bootstrapping robust immutability and token value. This is solved by building a DApp as a smart-contract on top of an existing Turing-complete blockchain platform such as Ethereum. We propose a means of using Ethereum Virtual Machine smart contracts to automate the payout of cryptocurrency rewards for market-based voluntary participation in the solution of combinatorial optimization problems without trusted intermediaries. We suggest use of this method for optimization-as-a-service, automation of contests, and long-term recording of best-known solutions.

Citation

CHRISTIE, L.A. 2020. Decentralized combinatorial optimization. In B├Ąck, T., Preuss, M., Deutz, A., Wang, H., Doerr, C., Emmerich, M. and Trautmann, H. (eds.) Parallel problem solving from nature: PPSN XVI: proceedings of the 16th Parallel problem solving from nature international conference (PPSN 2020), 5-9 September 2020, Leiden, Netherlands. Theoretical computer science and general issues, 12269. Cham; Springer, pages 360-372. Available from: https://doi.org/10.1007/978-3-030-58112-1_25

Conference Name 16th Parallel problem solving from nature international conference 2020 (PPSN 2020)
Conference Location Leiden, The Netherlands
Start Date Sep 5, 2020
End Date Sep 9, 2020
Acceptance Date May 28, 2020
Online Publication Date Aug 31, 2020
Publication Date Dec 31, 2020
Deposit Date Sep 22, 2020
Publicly Available Date Sep 22, 2020
Publisher Springer
Volume 12269
Pages 360-372
Series Title Lecture notes in computer science
Series ISSN 0302-9743
Book Title Parallel problem solving from nature: PPSN XVI: proceedings of the 16th Parallel problem solving from nature international conference (PPSN 2020), 5-9 September 2020, Leiden, The Netherlands.
ISBN 9783030581114
DOI https://doi.org/10.1007/978-3-030-58112-1_25
Keywords Combinatorial optimization; Computational problem; Blockchain technology; DApp
Public URL https://rgu-repository.worktribe.com/output/969437

Files





You might also like



Downloadable Citations