Algoritmos de Aproximación, Algoritmos Randomizados Flashcards
Expliqué qué son los algoritmos de aproximación y qué se debe tener para probar el resultado.
Los algoritmos de aproximación son algoritmos que corren en tiempo polinomial y encuentran soluciones cercanas al óptimo.
Para probar que es cercano al óptimo se debe conocer el óptomo en sí, que en general es muy difícil de encontrar.
Explique el problema de Balanceo de Cargas. ¿Qué tipo de problema es?
Se tienen:
- Un conjunto de
mmáquinasM1, ..., Mny un conjunto dentrabajos. - Cada trabajo
jtiene un tiempo de procesamientotj
Se busca asignar cada trabajo a una de las máquinas de forma tal que la carga de todas las máquinas esté lo más balanceada posible.
A(i) es el conjunto de trabajos asignados a la máquina Mi. Bajo esta asignación, la máquina necesita trabajar un tiempo total a la sumatoria de todos sus trabajos asignados. A esto se le llama “carga”.
Se quiere minimizar la cantidad conocida como ‘ makespan’, que es la carga máxima de cualquier máquina T = max1 Ti.
El problema tiene complejidad NP-Hard.
Explique el algoritmo para Balanceo de Carga
Ordenar los trabajos de mayor a menor duración.
Se hace una pasada por los trabajos. Cuando llega al trabajo j, le asigna el mismo a la máquina cuya carga sea la menor hasta el momento.
Si hay m o menos tareas, la solución es optima.
Si hay más de m tareas, entonces T* ≥ 2tm+1.
Balanceo de Carga: ¿Cómo podemos mostrar que la carga máxima T de cualquier máquina no es mucho más grande que la cantidad máxima posible T*?
Para mostrar que la carga máxima T de cualquier máquina no es mucho más grande que la cantidad máxima posible T*, usamos una cota inferior al óptimo. De esta forma, no importa qué tan bueno sea el óptimo, no puede ser menor que esta cota.
Balanceo de Carga: ¿Cuál es la carga que produce el algoritmo greedy?
El algoritmo greedy de balanceo produce una asignación de trabajos a máquinas con una carga de T <= 2T*.
Explique el Problema de Selección Central
Se tienen:
- Número entero
k - Conjunto
Sdenciudades - Una función
distancia
Sea C un conjunto de centros, asumismo que la pobalción de una ciudad va a ir a comprar al centro más cercano. Esto requiere que la distancia de un sitio a los centros sea la distancia entre el centro más cercano y el sitio.
Decimos que Cforma un r-cubrimiento si cada sitio está a una distancia a lo sumo r de los centros.
Queremos seleccionar un conjunto de k centros para los cuales r(C) sea lo menor posible.
Explique el algoritmo de Selección Central
Conocer el radio óptimo es de ayuda.
- Sabemos que existe un conjunto de
kcentros con radior. - Debemos encontrar algún conjunto de
kcentros deCcuyo radio de cubrimiento no sea mucho mayor ar.
Podemos encontrar un conjunto de k centros con un radio de cobertura de a lo sumo 2r.
Tiene que existir un centro c* que cubra el sitio s y que esté a distancia de a lo sumo r de s. Tomamos ese sitio como el centro, en vez de a c*: buscamos que s cubra todos los sitios que c* cubre, expandiendo el radio de r a 2r.
Todos los sitios que estaban a distancia a lo sumo r del centro de c* ahora están a distancia (a lo sumo) 2r de s, por desigualdad triangular.
Cualquier conjunto de centros C retornado por el algoritmo tiene un radio de cubrimiento r(C) <= 2r
Selección Central: ¿Cómo se ajusta el radio en el algoritmo?
- Si se encuentra un conjunto de
kcentros con un radio de cobertura de a lo sumo2r, se puede ir bajando la aproximación, buscando la solución óptima. - Si no se encuentra, necesitamos elevar el tamaño del radio.
Selección Central: Explique el algoritmo greedy. ¿Qué devuelve?
- Asumo que
k <= |s|, sino, definirC = S. - Seleccionar cualquier sitio
s, tal queC = {s} - Mientras |C| < k:
a. Seleccionar un sitiosenSque maximicedist(s,C)
b. Agregar el sitiosal conjuntoC - Devolver
Ccomo el conjunto seleccionado de sitios.
Este algoritmo devuelve un conjunto C de k puntos tal que r(C) <= 2r(C*), donde C* es un conjunto òptimo de k puntos.
Explique el problema de Set Cover
Tenemos una serie de conjuntos, donde cada conjunto Si tiene un peso asociado wi mayor o igual a cero.
El objetivo es encontrar un cubrimiento por conjuntos C de tal forma que el peso total sea minimizado.
Este problema es al menos tan difícil como el problema de decisión de Set Cover: si seteamos todos los wi en 1, entonces el peso mínimo de un cubrimiento de conjuntos es a lo sumo k si y sólo si existe una colección de a lo sumo k conjuntos que cubren U.
Explique el algoritmo greedy del problema de Set Cover con peso wi
-
R = U, ningún conjunto seleccionado. - Mientras R no esté vacío:
a. Seleccionar el conjuntoSique minimizawi / |Si ∩ R|
b. Borrar el conjuntoSideR - Retornar los conjuntos seleccionados.
Set Cover: ¿Cuánto más grande será el peso de este cubrimiento que el peso de un cubrimiento de conjuntos óptimo w*?
El cubrimienot por conjuntos seleccionado por el algoritmo greedy pesa a lo sumo H(d*)veces el óptimo w*, donde H(x) es la función armónica.
Vertex Cover: Explique el problema del Método de precios para minizar costos
- El peso de un vértice es el costo por el uso del mismo en el cubrimiento
- La arista es un agente separado que va a pagar algo al nodo que cubrirá.
- El algoritmo no sólo encontrará un cubrimiento por vértices
S, sino que también determinará los preciospe >= 0para cada arista, de forma tal que la suma sea de ellas cubra al precio total aproximadamente.
Vertex Cover: Método de precios para minizar costos: ¿A qué se le llama “precio justo”?
Se le llama precio justo pe si para cada vértice, las aristas adyacentes al mismo no tienen que pagar más que el costo del vértice.
La suma de todos los precios de los ejes (pe) es menor al costo del vértice (wi).
Vertex Cover: Método de precios para minimizar costos: explique el algoritmo. ¿Qué retornar?
- Seteamos pe = 0 para todos los ejes
- Mientras exista una arista
e=(i,j)tal que niinijestá pagado
a. Seleccionar esa arista e
b. Incrementar pe sin violar un precio justo
- Siendo S el conjunto de todos los nodos ajustados: retornar S
El conjunto y los precios retornados satisfacen que la suma de los precios de todas las aristas es mayor o igual al costo del conjunto.
El conjunto retornado por el algoritmo es un cubrimiento por vértices, y su costo es a lo sumo el doble del costo mínimo de cualquier cubrimiento por vértices.
