Decentralized combinatorial optimization.

Christie, Lee A.

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