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

Dr Huang, Zhiyi   (Principal Investigator (PI))

36

2016-01-01

496028

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

Combinatorial optimization, Convex program, Online algorithm, Primal dual

Computer Science Fundamentals

Engineering (E)

17202115

General Research Fund (GRF)

2015

Completed

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.