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

Dr Chan, Hubert Tsz Hong   (Principal Investigator (PI))

Professor Wu Chuan   (Co-Investigator)

36

2016-06-15

496028

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

mathematical programming, matroid theory, online matching problems, primal-dual methods, secretary problem

Computer Science Fundamentals

Engineering (E)

17202715

General Research Fund (GRF)

2015

Completed

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.