|Abstract as per original application
This project will investigate online matching problems in various settings. The underlying graph is bipartite, with the offline nodes constituting one side. In each step, an online node arrives and the weights of its incident edges connecting to the offline nodes are revealed. The algorithm then immediately decides whether any of the newly arriving edges are included in the matching, subject to certain constraints at the online node and offline nodes. The goal is to maximize the total weight of the edges in the matching, in which the performance ratio compares its weight with that of the offline optimal matching. The problem has wide applications in areas such as online advertising, resource allocation and logistics. For instance, in online advertising, an online node corresponds to a homepage request, for which a number of advertisements will be shown. In addition to budget constraints, the system should ensure that no competing advertisements are displayed together on the requested homepage.
When the online nodes arrive in random order with only one offline node, the problem becomes the classical secretary problem. In preliminary work, we use a primal-dual continuous linear program (LP) framework to derive an asymptotically optimal algorithm for a generalized secretary problem in which the offline node can have capacity greater than one. In an upcoming SODA 2015 paper, we extend this algorithm to the online matching problem in which the offline nodes can have non-uniform capacities. Together with the continuous LP techniques developed in our previous SODA 2014 paper, we have a collection of powerful techniques for tackling new variants of the online matching problem:
(1) General node constraints. For instance, the chosen edges incident to a node form an independent set in some underlying matroid, which forbids certain edges from being selected together, as in the foregoing online advertising example.
(2) Arbitrary arrival order with free disposal. In the literature, this scenario means that the arrival order can be chosen adversarially, and that the constraints at the offline nodes are enforced at the end by disposing of certain edges.
(3) Algorithms considering only relative merits. In privacy-sensitive applications, the algorithm cannot observe the actual edge weights, but only their relative merits.
This project will unify and make important technical contributions to a number of research areas such as online matching, secretary problems and matroid theory. Moreover, our results will have significant impacts on the related practical applications.
本項目將探討多種設定下的在線匹配問題。基礎圖為二分圖，其中一邊由離線節點組成。在每一步，一個在線節點到達並顯示其與離線節點之間邊上的權值。在滿足基於在線節點和離線節點的特定約束的情況下，算法將立即決定是否將某些新到達的邊納入匹配中。目標是最大化該匹配中的邊權值之和，且這種情況下的性能比將對該匹配的權值和離線最優匹配的權值進行比較。該問題在在線廣告、資源分配和物流等領域具有廣泛應用。例如，於在線廣告中，一個在線節點對應一個網頁請求，針對該請求的一些廣告將會顯示。除預算約束外，系統應確保相互競爭的廣告不同時出現在請求的網頁中。當在線節點以隨機順序到達且只有一個離線節點時，該問題即為經典秘書問題。在初步工作中，我們用一個原對偶連續線性規劃框架導出了一個針對廣泛秘書問題的漸進最優算法；在該問題中離線節點可具有大於一的容量。在一篇SODA 2015論文中，我們將該算法擴展到離線節點可具有非均勻容量的在線匹配問題上。加上我們SODA 2014論文所開發的連續線性規劃技術，我們有強大的技術庫來應對在線匹配問題的新變種：（1）廣泛節點約束。例如，連接同一個節點的所選中的邊應形成某個擬陣中的獨立集；如在線廣告例子中所述，該約束禁止某些邊被同時選中。（2）任意到達順序並可自由處置。在文獻中，該情境意味着到達順序可被對抗性地決定，並且最終算法將處置某些邊以確保服從離線節點的約束。（3）只考慮相對價值的算法。在對隱私敏感的應用中，算法不能觀測真實的邊權值，而只能獲得它們的相對價值。本項目將針對在線匹配、秘書問題和擬陣理論等諸多研究領域進行整合並作出重要的技術貢獻。此外，我們的結果將對相關的實際應用產生重大影響。