# Online Primal-Dual Algorithms with Configuration Linear Programs

arXiv: https://arxiv.org/abs/1708.04903 · HTML: https://mlsanity.com/paper/1708.04903/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Aug 2017.

## Built on by (most cited first, 1 of 1)

- [Online Primal-Dual Algorithms with Predictions for Packing Problems](https://mlsanity.com/paper/2110.00391/) (2021)

## Abstract (arXiv)

Non-linear, especially convex, objective functions have been extensively studied in recent years in which approaches relies crucially on the convexity property of cost functions. In this paper, we present primal-dual approaches based on configuration linear programs to design competitive online algorithms for problems with arbitrarily-grown objective. This approach is particularly appropriate for non-linear (non-convex) objectives in online setting. We first present a simple greedy algorithm for a general cost-minimization problem. The competitive ratio of the algorithm is characterized by the mean of a notion, called smoothness, which is inspired by a similar concept in the context of algorithmic game theory. The algorithm gives optimal (up to a constant factor) competitive ratios while applying to different contexts such as network routing, vector scheduling, energy-efficient scheduling and non-convex facility location. Next, we consider the online 0-1 covering problems with non-convex objective. Building upon the resilient ideas from the primal-dual framework with configuration LPs, we derive a competitive algorithm for these problems. Our result generalizes the online primal-dual algorithm developed recently by Azar et al. for convex objectives with monotone gradients to non-convex objectives. The competitive ratio is now characterized by a new concept, called local smoothness --- a notion inspired by the smoothness. Our algorithm yields tight competitive ratio for the objectives such as the sum of ℓk-norms and gives competitive solutions for online problems of submodular minimization and some natural non-convex minimization under covering constraints.