Problema 3

[AsLogd]

En el problema 3, si lo he entendido bien, se pide resolver una especie de vertex cover, donde tenemos dos tipos de vertices: -los vertices que representan un equipo de vigilancia (T) (con coste c, el precio de contratar al equipo) -los vertices que representan una localizacion (L) Para el equipo t de T con una camara en la localizacion l de L, hay una arista (t,l) Tenemos que seleccionar un subconjunto de T minimo que cubra todo L.

[AsLogd]

Podemos definir el problema como un weighted set cover: Un universo U={l_1, ..., l_n} de localizaciones que hace falta vigilar. Un conjunto de tuplas (conjunto, coste) S={(t_1,c_1),...,(t_n,c_n)}, donde cada tupla representa un equipo: un conjunto de las localizaciones que puede vigilar y el coste asociado. Queremos seleccionar todos los elementos de U minimizando la suma de los costes

[AsLogd]

Un greedy para weighted set cover: http://www.cs.huji.ac.il/course/2005/algo2/scribes/lecture2.pdf

[AsLogd]

Problema: las soluciones que he encontrado no tienen un factor de aproximacion constante

[daniconde]

Aquí dan una 2-approx pasando a linear programming: http://web.cs.iastate.edu/~cs511/handout10/Approx_VC.pdf

[AsLogd]

No es lo mismo weighted vertex cover que weighted set cover jajaja. Creo que lo que hare sera justificar que n es constante en este problema...

[daniconde]

Nada, estaba interpretando mal el problema

[AsLogd]

Ya, yo tambien tiraba por ahi al principio... pero claro, el problema no busca cubrir todas las aristas, solo se quieren cubrir las localizaciones

[AsLogd]

Da la impresion de que falta alguna cota, quiza hay alguna implicita en el enunciado

[daniconde]

Es que de esto entiendo que si existe una aproximación con factor constante entonces P = NP jajajaja.

No sé, me he leído el enunciado una y otra vez y no veo por donde se puede acotar. Tampoco veo manera de interpretarlo como un problema más sencillo que un weighted set cover.

[gonsp]

Mmmm tampoco le veo la diferencia de este problema con el weighted set cover. Osea es 100% igual!!!

[gonsp]

Enviamos mail diciendo algo como: "Creemos muy fuertemente que el problema es idéntico a weighted set cover y por lo tanto no existe constant time approx. Puedes asegurarnos que el problema es correcto?"?

[gonsp]

He enviado mail

[gonsp]

No sé si habéis visto el cambio de Maria, pero aún así lo sigo viendo equivalente a Weighted Set Cover. Esto es lo que le acabo de responder, a ver si estamos de acuerdo con mi interpretación:

---

Gracias por tu respuesta,

De todas formas esto me crea otra duda más:

"... looking to the images of all the surveillance locations covered by their camera"

Lo de que una cámara puede cubrir más de una location es nuevo, osea no lo entendía así con la versión original. Si esto es verdad, entonces creo que el problema sigue siendo Weighed Set Cover. Me explico:

Originalmente, me pensaba que había unas locations que estaban cubiertas con relación uno a uno por una cámara. De forma que era equivalente hablar de location o de cámara. Y aparte estaban los teams que poseían unas de esas cámaras, los cuales podían compartir cámaras entre ellos. Por eso, bajo este setup, el problema era Weighted Set Cover.

Con la nueva versión, lo que interpreto es que cada team solo tiene una cámara, por lo que ahora es equivalente hablar de un team o de una cámara. Y aparte están las locations. Una cámara puede cubrir una o más locations, y pueden compartir locations entre ellas. Este nuevo setup también es equivalente a Weighted Set Cover.

Hay algo que estoy entendiendo mal?

Gracias

[AsLogd]

Yo del enunciado original entendia que cada location tiene varias camaras (pertenecientes a diferentes equipos), Es decir, que podria ser que un mismo location lo pudiera cubrir con una camara "cara" o con una camara "barata", dependiendo de lo que cobre ese equipo. Lo que me hace pensar eso es esta frase:

For each of those locations, they have collected the surveillance teams that have cameras visualizing the location

Es decir, por cada location (a ser cubierto) hay diversos equipos con una camara para cubrirlo. En el original decia esto:

Assume, for this exercise, that a surveillance team receives a fix amount of money for looking to the images of all the cameras assigned to it.

