Approximation Techniques (Claire
Kenyon)
Résumé :
L'approximation est une approche
naturelle pour traiter les problèmes d'optimisation qui sont NP-difficiles
ou non connus comme faisant partie des problèmes polynomiaux. Nous
nous intéressons à des algorithmes possédant dans
le pire des cas une garantie, à la fois en termes de temps d'exécution
et en termes d'erreur relative de l'approximation.
Dans ce cours nous mettrons l'accent
sur les algorithmes d'approximation basées sur la technique de l'arrondi
et nous présenterons plusieurs paradigmes par des exemples:
-
Approximation à base d'arrondi
et de recherche exhaustive.
Exemple : Grappes en deux dimensions
dans la métrique Euclidienne (travaux
de Indyk, de la Vega et Kenyon).
-
Approximation à base d'arrondi
de programmation dynamique.
Exemple : Somme de sous-parties
(travaux de Ibarra et Kim).
-
Approximation à base d'arrondi
et de programmation linéaire.
Exemple : Bin-packing (travaux
de de la Vega et Lueker).
-
Approximation à base de relaxation
Lagrangienne.
Exemple : Diffusion de données
(travaux
de Kenyon et Schabanel).
-
Approximation à base de relaxation
``ad hoc''.
Exemple : Codes de Huffman avec
longueurs de lettres inégales (travaux de Golin, Kenyon et Young).
Abstract:
Approximation is a natural approach
to deal with optimization problems which are NP-hard or not known to be
in P. We are interested in algorithms with a worst case guarantee, both
in terms of running time and in terms of the relative error of the approximation.
In this lecture I will focus on
approximation techniques based on rounding, and present several paradigms
via examples.
-
Approximation using rounding and exhaustive
search.
Example: Clustering in two dimensions
with the Euclidian metric. (work
by Indyk, de la Vega, and Kenyon)
-
Approximation using rounding and dynamic
programming.
Example: Subset-sum. (work by Ibarra
and Kim)
-
Approximation using rounding and linear
programming.
Example: Bin-packing. (work by
de la Vega and Lueker)
-
Approximation using Lagrangian relaxation.
Example: Data broadcasting. (work
by Kenyon and Schabanel)
-
Approximation using ad hoc relaxation.
Example: Huffman codes with unequal
letter lengths. (work by Golin, Kenyon and Young).
Related papers: