En informática , la aproximación k de un conjunto de k-hitting es un algoritmo de aproximación para un conjunto de k-hitting ponderado . La entrada es una colección S de subconjuntos de algún universo T y una asignación W de T a números no negativos llamados pesos de los elementos de T. En un conjunto de k-hitting, el tamaño de los conjuntos en S no puede ser mayor que k . Es decir, . El problema ahora es elegir un subconjunto T ' de T tal que cada conjunto en S contenga algún elemento de T ', y tal que el peso total de todos los elementos en T ' sea lo más pequeño posible.
Para cada conjunto de S se mantiene un precio , , que inicialmente es 0. Para un elemento a de T , sea S ( a ) la colección de conjuntos de S que contienen a . Durante el algoritmo se mantiene el siguiente invariante
Decimos que un elemento, a , de T es ajustado si . La parte principal del algoritmo consiste en un bucle: mientras haya un conjunto en S que no contenga ningún elemento de T que sea ajustado, el precio de este conjunto se incrementa tanto como sea posible sin violar el invariante anterior. Cuando este bucle sale, todos los conjuntos contienen algún elemento ajustado. Escoja todos los elementos ajustados para que sean el conjunto ganador.
El algoritmo siempre termina porque en cada iteración del bucle el precio de algún conjunto en S se incrementa lo suficiente como para hacer que un elemento más de T sea ajustado. Si no puede aumentar ningún precio, sale. Se ejecuta en tiempo polinomial porque el bucle no realizará más iteraciones que el número de elementos en la unión de todos los conjuntos de S . Devuelve un conjunto que coincide, porque cuando el bucle sale, todos los conjuntos en S contienen un elemento ajustado de T , y se devuelve el conjunto de estos elementos ajustados.
Nótese que para cualquier conjunto de impacto T* y cualquier precio donde el invariante del algoritmo sea verdadero, el peso total del conjunto de impacto es un límite superior a la suma sobre todos los miembros de T* de la suma de los precios de los conjuntos que contienen este elemento, es decir: . Esto se desprende de la propiedad invariante. Además, dado que el precio de cada conjunto debe aparecer al menos una vez en el lado izquierdo, obtenemos . Especialmente, esta propiedad es verdadera para el conjunto de impacto óptimo.
Además, para el conjunto de aciertos H devuelto por el algoritmo anterior, tenemos . Dado que cualquier precio puede aparecer como máximo k veces en el lado izquierdo (ya que los subconjuntos de S no pueden contener más de k elementos de T ) obtenemos Combinado con el párrafo anterior obtenemos , donde T* es el conjunto de aciertos óptimo. Esta es exactamente la garantía de que es un algoritmo de aproximación k.
Este algoritmo es una instancia del método primal-dual , también llamado método de fijación de precios . La intuición es que es dual con respecto a un algoritmo de programación lineal . Para obtener una explicación, consulte http://algo.inria.fr/seminars/sem00-01/vazirani.html.
