Current Location:home > Browse

1. chinaXiv:202110.00056 [pdf]

Resonance Algorithm: A New Look at the Shortest Path Problem

Liu, Yu; Lin, Qiguang; Hong, Binbin; Hjerpe, Daniel; Liu, Xiaofeng
Subjects: Mathematics >> Applied Mathematics
Subjects: Information Science and Systems Science >> Other Disciplines of Information Science and Systems Science

The shortest path problem (SPP) is a classic problem and appears in a wide range of applications. Although a variety of algorithms already exist, new advances are still being made, mainly tuned for particular scenarios to have better performances. As a result, they become more and more technically complex and sophisticated. Here we developed a novel nature-inspired algorithm to compute all possible shortest paths between two nodes in a graph: Resonance Algorithm (RA), which is surprisingly simple and intuitive. Besides its simplicity, RA turns out to be much more time-efficient for large-scale graphs than the extended Dijkstra's algorithm (such that it gives all possible shortest paths). Moreover, RA can handle any undirected, directed, or mixed graphs, irrespective of loops, unweighted or positively-weighted edges, and can be implemented in a fully decentralized manner. These good properties ensure RA a wide range of applications.

submitted time 2021-10-11 Hits2806Downloads295 Comment 0

2. chinaXiv:202004.00005 [pdf]

金融科技中支持区块链生态系统的一般共识博弈框架

袁先智
Subjects: Mathematics >> Applied Mathematics
Subjects: Information Science and Systems Science >> Other Disciplines of Information Science and Systems Science

本文的目的是建立区块链生态系统中采矿池博弈共识均衡的一般框架,特别是在区块链生态系统中,通过使用一个新的概念“共识博弈(Consensus Game)”,解释与挖掘差距(Gap Games)博弈行为相关的共识均衡存在的意义上的稳定性,这里,区块链生态系统主要是指应用2008年中本聪(Nakamoto)所提出的“工作证明”(Proof of Work) 这一关键共识,将区块链工作的费用、报酬机制和采矿权三类不同因素考虑在内的经济活动。 为了做到这一点,我们首先概述了采矿池游戏共识均衡的一般存在性是如何表述的,然后通过区块链共识框架下共识均衡的存在性来解释比特币缺口博弈 (Gap博弈) 稳定性,然后利用博弈论中矿工的利润函数作为收益,建立了一般矿业缺口博弈一致均衡的一般存在性结果。作为应用,建立了缺口博弈 (Gap博弈)一致均衡的一般存在性结果,这不仅有助于我们在区块链生态系统的一般框架下断言缺口博弈 (Gap博弈) 的一般稳定性的存在性,但也让我们能够说明在研究采矿池博弈时的一些不同现象,这些现象可能是由于采矿者的(Gap博弈)行为与嵌入比特币经济学的情景造成的。 我们对区块链生态系统挖掘缺口博弈稳定性的解释研究表明,共识均衡的概念可能对共识经济学基础理论的发展起到重要作用

submitted time 2020-03-31 Hits23352Downloads1960 Comment 0

  [1 Pages/ 2 Totals]