New Frontiers of the Online Primal Dual Technique: Convex Programs and Limitations of the Canonical Approach


Grant Data
Project Title
New Frontiers of the Online Primal Dual Technique: Convex Programs and Limitations of the Canonical Approach
Principal Investigator
Dr Huang, Zhiyi   (Principal investigator)
Duration
36
Start Date
2016-01-01
Completion Date
2018-12-31
Amount
496028
Conference Title
Presentation Title
Keywords
Online algorithm, Primal dual, Combinatorial optimization, Convex program
Discipline
Computer Science Fundamentals
Panel
Engineering (E)
Sponsor
RGC General Research Fund (GRF)
HKU Project Code
17202115
Grant Type
General Research Fund (GRF)
Funding Year
2015/2016
Status
On-going
Objectives
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.