Online Primal-Dual Algorithms for Covering and Packing 2: The Phased Online Fractional Covering Scheme Covers Every Constraint to 1/B at Cost at Most 8 log(2n)/B Times the OptimumResearch Paper
Online covering models decisions that must be made as requirements arrive. A planner knows the cost of each available resource, but learns the requirements one at a time and cannot undo an allocation already made. This occurs, for example, when requests for network service or elements needing coverage appear over time. The central question is how much more…