Earlier Version

Weighted acket selection for rechargeable links in cryptocurrency networks: Complexity and approximation

Schmid S, Svoboda J, Yeo MX. 2023. Weighted acket selection for rechargeable links in cryptocurrency networks: Complexity and approximation. 30th International Colloquium on Structural Information and Communication Complexity. SIROCCO: International Colloquium on Structural Information and Communication Complexity, LNCS, vol. 13892, 576–594.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published | English

Scopus indexed
Author

Corresponding author has ISTA affiliation

Series Title
LNCS
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 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 (u, v) 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 + square3) for some arbitrary E>0.
Publishing Year
Date Published
2023-05-25
Proceedings Title
30th International Colloquium on Structural Information and Communication Complexity
Publisher
Springer Nature
Acknowledgement
We thank Mahsa Bastankhah and Mohammad Ali Maddah-Ali for fruitful discussions about different variants of the problem. This work is supported by the European Research Council (ERC) Consolidator Project 864228 (AdjustNet), 2020-2025, the ERC CoG 863818 (ForM-SMArt), and the German Research Foundation (DFG) grant 470029389 (FlexNets), 2021–2024.
Volume
13892
Page
576-594
Conference
SIROCCO: International Colloquium on Structural Information and Communication Complexity
Conference Location
Alcalá de Henares, Spain
Conference Date
2023-06-06 – 2023-06-09
ISSN
eISSN
IST-REx-ID

Cite this

Schmid S, Svoboda J, Yeo MX. Weighted acket selection for rechargeable links in cryptocurrency networks: Complexity and approximation. In: 30th International Colloquium on Structural Information and Communication Complexity. Vol 13892. Springer Nature; 2023:576-594. doi:10.1007/978-3-031-32733-9_26
Schmid, S., Svoboda, J., & Yeo, M. X. (2023). Weighted acket selection for rechargeable links in cryptocurrency networks: Complexity and approximation. In 30th International Colloquium on Structural Information and Communication Complexity (Vol. 13892, pp. 576–594). Alcalá de Henares, Spain: Springer Nature. https://doi.org/10.1007/978-3-031-32733-9_26
Schmid, Stefan, Jakub Svoboda, and Michelle X Yeo. “Weighted Acket Selection for Rechargeable Links in Cryptocurrency Networks: Complexity and Approximation.” In 30th International Colloquium on Structural Information and Communication Complexity, 13892:576–94. Springer Nature, 2023. https://doi.org/10.1007/978-3-031-32733-9_26.
S. Schmid, J. Svoboda, and M. X. Yeo, “Weighted acket selection for rechargeable links in cryptocurrency networks: Complexity and approximation,” in 30th International Colloquium on Structural Information and Communication Complexity, Alcalá de Henares, Spain, 2023, vol. 13892, pp. 576–594.
Schmid S, Svoboda J, Yeo MX. 2023. Weighted acket selection for rechargeable links in cryptocurrency networks: Complexity and approximation. 30th International Colloquium on Structural Information and Communication Complexity. SIROCCO: International Colloquium on Structural Information and Communication Complexity, LNCS, vol. 13892, 576–594.
Schmid, Stefan, et al. “Weighted Acket Selection for Rechargeable Links in Cryptocurrency Networks: Complexity and Approximation.” 30th International Colloquium on Structural Information and Communication Complexity, vol. 13892, Springer Nature, 2023, pp. 576–94, doi:10.1007/978-3-031-32733-9_26.

Export

Marked Publications

Open Data ISTA Research Explorer

Search this title in

Google Scholar
ISBN Search