New Frontiers of the Online Primal Dual Technique: Convex Programs and Limitations of the Canonical Approach
Dr Huang, Zhiyi (Principal investigator)
Online algorithm, Primal dual, Combinatorial optimization, Convex program
Computer Science Fundamentals
RGC General Research Fund (GRF)
HKU Project Code
General Research Fund (GRF)
1) Online Primal Dual with Convex Programs - Case Studies: We will use online primal dual and convex programs to design and analyze online algorithms for three representative cases -- online scheduling on speed-scalable machines, online combinatorial auctions with production costs, and online facility location with scalable capacities. We will complement the algorithmic results with lower bounds on the competitive ratios of these problems to justify the optimality of our algorithms; 2) Online Primal Dual with Convex Programs - General Framework: We will develop a recipe for using online primal dual to solve a large family of convex programs online, including convex extensions of packing and covering linear programs, and convex programs with mixed packing and covering constraints; 3) Limitations of the Canonical Approach: We will explain why online primal dual failed on some problems using a novel theory of canonical online primal dual and online duality gap that we developed in our preliminary studies. We will further develop the theory of online duality gap and study how it depends on the competitive ratios of the primal and dual problems; 4) Beyond the Canonical Approach: We will explore potential approaches beyond the canonical one to circumvent the online duality gap, and use such approaches to design better algorithms for problems on which the canonical approach failed.