Con lo cual se entiende que al contratar un equipo, cubres todas las locations donde tienen una camara. En conclusion: para mi en el original no habia ninguna incongruencia como dice ella, lo unico que es claramente un weighted set cover.

En la version editada, ahora si que no me cuadra la frase nueva con la primera cita que he puesto. Me parece que no tiene sentido

Edit: bueno, realmente creo que no hay nada que contradiga el hecho de que las camaras puedan ver mas de un location, pero me parece que si, sigue siendo un set cover (pero mas complejo?)

Edit2: Me parece que este cambio (una camara puede ver varios locations), junto con la cita del enunciado:

Each camera has a unique surveillance team that can visualize the images on the spot.

Hace una representacion como la del dibujo. Una camara solo tiene un equipo padre, y un equipo tiene varias camaras. Una location puede tener varias camaras padre. De forma que al final lo que queda es que puedes preprocesar y patillarte las camaras y queda un weighted set cover sea como sea

[ghost]

Yo sigo entendiendo que hay equipos (T) y localizaciones (L) y tenemos un grafo que para cada T nos conectamos a las localizaciones que podemos vigilar. Además tenemos un coste de seleccionar cada T_i y queremos cubrir todos los L minimizando este coste. Lo veis así?

Puede que el enunciado sea correcto pero se haya equivocado al pedir un constant factor approx.

[AsLogd]

Yup

[BowlOfPetunias]

Si hubiera un tope en el numero de localizaciones que cada equipo T puede vigilar, por ejemplo k, entonces existe una k-aproximacion. Supongo que se ha olvidado de el tope este. https://en.wikipedia.org/wiki/K-approximation_of_k-hitting_set

[AsLogd]

Si. Es lo que puse hace unos comentarios. Que parece que falte una cota. En clase resolvi el set cover unweighted, y tenia una r-aproximacion porque estaba limitado a k sets

Edit:De todas formas hitting set es diferente a set cover, no?

[BowlOfPetunias]

Los dos problemas son equivalentes, solo son formulaciones diferentes del mismo problema.

[gonsp]

Nuevo mail debido a la re-corrección ambigua:

---

Gracias por la corrección.

Siento insistir pero sigo viendo alguna ambigüedad. Por ejemplo:

Si con "in any case" significa "en cualquier caso" (traducción correcta), estás dando un lower bound. Y aún así, no sé si te refieres a que para cubrir todas las locations hacen falta como mínimo 5 cámaras o que para cada location hay como mínimo 5 cámaras?

Si con "in any case" significa "en ningún caso" (traducción literal), estarías dando un upper bound. Significa que para cubrir todas las locations hacen falta 5 o menos cámaras? O que cada location solo es cubierta como máximo por 5 cámaras?

De estas posibilidades, si fuera "cada location solo es cubierta como máximo por 5 cámaras", el problema se convierte en un k-weighted cover set, el cual sí que tiene aproximación constante (5-approximation), por lo que el apartado a se podría resolver. Creo que es lo que tendría más sentido pero no me cuadra con tu mensaje anterior porque das a entender que ahora podemos resolver el apartado b pero no el a.

Podrías aclarar esto?

Gracias

[gonsp]

Uff, el k-hitting set no es exactamente igual que el set cover.... Osea he leído que es primal-dual, pero el algoritmo de wikipedia de la k-approximation de k-weighted hitting set no la podemos usar tal cual... (si os fijáis, en este setup las locations tendrían un precio, y en realidad lo tienen las cámaras). Se debería de primero pasar el problema de k-weighted set cover a k-hitting set para poder aplicar este algoritmo, pero no estoy entendiendo cómo hacerlo... Os lo podéis mirar?

[ghost]

En este artículo parece que sí que modela nuestro problema, no? http://www.cslog.uni-bremen.de/teaching/summer17/approx-algorithms/resource/lec3.pdf

La cosa es, que estamos partiendo de la base que cada equipo tiene una única cámara y cada cámara pertenece a un único equipo, no? Al final esto era una suposición nuestro o estaba en el enunciado?

[gonsp]

En este artículo parece que sí que modela nuestro problema, no? http://www.cslog.uni-bremen.de/teaching/summer17/approx-algorithms/resource/lec3.pdf

