Introduction

In this chapter, we describe a generic primal–dual technique to bound the competitive ratio for a variety of online problems, whose relaxations can be posed as linear programs (LPs). The basic idea of this approach is to interpret the relaxation of the problem that we are interested in solving as the primal program (let it be a minimization problem). Then considering the primal and its dual together, an algorithm is proposed that updates both the primal and the dual solutions on each new request of the input sequence, such that the increment in the primal cost is upper bounded by c (for some c > 1) times the increment in the dual cost. Combining this with the weak duality of LPs, that means that the primal cost is lower bounded by the optimal value of the dual, it follows that the competitive ratio of the proposed algorithm is at most c.

We first describe this recipe in detail, and then discuss three versatile problems that are well suited for this primal–dual schema's application.

The first problem we consider is the set cover problem, where we are given a universe of elements and a collection of subsets of the universe, with each subset having an associated cost. The elements of the universe arrive online, and on each new element's arrival, if that element is not part of the current cover (collection of subsets), then at least one subset that contains that element has to be included in the cover. The objective is to choose that set of subsets that minimizes the sum of the cost of the cover at the end of all element arrivals in the input.

The set cover problem is a special case of what is known as covering problems, where the objective is to minimize the cost of selected resources under some generic coverage constraints. The dual of the covering problem is a packing problem, such as the knapsack problem (Chapter 8), where the objective is to maximize the profit of included items subject to some capacity constraints on the total size of the included items.

The next problem we consider is a packing problem, called the AdWords, that is highly relevant for online web portals like Google, Facebook, etc., where items (ad slots) arrive online and their valuation from multiple interested buyers (advertisers) are revealed.