Online Algorithms for Covering and Packing Problems with Convex Objectives-猫眼课题宝

用于凸目标覆盖和打包问题的在线算法

DOI：

发表时间：

2016

期刊：

IEEE Annual Symposium on Foundations of Computer Science

影响因子：

通讯作者：

中科院分区：

文献类型：

作者：

Y. Azar;Niv Buchbinder;T;Shahar Chen;I. Cohen;Anupam Gupta;Zhiyi Huang;N. Kang;V. Nagarajan;J. Naor;Debmalya Panigrahi

我们提出了用于覆盖和打包（非线性）凸目标问题的在线算法。凸覆盖问题定义为：minxϵR+nf(x) s.t。 Ax ≥ 1，其中 f:R+n → R+ 是单调凸函数，A 是具有非负项的 m×n 矩阵。在在线版本中，每一步都会显示约束矩阵的新行，代表新的覆盖约束，并且要求算法随时间保持可行且单调非递减的分配 x 。我们还考虑凸堆积问题，定义为： maxyϵR+m Σj=1m yj - g(AT y)，其中 g:R+n→R+ 是单调凸功能。在在线版本中，每个变量 yj 在线到达，算法必须在其到达时决定 yj 的值。当 g 是 f 的凸共轭时，这表示凸覆盖程序的 Fenchel 对偶。我们使用原对偶方法为这些通用问题提供在线算法，并使用它们来简化、统一和改进多个应用程序的先前结果。

We present online algorithms for covering and packing problems with (non-linear) convex objectives. The convex covering problem is defined as: minxϵR+nf(x) s.t. Ax ≥ 1, where f:R+n → R+ is a monotone convex function, and A is an m×n matrix with non-negative entries. In the online version, a new row of the constraint matrix, representing a new covering constraint, is revealed in each step and the algorithm is required to maintain a feasible and monotonically non-decreasing assignment x over time. We also consider a convex packing problem defined as: maxyϵR+m Σj=1m yj - g(AT y), where g:R+n→R+ is a monotone convex function. In the online version, each variable yj arrives online and the algorithm must decide the value of yj on its arrival. This represents the Fenchel dual of the convex covering program, when g is the convex conjugate of f. We use a primal-dual approach to give online algorithms for these generic problems, and use them to simplify, unify, and improve upon previous results for several applications.

Online Algorithms for Covering and Packing Problems with Convex Objectives

用于凸目标覆盖和打包问题的在线算法

文献摘要

被引文献

相似文献