Primal-Dual Mathematical Programming Methods for Online Matching Problems with Generalized Constraints


Grant Data
Project Title
Primal-Dual Mathematical Programming Methods for Online Matching Problems with Generalized Constraints
Principal Investigator
Dr Chan, Hubert Tsz Hong   (Principal investigator)
Co-Investigator(s)
Dr Wu Chuan   (Co-Investigator)
Duration
36
Start Date
2016-06-15
Completion Date
2019-06-14
Amount
496028
Conference Title
Presentation Title
Keywords
online matching problems, secretary problem, mathematical programming, primal-dual methods, matroid theory
Discipline
Computer Science Fundamentals
Panel
Engineering (E)
Sponsor
RGC General Research Fund (GRF)
HKU Project Code
17202715
Grant Type
General Research Fund (GRF)
Funding Year
2015/2016
Status
On-going
Objectives
1) To design and analyze algorithms for the problem with general constraints at the offline and online nodes via mathematical programming methods. For instance, the chosen edges incident to a node should respect the node capacity or form an independent set in some underlying matroid; 2) To design and analyze algorithms for the problem with arbitrary arrival order and also random arrival order. For arbitrary arrival order, free disposal is performed at the end to enforce the node constraints. Even for unit capacity, achieving a ratio better than 0.5 would be non-trivial; 3) To design and analyze algorithms that can observe only the relative merits of edge weights. For example, we will consider privacy-sensitive applications, in which users may want to keep their actual weights secret, revealing only the relative merits of those weights.