k-aproximación del conjunto de k-golpes
En informática , la aproximación k del conjunto de aciertos k es un algoritmo de aproximación para el conjunto de aciertos ponderado . La entrada es una colección S de subconjuntos de algún universo T y un mapeo W de T a números no negativos llamados pesos de los elementos de T. En k-hitting set, el tamaño de los sets en S no puede ser mayor que k . Es decir, . El problema ahora es elegir algún subconjunto T ' de T tal que cada conjunto en Scontiene algún elemento de T ', y tal que el peso total de todos los elementos en T ' es lo más pequeño posible.
Para cada conjunto en S se mantiene un precio , , que inicialmente es 0. Para un elemento a en T , sea S ( a ) el conjunto de conjuntos de S que contiene a . Durante el algoritmo se mantiene el siguiente invariante
Decimos que un elemento, a , de T es compacto si . La parte principal del algoritmo consiste en un bucle: siempre que 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 ciclo sale, todos los conjuntos contienen algún elemento apretado. Elija todos los elementos apretados para ser el conjunto de bateo.
El algoritmo siempre termina porque en cada iteración del ciclo el precio de algún conjunto en S aumenta 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 hará más iteraciones que el número de elementos en la unión de todos los conjuntos de S . Devuelve un conjunto de aciertos, porque cuando el ciclo sale, todos los conjuntos en S contienen un elemento ajustado de T , y se devuelve el conjunto de estos elementos ajustados.