Aquí dan una log(n)-approximation porque el problema es Weighted Set Cover, el nuestro es k-Weighted Set Cover y necesitamos una aproximación constante, así que esto no sirve...

Al final esto era una suposición nuestro o estaba en el enunciado?

Esto es así. Me ha confirmado María que es un k-Weighted Set Cover así que sí.

[ghost]

Ya, me refería a que en una formalización parece que la función de pesos está en los sets y en la otra en los elementos.

[gonsp]

Ya, pero cómo haces ese cambio? En el pdf no mencionan nada de eso, no?

[ghost]

lec21.pdf

En la segunda página comparan los 2 problemas y muestran transformaciones para pasar de uno a otro. Si no deja claro del todo los pasos después me lo miro con más detenimiento!

[gonsp]

Vale buena aportación! Creo que me estaba liando yo solo. Para solucionar el problema solo habria que mencionar que formulamos el problema como k-hitting set y damos el algoritmo de k-approximation k-hitting set y ale

[gonsp]

Vale nono, PUTADA GRANDE: k-set cover no es equivalente a k-hitting set. Por lo que no podemos utilizar el algoritmo de k-approx k-hitting set, ya que en el setup de k-hitting set, cada location solo podría aparecer en como máximo k cámaras. Pero lo que sabemos es que cada cámara no apunta a más de k locations....

[AsLogd]

Vale ya decia yo que no lo veia claro.. Estuve buscando y encontre una k aproximacion de wsc pero el parametro era sobre el universo. Con una cota en Hk. Tambien vi que mencionaban que se supone que se podia acotar sobre la mida del set maximo (lo que nos interesa) pero no he encontrado ninguna demostracion. Luego busco el pdf donde se mencionaba esto

El mié., 13 jun. 2018 13:34, Gonzalo Solera Pardo notifications@github.com escribió:

Vale nono, PUTADA GRANDE: k-set cover no es equivalente a k-hitting set. Por lo que no podemos utilizar el algoritmo de k-approx k-hitting set, ya que en el setup de k-hitting set, cada location solo podría aparecer en como máximo k cámaras. Pero lo que sabemos es que cada cámara no apunta a más de k locations....

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/AsLogd/Problemes-Ampliaci-Algorismia/issues/2#issuecomment-396906333, or mute the thread https://github.com/notifications/unsubscribe-auth/AGjuNYJHVEXOm7iNAyRfNGbjmycbbWgZks5t8PjCgaJpZM4Ug9Se .

[gonsp]

Ah pues sería muy clave ese pdf. He enviado un mail y tal vez me he pasado de listo si existe el algoritmo que dices

[AsLogd]

Vale, tengo estos dos pdfs: p1.pdf En este se menciona:

...When we consider instances of the weighted set-cover such that each Sj has at most k elements (|S|≤k for all S ∈F), we obtain the weighted k-set cover problem...

y

...It is well known (see [2]) that a greedy algorithm is an Hk-approximation algorithm for the weighted k-set cover, where Hk is the k-th harmonic number...

Lo que me da a entender que existe un algoritmo con factor Hk con k = max(|Sj|) para todo subconjunto S. Encuentro algo parecido en este otro pdf: p2.pdf

it can be approximated to a factor of Hd = logd + O(1), where d = max{|S| : S ∈ F}, at least for the special case where cost(S) = 1 ∀S ∈ F

Parece que dice lo mismo pero no esta claro por ese "at least". En ningun caso he encontrado como demostrar esto. En este ultimo pdf lo demuestra con una cota sobre |U|. Luego he encontrado esta referencia: D. S. Hochbaum, "Approximation algorithms for the weighted set covering and node cover problems," SIAM Journal on Computing, 11, 555-556, 1982 Pero no he encontrado el paper

[arnaubadia]

A nuestro grupo le toco hacer el ejercicio 18 de aproximación, que va precisamente de demostrar porque un algoritmo que te dan es una k-aproximación de k-set covering. En su día le presenté una solución que me la dio por buena, pero ahora fijándome creo que está incompleta. Faltaría demostrar que en cada iteración encuentra un set con valor >= 1/k (que supongo que tiene algo que ver con que los sets sean de tamaño k como máximo). Os dejo mi solución aquí. Se la entregué escrita a mano, sorry. ex3a.pdf

[AsLogd]

No acabo de pillar los pasos pero tiene buena pinta. Luego lo estudiare con calma

