Online covering with $$\ell _q$$-norm objectives and applications to network design
Online covering with $$\ell _q$$-norm objectives and applications to network design
复制标题
在线涵盖 $$ell _q$$-规范目标和网络设计应用
DOI：
10.1007/s10107-019-01409-9
复制
发表时间：
2020
影响因子：
2.7
通讯作者：
Nagarajan, Viswanath
中科院分区：
文献类型：
--
作者：
Shen, Xiangkun;Nagarajan, Viswanath
我们考虑了目标为-范数的分数阶在线覆盖问题及其对偶装箱问题。感兴趣的问题的形式是加权和的-范数和A是一个非负矩阵。A的行（即覆盖约束）随着时间的推移而在线。我们提供了一个在线竞争算法，其中和是A和的行稀疏性的最大值。这是基于在线原始对偶框架，我们使用上述凸规划的对偶。我们的结果是近紧（即使在线性特殊情况下），它扩大了类凸规划，承认在线算法。我们还提供了两个应用程序，这种凸程序出现的离散优化问题的松弛，我们的结果导致良好的在线算法。特别是，我们得到了一个改进的在线算法（由两个对数因子）的非均匀批量购买网络设计和多对数竞争比下的正常容量的吞吐量最大化。
We consider fractional online covering problems with-norm objectives as well as its dual packing problems. The problem of interest is of the formwhereis the weighted sum of-norms andAis a non-negative matrix. The rows ofA(i.e. covering constraints) arrive online over time. We provide an online-competitive algorithm whereanddis the maximum of the row sparsity ofAand. This is based on the online primal-dual framework where we use the dual of the above convex program. Our result is nearly tight (even in the linear special case), and it expands the class of convex programs that admit online algorithms. We also provide two applications where such convex programs arise as relaxations of discrete optimization problems, for which our result leads to good online algorithms. In particular, we obtain an improved online algorithm (by two logarithmic factors) for non-uniform buy-at-bulk network design and a poly-logarithmic competitive ratio for throughput maximization under-norm capacities.