论文标题
可充电链接的加权数据包选择：复杂性和近似值
Weighted Packet Selection for Rechargeable Links: Complexity and Approximation
论文作者
论文摘要
我们考虑一个自然问题，即在可充电链路上选择加权数据包选择，例如，该链接在加密货币网络中找到应用程序。链接$（u，v）$的容量取决于此链接的$ u $ $ u $和$ v $的数量。具体而言，输入是有限有序的数据包序列，这些序列沿着链接沿两个方向到达。给定的$（u，v）$和一包重量$ x $从$ u $到$ v $，player $ u $可以接受或拒绝该数据包。如果播放器$ u $接受数据包，则它们在链接$（u，v）$上的容量减少了$ x $。相应地，$（u，v）$上的player $ v $容量增加了$ x $。如果玩家拒绝数据包，这将需要在数据包的重量中进行成本线性。链接是“可充电”的，因为链接的总能力必须保持恒定，但是链接末端的容量分配可以任意取决于玩家的决定。目标是最大程度地减少注入链接的容量和拒绝数据包的成本。我们表明问题是NP-HARD，但可以有效地近似于$（1+ \ varepsilon）\ cdot（1+ \ sqrt {3}）$的比率（对于某些任意$ \ varepsilon> 0 $）。
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+\sqrt{3})$ for some arbitrary $\varepsilon >0$.
