The general adwords problem has remained largely unresolved. We define a subcase called {\em $k$-TYPICAL}, $k \in \Zplus$, as follows: the total budget of all the bidders is sufficient to buy $k$ bids for each bidder. This seems a reasonable assumption for a ``typical'' instance, at least for moderate values of $k$. We give a randomized online algorithm achieving a competitive ratio of $\left(1 - {1 \over e} - {1 \over k} \right) $ for this problem. We also give randomized online algorithms for other special cases of adwords. The key to these results is a simplification of the proof for RANKING, the optimal algorithm for online bipartite matching, given in \cite{KVV}. Our algorithms for adwords can be seen as natural extensions of RANKING.
翻译：一般广告问题基本上仍未解决。 我们定义了一个名为 $ $k$- TyPicrial}, $k $ k $ +$ 的子案例, 如下: 所有投标人的总预算足以为每个投标人购买 $k$ 的标书。 这似乎是“ 典型” 实例的合理假设, 至少对中值为$k$。 我们给出了一个随机化的在线算法, 其竞争性比率为$left( 1 - {1\ over e} - {1\ over k}\ right) 。 我们还为其他特殊标书提供了随机化的在线算法。 这些结果的关键是简化 RANKING 的证明, 即在线双边匹配的最佳算法, 在\ cite{ KV} 中给出。 我们的标书算法可以被视为 RANKING 的自然延伸 。
相关内容
- Today (iOS and OS X): widgets for the Today view of Notification Center
- Share (iOS and OS X): post content to web services or share content with others
- Actions (iOS and OS X): app extensions to view or manipulate inside another app
- Photo Editing (iOS): edit a photo or video in Apple's Photos app with extensions from a third-party apps
- Finder Sync (OS X): remote file storage in the Finder with support for Finder content annotation
- Storage Provider (iOS): an interface between files inside an app and other apps on a user's device
- Custom Keyboard (iOS): system-wide alternative keyboards
Source: iOS 8 Extensions: Apple’s Plan for a Powerful App Ecosystem
微信扫码咨询专知VIP会员