标题： 无线链路调度的灵活数据速率近似算法 显示英文标题

标题： Approximation Algorithms for Wireless Link Scheduling with Flexible Data Rates

摘要： 我们考虑无线网络中与灵活数据速率相关的调度问题。也就是说，根据信号质量，每次传输的数据量或多或少，而信号质量由信噪干扰比（SINR）决定。每个无线链路都有一个效用函数，将SINR值映射到相应的数据速率。我们必须决定哪些传输同时进行，并且（根据问题变体）还决定使用哪些传输功率。在容量最大化问题中，目标是最大化整个网络的吞吐量，即所有链路效用的总和。对于任意效用函数（不一定是连续的），当有n个通信请求时，我们提出一个O(log n)近似算法。该算法基于该问题特殊情况的常数因子近似，其中效用函数仅由一个步骤组成。换句话说，每个链路都有一个单独的阈值，我们的目标是最大化满足其阈值的链路数量。在此过程中，这改进了[Kesselheim, SODA 2011]的结果，不仅将其扩展到单独的阈值，还展示了与底层度量空间或网络参数无关的常数近似因子。此外，我们还考虑了延迟最小化问题。在这里，每个链路有一个需求，例如表示数据量。我们必须计算一个尽可能短的调度，使得每个链路的需求得到满足，即总体效用（或传输的数据）至少等于其需求。基于容量最大化算法，我们为此问题展示了O(log^2 n)近似算法。 显示英文摘要

摘要： We consider scheduling problems in wireless networks with respect to flexible data rates. That is, more or less data can be transmitted per time depending on the signal quality, which is determined by the signal-to-interference-plus-noise ratio (SINR). Each wireless link has a utility function mapping SINR values to the respective data rates. We have to decide which transmissions are performed simultaneously and (depending on the problem variant) also which transmission powers are used. In the capacity-maximization problem, one strives to maximize the overall network throughput, i.e., the summed utility of all links. For arbitrary utility functions (not necessarily continuous ones), we present an O(log n)-approximation when having n communication requests. This algorithm is built on a constant-factor approximation for the special case of the respective problem where utility functions only consist of a single step. In other words, each link has an individual threshold and we aim at maximizing the number of links whose threshold is satisfied. On the way, this improves the result in [Kesselheim, SODA 2011] by not only extending it to individual thresholds but also showing a constant approximation factor independent of assumptions on the underlying metric space or the network parameters. In addition, we consider the latency-minimization problem. Here, each link has a demand, e.g., representing an amount of data. We have to compute a schedule of shortest possible length such that for each link the demand is fulfilled, that is the overall summed utility (or data transferred) is at least as large as its demand. Based on the capacity-maximization algorithm, we show an O(log^2 n)-approximation for this problem.