We propose a model for online graph problems where algorithms are given access to an oracle that predicts the degrees of nodes in the graph (e.g., based on past data). Within this model, we study the classic problem of online bipartite matching. An extensive empirical evaluation shows that a greedy algorithm called MinPredictedDegree compares favorably to state-of-the-art online algorithms for this problem. We also initiate the theoretical study of MinPredictedDegree on a natural random graph model with power law degree distribution and show that it produces matchings almost as large as the maximum matching on such graphs.
翻译：我们提出了一个在线图表问题模型,让算法能够访问一个神器,预测图中节点的程度(例如,基于过去的数据 ) 。 在这个模型中,我们研究了在线双边匹配的典型问题。 广泛的实证评估表明,贪婪算法名为MinPredistedDegree, 与这一问题的最新在线算法相比,更有利。 我们还启动了对 MinPredistedDegree 的理论研究,研究的是一个自然随机图形模型,该模型有权力法度分布,并显示它产生的匹配量几乎与这些图表上的最大匹配量一样大。
相关内容
- 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会员