[BowlOfPetunias]

No entiendo las restricciones que poneis en el problema. Tal como esta no estarian todos los sets dentro del cover ya que Xs >= 1? Faltaria una variable que indicara si un elemento esta cubierto al estilo Xs >= e para todo e dentro de Xs. I entonces para todo e >= 1, no?

[arnaubadia]

Lo que dice es que para cada elemento del universo, como mínimo uno de los sets que contienen ese elemento tiene que formar parte de la set cover.

[gonsp]

De todas formas necesitamos un algoritmo para la versión con pesos. La vuestra es sin pesos, no?

[arnaubadia]

No, es con pesos. Cada set tiene un coste asociado a él.

[gonsp]

Uops cierto, estoy empanado

[gonsp]

No entiendo vuestra demostración. Tampoco me explico que tengáis una k-approximation cuando hemos visto papers en que la versión unweighted es H_k approximable, y no k-approximable... No puede ser que una versión más fácil de este problema no se pueda aproximar mejor que la versión más difícil...

[AsLogd]

Creo que Hk <= k (H1 = 1, despues Hk siempre < k)

[gonsp]

Ah vale pues otra cagada mía jajaja. Entiendes todos los pasos @AsLogd ?

[AsLogd]

Ahora estoy intentando demostrar la parte que falta, que es lo de que en cada iteracion se puede seleccionar un conjunto con 1/k. Lo demas aun no me he puesto muy a tope, pero me parece que tiene sentido. Muchas veces para dar una k-aprox basta con dar una cota de cuanto mejora el bucle (osea que es bastante importante la parte que falta jajaja) A ver si lo consigo y lo subo redactado y tal

[AsLogd]

Vale, no se si me estoy perdiendo algo pero creo que no es cierto lo de 1/k en cada iteracion. Dado S={(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)} (k=2) y asumiendo peso 1, si no me equivoco la solucion optima de LP seria dar 0.33 a cada conjunto (ya que cada numero esta tres veces), que es mas pequeño que 1/2. A partir de este argumento creo que es de donde sale un algoritmo f-aprox, donde f diria que es la frecuencia de un elemento en cada set

[AsLogd]

Bueno, despues de estar toda la noche con el tema este no he conseguido llegar al algorismo de H_k. Estaba intantando pillar el algoritmo del pdf que subi mas arriba (para la version sin k) y meterle la k en algun sitio. En concreto el algoritmo usa |T_i-A| (el tamaño de un nuevo conjunto seleccionado menos la solucion parcial) y esto sabemos que como mucho es k. He intentado jugar con eso pero buah, no he conseguido nada. Para la version sin parametro la definicion de la cota es bastante natural, por que especifica una desigualdad para cada uno de los elementos de U (y de ahi sale la serie harmonica H_n (OPT*(1+1/2+1/3+...+1/n)), el problema es que al añadir el parametro k, no entiendo como tendremos H_k pero seguiremos con n elementos (sobre que elementos se definen k desigualdades?).

[gonsp]

Solo por si acaso, alguien tiene alguna idea con la pregunta b? @DavidMoranPomes al final le has echado un vistazo?

[gonsp]

Bastaria con argumentar que Set Cover es FPT respecto el número de sets, ya que FPT \in W[1] pero no sé si es cierto

[AsLogd]

El apartado b el problema creo seria exactamente igual al problema 3 de la lista de problemas (esta en el repo solucionado). En principio ahi se demuestra que es FTP porque existe una 1.58-aprox. (Pero como tengas que demostrar eso en el examen te mueres)

Edit; Yo argumentaria que esta solucionado en clase, sino es muerte

[josepdecid]

Es pot demostrar que es FPT amb paràmetre k, ja que tens n sobre k possibles subconjunts ≈ n^k i cadascun es pot mirar en temps polínomic.

Com FPT ⊆ W[1] ja estaria i crec que això no cal demostrar-ho perquè ho vam veure a classe em sembla...

[josepdecid]

El que no em quadra és que en l'última correció on va afefir "Furthermore, in any case a camera covers NO more than 5 surveillance positions.", diu que ho necessitem per resoldre tots dos apartats (entenc que el de màxim 5) però no veig on ajuda 😐

[AsLogd]

n^k no es funció de k, no? Jo crec que aixo no es FPT. I lo segon ni idea