No label defined (Q4938889)

It is well known that several basic problems of discrete optimization are computationally intractable (NP-hard or worse). However, such problems do need to be solved, and a very useful practical approach is to design a heuristic Tailor-made for a particular application. Another approach is to develop and implement approximation algorithms for the given problem, which come with proven guarantees. Study of the approximability of various classes of hard (combinatorial) optimization problems has greatly bloomed in the last two decades. In this survey, we study one important tool in this area, that of randomized rounding. We have not attempted to be encyclopaedic here, and sometimes do not present the best-known results; our goal is to present some of the underlying principles of randomized rounding without necessarily going into full detail. For our purposes here, we shall consider an algorithm to be efficient if it runs in polynomial time (time that is bounded by a fixed polynomial of the length of the input). We will not explicitly present the running times of our algorithms; it will mostly be clear from the context that they are polynomial-time. However, we remark that most of our algorithms are indeed reasonable efficient; for instance, most of them involve network flows and other special cases of linear programming, for which efficient algorithms and codes are available. Our focus throughout will be on the quality of approximation guaranteed by our approximation algorithms; we now recall the notion of an approximation algorithm. For the entire collection see [Zbl 0920.00042].