Seminar Details

Factor-revealing and policy-revealing linear programs (LPs) are widely used to analyze approximation and online algorithms when direct performance evaluation is difficult. These LPs characterize worst-case performance as a family of programs parameterized by instance size n, and the key challenge is to determine their optimal objective values and solutions as the size n approaches infinity. Existing approaches—such as the primal–dual method and strongly factor-revealing LPs—rely on instance-specific constructions, making them hard to generalize. This talk introduces a variational-calculus framework that reformulates the limiting behavior of these LP families as a continuous variational problem, allowing the use of analytical tools such as the Euler–Lagrange equation and Lagrange multipliers. I will illustrate the framework through three online optimization case studies and discuss how it yields unified and broadly applicable insights into algorithm design and analysis.