Simultaneous approximations for adversarial and stochastic online budgeted allocation
Simultaneous approximations for adversarial and stochastic online budgeted allocation
复制标题
对抗性和随机在线预算分配的同时近似
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Morteza Zadimoghaddam
中科院分区：
文献类型：
--
作者：
V. Mirrokni;S. Gharan;Morteza Zadimoghaddam
受在线广告分配的启发，我们研究了对抗性和随机性在线预算分配问题的同时逼近问题。该问题由一个二分图G =（X，Y，E）组成，其中Y沿着的节点及其相应的容量对于算法来说是预先已知的，而X的节点到达在线。当X的一个节点到达时，它的关联边和它们各自的权重就会显示出来，算法可以将它与Y中的一个邻居进行匹配。我们的目标是最大限度地提高最终匹配的重量，同时尊重的能力。
当节点以对抗顺序到达时，最佳竞争比已知为1 - 1/e，并且可以通过Ranking [18]及其推广（Balance [16，21]）来实现。另一方面，如果节点通过随机排列到达，则可以实现1-e的竞争比[9]。在本文中，我们设计的算法，实现竞争比优于1 - 1/E平均，同时保持一个接近最佳的最坏情况下的竞争比。理想情况下，我们希望实现两全其美，即设计一个算法，在对抗和随机到达模型中具有最佳竞争比。我们实现了这一点的非加权图，但表明，这是不可能的加权图。
特别是，对于未加权图，在一些温和的假设下，我们证明了平衡实现的竞争比1-e在一个随机置换模型。对于加权图，但是，我们证明这是不可能的，我们证明，没有在线算法，实现近似因子为1 - 1/E的最坏情况下的输入可能会实现平均近似因子优于97.6%的随机输入。鉴于这一困难的结果，我们的目标是设计算法的随机到达模型中的近似比，同时保持竞争比1 - 1/e在最坏的情况下。为此，我们证明了[21]提出的算法对于随机到达模型实现了0.76的竞争比，而在最坏情况下具有1 - 1/e比。
Motivated by online ad allocation, we study the problem of simultaneous approximations for the adversarial and stochastic online budgeted allocation problem. This problem consists of a bipartite graph G = (X, Y, E), where the nodes of Y along with their corresponding capacities are known beforehand to the algorithm, and the nodes of X arrive online. When a node of X arrives, its incident edges, and their respective weights are revealed, and the algorithm can match it to a neighbor in Y. The objective is to maximize the weight of the final matching, while respecting the capacities.
When nodes arrive in an adversarial order, the best competitive ratio is known to be 1 - 1/e, and it can be achieved by the Ranking [18], and its generalizations (Balance [16, 21]). On the other hand, if the nodes arrive through a random permutation, it is possible to achieve a competitive ratio of 1 -- e [9]. In this paper we design algorithms that achieve a competitive ratio better than 1 -- 1/e on average, while preserving a nearly optimal worst case competitive ratio. Ideally, we want to achieve the best of both worlds, i.e, to design an algorithm with the optimal competitive ratio in both the adversarial and random arrival models. We achieve this for unweighted graphs, but show that it is not possible for weighted graphs.
In particular, for unweighted graphs, under some mild assumptions, we show that Balance achieves a competitive ratio of 1 -- e in a random permutation model. For weighted graphs, however, we prove this is not possible; we prove that no online algorithm that achieves an approximation factor of 1 -- 1/e for the worst-case inputs may achieve an average approximation factor better than 97.6% for random inputs. In light of this hardness result, we aim to design algorithms with improved approximation ratios in the random arrival model while preserving the competitive ratio of 1 -- 1/e in the worst case. To this end, we show the algorithm proposed by [21] achieves a competitive ratio of 0.76 for the random arrival model, while having a 1 -- 1/e ratio in the worst case.