|
|
ENQUIRE PROJECT DETAILS BY GENERAL PUBLIC |
| Project Details |
| Funding Scheme : | General Research Fund | |||||||||||||||||||||
| Project Number : | 17202715 | |||||||||||||||||||||
| Project Title(English) : | Primal-Dual Mathematical Programming Methods for Online Matching Problems with Generalized Constraints | |||||||||||||||||||||
| Project Title(Chinese) : | 針對廣泛約束下在線匹配問題的原對偶數學規劃方法 | |||||||||||||||||||||
| Principal Investigator(English) : | Dr Chan, Hubert Tsz Hong | |||||||||||||||||||||
| Principal Investigator(Chinese) : | ||||||||||||||||||||||
| Department : | School of Computing and Data Science | |||||||||||||||||||||
| Institution : | The University of Hong Kong | |||||||||||||||||||||
| E-mail Address : | hubert@cs.hku.hk | |||||||||||||||||||||
| Tel : | 28578461 | |||||||||||||||||||||
| Co - Investigator(s) : |
|
|||||||||||||||||||||
| Panel : | Engineering | |||||||||||||||||||||
| Subject Area : | Computing Science & Information Technology | |||||||||||||||||||||
| Exercise Year : | 2015 / 16 | |||||||||||||||||||||
| Fund Approved : | 496,028 | |||||||||||||||||||||
| Project Status : | Completed | |||||||||||||||||||||
| Completion Date : | 14-6-2019 | |||||||||||||||||||||
| Project Objectives : |
|
|||||||||||||||||||||
| Abstract as per original application (English/Chinese): |
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）只考慮相對價值的算法。在對隱私敏感的應用中，算法不能觀測真實的邊權值，而只能獲得它們的相對價值。本項目將針對在線匹配、秘書問題和擬陣理論等諸多研究領域進行整合並作出重要的技術貢獻。此外，我們的結果將對相關的實際應用產生重大影響。 |
|||||||||||||||||||||
| Realisation of objectives: | Objective 1 As a first step to employ mathematical programming in the project, we have considered a max-min allocation problem in which items are assigned to users such that the minimum utility of a user is maximized. Even the special case in which the utility of an item for a user is either 1 or some small epsilon is interesting, as we have shown that it is NP-hard to obtain an approximation ratio better than 2. Using a configuration linear program (CLP), we have expressed the bound on the minimum user utility as constraints on all the user nodes. As opposed to existing approaches, our algorithms and analysis do not directly use the feasibility of CLP. Instead we use integrality gap analysis and local search technique to show that our algorithms terminate with the claimed approximation ratios if the CLP is feasible. We have designed approximation algorithms based on the approach of hypergraph matching augmentation. In quasi-polynomial-time, our approach can achieve approximation ratio arbitrarily close to 3, and in polynomial-time, our approach gives 9-approximation. The results have appeared in ISAAC 2016 and Algorithmica 2018. Next, to develop a theoretical foundation for online optimization with matroid constraint, we have studied the problem of online submodular maximization under the special case of uniform matroid. The best previous performance ratio is 0.25 for general matroids by Chakrabarti and Kale (IPCO 2014), Buchbinder et al. (SODA 2015), and Chekuri et al. (ICALP 2015). The uniform matroid is the special case in which a solution is feasible if its size is at most some pre-determined budget k. We have designed a deterministic algorithm with competitive ratio at least 0.2959, and the ratio approaches 0.3178 as the budget k approaches infinity. We have also shown that our algorithm is optimal among a class of deterministic monotone algorithms that accept a new arriving element only if the objective is strictly increased. Further, we prove that no deterministic monotone algorithm can be strictly better than 0.25-competitive even for partition matroids. Interestingly, we show that randomized algorithms are strictly more powerful by giving a (non-monotone) randomized algorithm for partition matroids with ratio 0.3178. The results have appeared in SODA 2017/TALG 2018. The above results have inspired us to consider other budgeted optimization problems. For instance, given a graph, the goal is to find which k edges would have the largest impact on maximum flow queries on a network. This problem has important applications in areas like social network and network planning. We have shown the inapproximability of the problems and presented several heuristic algorithms. The results have appeared in Information Systems 2017. Objective 2 Using techniques in convex program, we have considered online optimization problems with covering or packing constraints with arbitrary arrival order. For instance, the capacity of a node can be expressed as a packing constraint. In the online covering problem, the variables are offline, and each constraint arrives at every time step. In the online packing problem, the number of constraints is fixed, and each variable arrives at every time step. By analyzing the Frenchel dual of the objective function, we have developed a primal-dual approach to give online algorithms for these generic problems. As our framework is very general, we can use it to simplify, unify, and improve upon previous results for several applications such as mixed covering and packing LPs, social welfare maximization with production costs, unrelated machine scheduling with startup costs, capacity constrained facility location, capacitated multicast problem, online set cover with set requests, etc. Our main idea is to increase the values of the primal variables exponentially proportional both to their current value and their coefficient in the constraint, but divided by the gradient of the objective function at the current solution. The dual is increased at a carefully chosen linear rate. Moreover, we use “shadow duals” to bound the primal cost more tightly. These dual variables are non-monotone and may be decreased at certain times. However, doing this carefully and maintaining such “non-monotone” duals is crucial in obtaining a sharp competitive ratio. The results have appeared in FOCS 2016. To illustrate the difference between arbitrary arrival order and random arrival order, we have studied the online problem with vector knapsack constraint, in which each item has a weight and a node has a capacity vector such that the items collected have to satisfy the capacity constraint in every dimension. The results are typically parameterized by the sparsity k, which is an upper bound on the number of non-zero coordinates of each weight vector. We have developed an O(k)-competitive algorithm for the slacked variant in which no single item can totally saturate any dimension. Even though our algorithm is deterministic, the techniques are inspired by randomized rounding. Specifically, our algorithm maintains a fractional solution, which is rounded at every step to achieve an integer solution. Even when each coordinate of the weight vector is arbitrarily small, we have shown that there is no algorithm with competitive ratio o(log k/ log log k). This is in contrast with the random arrival order scenario, in which competitive ratio close to 1 is possible. Our results have appeared in ESA 2017. Objective 3 We have also investigated the scenario in which the weight of an edge represents a user’s evaluation on a certain item, which can be considered private information. Hence, the goal is to develop a truthful allocation mechanism such that a user has no incentive to lie about his information. We have applied mechanism design techniques on a double auction problem between buyer and seller nodes. Using the technique of reserve price, we design a mechanism such that the subset of users that actually participate in the final allocation depends on the relative merits of their evaluations. Moreover, the party running the double auction aims to maximize the total weight of matched edges which represents the social welfare. Together with the Co-I, we have evaluated our mechanisms using real-world data and compare the experimental results with the theoretical analysis. The results have appeared in CLOSER 2017. Finally, as we have observed that the aforementioned mechanism depends on the relative merits of users’ private evaluations, comparison-based oblivious sorting is an important subroutine to filter out some buyers or sellers. As these applications involve a huge number of users, these mechanisms are often run in the cloud, and hence, the I/O costs under the external-memory paradigm will have an impact on the practical performance. We have made a significant step forward in understanding external-memory oblivious sorting algorithms. Specifically, we have constructed such an algorithm that is optimal in I/O-cost; moreover, our algorithm is also cache-agnostic in the sense that the algorithm does not need to know the storage hierarchy's internal parameters such as the cache and cache-line sizes. Our results have appeared in SODA 2018. | |||||||||||||||||||||
| Summary of objectives addressed: |
|
|||||||||||||||||||||
| Research Outcome | ||||||||||||||||||||||
| Major findings and research outcome: | We have investigated various mathematical programs to tackle different optimization problems. As a starting point, we have used a configuration linear program to design and analyze algorithms for a max-min allocation problem in which the utility of an item for a user is either 1 or some small epsilon. Our constant approximation algorithms have appeared in ISAAC 2016/Algorithmica 2018. We have studied the problem of online submodular maximization under the special case of uniform matroid. While the best previous performance ratio is 0.25 for general matroids, we have improved the ratio to 0.2959, and the ratio approaches 0.3178 as the rank of the uniform matroid approaches infinity, where the ratio is optimal for a class of deterministic monotone algorithms. The results have appeared in SODA 2017/TALG 2018. Using techniques in convex program, we have considered online optimization problems with covering or packing constraints with arbitrary arrival order. By analyzing the Frenchel dual of the objective function, we have designed primal-dual online algorithms for these generic problems. Our framework is very general, and we have used it to simplify, unify, and improve upon previous results for several applications. The results have appeared in FOCS 2016. To illustrate the difference between arbitrary arrival order and random arrival order, we have studied the online problem with vector knapsack constraint, in which each item has a weight vector with sparsity at most k. We have developed an O(k)-competitive algorithm for the slacked variant in which no single item can totally saturate any dimension. We have proved that when each coordinate of the weight vector is arbitrarily small, there is no algorithm with competitive ratio o(log k/ log log k). This is in contrast with the random arrival order scenario, in which competitive ratio close to 1 is possible. Our results have appeared in ESA 2017. We have also investigated the scenario in which the weight of an edge represents a user’s evaluation on a certain item, which can be considered private information. We have developed a truthful allocation mechanism such that a user has no incentive to lie about his information via a double auction problem between buyer and seller nodes. The results have appeared in CLOSER 2017. Inspired by the aforementioned mechanism, we have constructed a comparison-based oblivious and cache-agnostic sorting algorithm that has optimal I/O cost in the external memory model. The results have appeared in SODA 2018. | |||||||||||||||||||||
| Potential for further development of the research and the proposed course of action: |
We have developed online allocation algorithms under various settings. A common theme in the design of these algorithms is that only partial information is known at the moment an algorithm needs to make a decision. Towards the end of the project, we have seen that this algorithm design paradigm can lead to privacy preserving mechanisms, which can make decisions without complete knowledge of sensitive user data. In addition to performance ratio, future work should investigate other practical aspects such as I/O efficiency in real-world applications such has cloud platforms. While the decisions of the online algorithms in this project are made centrally, in modern peer-to-peer networks, it is also relevant to consider these problems in a distributed setting. Besides protecting its own privacy, each node might also behave arbitrarily. Hence, an interesting direction is to consider game theoretic and security notions in online allocation problems in a Byzantine environment. In addition to maintaining utility and security, desirable protocols should have good practical performance such as low round and communication complexity. | |||||||||||||||||||||
| Layman's Summary of Completion Report: | The results of this project have applications in online advertising, resource allocation and logistics. We have developed online primal-dual algorithms that make irrevocable decisions based on incomplete information and maintain feasible solutions. For instance, using the theory of matroids, we can capture the constraint that no competing advertisements are displayed together on a requested homepage. Although random arrival order provides mathematical beauty in some analysis, we have designed algorithms for the online submodular maximization problem (for instance, with vector packing constraint) for the more practical scenario in which online requests may arrive in some adversarial order. We have achieved a better theoretical understanding by showing that performance ratios achieved under random arrival order may be impossible under adversarial arrival order. In privacy-sensitive applications such as resource allocation in cloud computing, we have designed mechanisms that do not make decisions based on users’ actual evaluations, but only their relative merits. This has inspired us to develop oblivious algorithms for the sorting abstraction that has optimal I/O-efficiency in the external memory model. The techniques developed in this project will foster further research in online distributed mechanisms that can achieve both utility and security. | |||||||||||||||||||||
| Research Output | ||||||||||||||||||||||
| Peer-reviewed journal publication(s) arising directly from this research project : (* denotes the corresponding author) |
|
|||||||||||||||||||||
| Recognized international conference(s) in which paper(s) related to this research project was/were delivered : |
|
|||||||||||||||||||||
| Other impact (e.g. award of patents or prizes, collaboration with other research institutions, technology transfer, etc.): |
||||||||||||||||||||||
| SCREEN ID: SCRRM00542 |