Delineating the tremendous growth in this area, the Handbook of Approximation Algorithms
and Metaheuristics covers fundamental, theoretical topics as well as advanced, practical …

The primal–dual method is a powerful algorithmic technique that has proved to be extremely
useful for a wide variety of problems in the area of approximation algorithms for NP-hard …

We study a wide range of online covering and packing optimization problems. In an online
covering problem, a linear cost function is known in advance, but the linear constraints that …

Stochastic optimization problems attempt to model uncertainty in the data by assuming that
the input is specified by a probability distribution. We consider the well-studied paradigm of …

Stochastic optimization problems attempt to model uncertainty in the data by assuming that
(part of) the input is specified in terms of a probability distribution. We consider the well …

We study a wide range of online covering and packing optimization problems. In an online
covering problem a linear cost function is known in advance, but the linear constraints that …

We consider the classical vertex cover and set cover problems with hard capacity
constraints. This means that a set (vertex) can cover only a limited number of its elements …

Given matrices A and B and vectors a, b, c and d, all with non-negative entries, we consider
the problem of computing min {cTx: x∈ Z+ n, Ax⩾ a, Bx⩽ b, x⩽ d}. We give a bicriteria …

We introduce a class of “stochastic covering” problems where the target set X to be covered
is fixed, while the “items” used in the covering are characterized by probability distributions …

Given a collection S of sets over a universe U, a set cover C⊆ S is a subcollection of the sets
whose union is U. The set-cover problem is, given S, to find a minimum-cardinality set cover …