Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation
Schmid, Stefan
Svoboda, Jakub
Yeo, Michelle X
General Computer Science
Theoretical Computer Science
ddc:000
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 many nodes 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, node u can either accept or reject the packet. If u accepts the packet, the capacity on link (u, v) decreases by x. Correspondingly, v's capacity on
increases by x. If a node rejects the packet, this will entail a cost affinely 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 the nodes' decisions. The goal is to minimise the sum of the capacity injected into the link and the cost of rejecting packets. We show that the problem is NP-hard, but can be approximated efficiently with a ratio of (1+E) . (1+3) for some arbitrary E>0.
Elsevier
2024
info:eu-repo/semantics/article
doc-type:article
text
http://purl.org/coar/resource_type/c_6501
https://research-explorer.ista.ac.at/record/14820
https://research-explorer.ista.ac.at/download/14820/17263
Schmid S, Svoboda J, Yeo MX. Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation. <i>Theoretical Computer Science</i>. 2024;989. doi:<a href="https://doi.org/10.1016/j.tcs.2023.114353">10.1016/j.tcs.2023.114353</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.1016/j.tcs.2023.114353
info:eu-repo/semantics/altIdentifier/issn/0304-3975
info:eu-repo/grantAgreement/EC/H2020/863818
https://creativecommons.org/licenses/by/4.0/
info:eu-repo/semantics/openAccess