Online Algorithms for Covering and Packing Problems with Convex Objectives

on YouTube ↗34m

" summary

Generalizes online primal–dual to convex objectives and proves a concrete competitive bound: for monotone convex f with monotone gradient and polynomial-like curvature parameter p, an online algorithm using Fenchel dual and a multiplicative update rule attains roughly (p log D)^p competitive ratio (D = row sparsity) and matches lower bounds for degree-p polynomials. Builds monotone primal and dual solutions, introduces a “shadow” dual that is briefly decreased to remove an a_max/a_min gap, and gives rounding for Lp-norm set cover with explicit extra factors.

AI-written summary · about

" chapters (8)

1. 0:00Introduction to the topic
2. 1:18Primal-dual framework basics
3. 7:49Generalizing the framework
4. 10:34Fenchel duality
5. 13:21Main results and theory
6. 17:32Related work and motivation
7. 21:12The proposed algorithm
8. 27:58Advanced techniques and wrap up