Weighted packet selection for rechargeable links in cryptocurrency networks: complexity and approximation

DOI10.1007/978-3-031-32733-9_26MaRDI QIDQ6148085zbMATH OpenOpenAlexFDO

Authors Stefan Schmid, Jakub Svoboda, Michelle Yeo

Publication date 11 January 2024

Published in Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2204.13459

zbMATH Keywords

approximation algorithmscomplexitycryptocurrenciesnetwork algorithmspayment channel networks

Mathematics Subject Classification ID

Computer system organization (68Mxx) Communication complexity, information complexity (68Q11) Graph theory (including graph drawing) in computer science (68R10)

Abstract: We consider a natural problem dealing with weighted packet selection across a rechargeable link, which e.g., finds applications in cryptocurrency networks. The capacity of a link $(u,v)$ is determined by how much players $u$ and $v$ allocate for this link. Specifically, the input is a finite ordered sequence of packets that arrive in both directions along a link. Given $(u,v)$ and a packet of weight $x$ going from $u$ to $v$, player $u$ can either accept or reject the packet. If player $u$ accepts the packet, their capacity on link $(u,v)$ decreases by $x$. Correspondingly, player $v$ capacity on $(u,v)$ increases by $x$. If a player rejects the packet, this will entail a cost linear in the weight of the packet. A link is "rechargeable" in the sense that the total capacity of the link has to remain constant, but the allocation of capacity at the ends of the link can depend arbitrarily on players' decisions. The goal is to minimise the sum of the capacity injected into the link and the cost of rejecting packets. We show the problem is NP-hard, but can be approximated efficiently with a ratio of $(1+varepsilon)cdot(1+sqrt3)$ for some arbitrary $varepsilon>0$.

Cites work

• \textsc{Hide} \& \textsc{Seek}: privacy-preserving rebalancing on payment channel networks
• Computational Complexity
• On-line routing of virtual circuits with applications to load balancing and machine scheduling
• Solving Linear Programs in the Current Matrix Multiplication Time
• The all-or-nothing multicommodity flow problem
• The capacity of wireless networks

This page was built for publication: Weighted packet selection for rechargeable links in cryptocurrency networks: complexity and approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6148085)