---
res:
bibo_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 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 \r\n 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.@eng"
bibo_authorlist:
- foaf_Person:
foaf_givenName: Stefan
foaf_name: Schmid, Stefan
foaf_surname: Schmid
- foaf_Person:
foaf_givenName: Jakub
foaf_name: Svoboda, Jakub
foaf_surname: Svoboda
foaf_workInfoHomepage: http://www.librecat.org/personId=130759D2-D7DD-11E9-87D2-DE0DE6697425
orcid: 0000-0002-1419-3267
- foaf_Person:
foaf_givenName: Michelle X
foaf_name: Yeo, Michelle X
foaf_surname: Yeo
foaf_workInfoHomepage: http://www.librecat.org/personId=2D82B818-F248-11E8-B48F-1D18A9856A87
orcid: 0009-0001-3676-4809
bibo_doi: 10.1016/j.tcs.2023.114353
bibo_volume: 989
dct_date: 2024^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/0304-3975
dct_language: eng
dct_publisher: Elsevier@
dct_subject:
- General Computer Science
- Theoretical Computer Science
dct_title: 'Weighted packet selection for rechargeable links in cryptocurrency networks:
Complexity and approximation@'
...