Approximation Algorithms
Prof. Fl vio Keidi Miyazawa
A branch of Combinatorial Optimization
Optimization problems, in general, aim to maximize or minimize a defined function over a certain domain. The classic theory of optimization deals with the case where the domain is infinite. In the case of so-called combinatorial optimization problems, the domain is typically finite; moreover, in general it is easy to list its elements and also test whether a given element belongs to that domain. Even so, the naive idea of testing all the elements of this domain in the search for the best proves to be impossible in practice, even for moderately sized instances.As classic examples of problems of combinatorial optimization we can mention the problem of the traveling salesman, the problem of the backpack, the problem of minimum coverage by sets, the problem of the Steiner forest and the problem of finding one maximum independent set in a graph. In the technical sense, all are NP-difficult. These, and several others of the same nature, are, however, of great interest because they arise in practical applications in the industry, such as in the design of telecommunications networks and VLSI circuits, packaging problems, distribution center location problems, scheduling problems, vehicle routing problems, etc. Other areas of application include statistics (data analysis), economics (input / output matrices), physics (determination of minimum energy states), molecular biology (DNA alignment, inferences of standards), etc.
What is an Approximation Algorithm?
Generally speaking, Algorithms of approximation are algorithms that do not necessarily produce an optimal solution, but solutions that are within a certain factor of the optimal solution.The development of approximation algorithms arose in response to the impossibility of satisfactorily solving several NP-difficult optimization problems. We are referring here to the impossibility, under the assumption that P <> NP, to find efficient algorithms for these problems.
In this situation, it seems reasonable to sacrifice optimality in exchange for guaranteeing an approximate computable solution efficiently. Certainly, the interest is, in spite of sacrificing optimality, doing so in a way that we can still give good guarantees on the value of the solution obtained, trying to gain the maximum in terms of computational efficiency.
This compromise between loss of optimality and gain in efficiency is the paradigm of approximation algorithms.
Techniques
Some of the techniques that have been used in approximation algorithms are:Some of the techniques above are quite recent and are attracting a lot of interest from researchers, currently being the focus of intense research and studies in the field.Combinatory Methods
Fl vio Keidi Miyazawa's Homepage