Problema 1

[DavidMoranPomes]

Yey! Tinc el primer problema resolt aquí. Hi ha una part que no tinc molt clara la demostració (per no dir que me la he patillat bastant), la he marcat entre ######. Si algú se li acut com demostrar-ho m'alegrarà el problema jajajajaja

[AsLogd]

Working on it ^. A veure si trec algo

[AsLogd]

Aquesta part m'esta costant, crec que es veuria beneficiada de una mica de rephrase. Al primer paragraf, l'aresta que elimines s'ha de fer amb cuidado no? si no podria ser que deixi de ser connex; que es S en aquesta part? que vols dir amb lo de que "no podem tenir la tercera per que d(S) hauria de incloure una altre aresta del cicle"?

[AsLogd]

Una tonteria, pero fijate que en la version actual la funcion objetivo no hace referencia a los p_i (que no tiene mucho sentido en este caso)

[DavidMoranPomes]

L'últim que dius no ho entenc. Segons l'enunciat:

The goal is to find a tree T rooted at r that minimizes the cost of the edges in the tree plus the penalties of all vertices not in the tree.

El que sí que és cert és que a on posa p_i y_i hauria de ser p_i (1 - y_i).

[AsLogd]

Aqui no falta tenir en compte els penaltis? (just lo que sobrava a l'apartat a)

[AsLogd]

(sobre lo anterior)

[DavidMoranPomes]

Ja veig el que dius. La formulació de cost del IP no és la mateixa que la del problema general, ja que el IP només resol una part del problema (SIMPLE resol l'altra)

[AsLogd]

Hmmm. Precisament SIMPLE no te en compte els penaltis no? De totes formes no se si ILP i simple es poden combinar facilment en aquest sentit. Podries detallar mes aquest argument? potser es que no testic entenent

[DavidMoranPomes]

Vale, ho he tornat a llegir. Tens raó en que per als apartats (a) i (b) la formulació és la curta, però al (d) és la llarga (sino no surt la 3-aproximació).

[AsLogd]

Vale, estem d'acord que en el a) es la versio sense els penaltis (no calen per que el graf sigui un arbre). Pero al b) si cal, no? Si no no minimitzes el fet de deixar fora vertexos

[DavidMoranPomes]

Vale, té sentit. Perque el fet d'ampliar la formulació no fà que la solució deixi de ser un arbre. En realitat, seria més senzill a l'enunciat fessin servir la formulació amb totes les penalitzacions al a) també, pero meh. Al c) em penso que no hi intervé per a res, i al d) és necessari utiltizar les penalitzacions.

[AsLogd]

Vale, segueixo mirant

[DavidMoranPomes]

He arreglat lo de la formulació aquí. Ara em reviso el primer que m'has dit!

[DavidMoranPomes]

També he arreglat el paràgraf que em deies al principi. Aquí tens el pdf.

[AsLogd]

Guai, gracies, porto una estona pensant que segurament es pot veure que el numero de restriccions es exactament n2^n. No es super important, i crec que tampoc es demana que es demostri, pero bueno

Edit: bueno, ese "observe" no se si es una pista o una ordre xD

[DavidMoranPomes]

Sincerament, m'ha fet pal filar més prim jajajajaja Si t'hi vols posar i ho treus ho afegeixo.

[DavidMoranPomes]

T'has mirat el 4 (c)? (la primera formula)

[AsLogd]

EDIT: res m'estava confonent

[AsLogd]

Vale a veure. Quan dius d(S) = e, vols dir d(S) = {e} o e pertany a d(S)? En el primer cas, el sumatori no te sentit, per que només tens un element x_e. Llavors dius que x_e (el resultat de LP per l'aresta e) es més gran que y_i (el resultat de ILP pel vertex i, aqui potser volies dir y_i?). Es a dir, si el vertex 'i' no esta agafat, x_e pertany a [0,1], si si que esta agafat, llavors x_e=1 (com es justifica aixo?). Llavors dius que com que almenys un dels vertexos de e esta a T, y_i >= a i per tant x*_e >= a, i dius que es una contradiccio, pero no veig per que aixo es contradictori... hmm

[adrian729]

Una pregunta, en l'apartat "a", si ens donen un graf amb tots els costos c a 0 es compleix sempre? La funció objectiu a minimitzar donarà sempre 0 independentment de com s'assigni res, no acabo de veure que s'hagi de complir que sigui acíclic en aquest cas, ja que no hi ha cap millora o empitjorament en cap moment.

[AsLogd]

Si tens rao. Jo havia pensat argumentar que hauriem de minimitzar tambe el numero de arestes

[AsLogd]

O obligar a que el cost d eles arestes es major estricte que 0

[adrian729]

Si el que dius, però sense cap d'aquestes dues coses ara mateix l'enunciat crec que està malament.

[AsLogd]

Si. Estic dacord. Envia un mail si vols/pots

[DavidMoranPomes]

A veure, em sembla una mica chorra rebuscar aquests casos extrems. Si totes les arestes tenen pes 0 el resultat pot no ser un arbre, però també podem trobar una solució equivalen que sigui un arbre. De tota manera, en aquest cas la resolució del problema també és trivial. Si voleu envieu mail, però jo no crec que faci falta.

[AsLogd]

Bueno el fet es que demostris que es un arbre. I pot no serho a no ser que es canvii lenunciat. A mi em sembla prou justificat. Nomes es canviar la desigualtat

El mar., 12 jun. 2018 18:36, David Moran notifications@github.com escribió:

A veure, em sembla una mica chorra rebuscar aquests casos extrems. Si totes les arestes tenen pes 0 el resultat pot no ser un arbre, però també podem trobar una solució equivalen que sigui un arbre. De tota manera, en aquest cas la resolució del problema també és trivial. Si voleu envieu mail, però jo no crec que faci falta.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/AsLogd/Problemes-Ampliaci-Algorismia/issues/13#issuecomment-396654381, or mute the thread https://github.com/notifications/unsubscribe-auth/AGjuNfdsNICiBmOVobQBetayGa0QQVbgks5t7-3xgaJpZM4UjAV4 .

[adrian729]

Jo li he enviat el correu dient-li això, que segurament sigui una tonteria i només un cas extrem però per si era un error li comento.

[adrian729]

Hola Adrián,

Tienes razón, si hay aristas con coste 0 entonces pueden aparecer soluciones óptimas que no son arboles ya que siempre puedes añadir aristas con peso cero sin aumetar el coste.

Puedes asumir que todos los pesos (tanto de aristas como de vertices) son mayores que cero.

Maria

[Urigueler]

Respecte l'apartat que segueix entre #####, encara és la versió inicial? perquè ho estava mirant i trobo que té força sentit...

[AsLogd]

Jo encara estic esperant comentar aquella part. He escrit un comentari amb dubtes, no acabo de entendrela

[Urigueler]

Tu suposes que hi ha una aresta e que no satisfa x*_e >= a/2.

Ara agafem el subconjunt S tal que d(S) = {e}. Si e esta en el tall un vertex dels extrems sera a V(T) i per definició aquell vertex tindra y*_i >= a.

Abans ens donen la norma del sumatori dels x_e de les arestes del tall i ens diu que es mes gran que qualsevol y_i d'S. Com que e és l'única aresta del tall, x_e ha de ser mes gran que totes les y_i d'S (individualment), per tant més gran que a, ja que hem trobat una y*_i més gran que a.

Això entra en contradicció amb la suposició que x*_e < a/2.

Jo ho entenc aixi...

[AsLogd]

Guai, ara quan arribi a casa estudio el que has dit amb deteniment

El mar., 12 jun. 2018 22:38, Urigueler notifications@github.com escribió:

Tu suposes que hi ha una aresta e que no satisfa x*_e >= a/2.

Ara agafem el subconjunt S tal que d(S) = {e}. Si e esta en el tall un vertex dels extrems sera a V(T) i per definició aquell vertex tindra y*_1

= a.

Abans ens donen la norma del sumatori dels x_e de les arestes del tall i ens diu que es mes gran que qualsevol y_i d'S. Com que e és l'única aresta del tall, x_e ha de ser mes gran que totes les y_i, per tant més gran que a, ja que hem trobat una y*_i més gran que a.

Això entra en contradicció amb la suposició que x*_e < a/2.

Jo ho entenc aixi...

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

[AsLogd]

Tu suposes que hi ha una aresta e que no satisfa x*_e >= a/2.

Ara agafem el subconjunt S tal que d(S) = {e}. Si e esta en el tall un vertex dels extrems sera a V(T) i per definició aquell vertex tindra y*_i >= a.

A veure si et segueixo: Suposem que a T hi ha una e = (v_1, v_2) i d(S)=e. Es obvi que v_1 i v_2 son de V(T). Qualsevol vertex de V(T) compleix que y_i >= a. Correcte. Llavors dius que sabem que x_e (ja que el sumatori de un es ell mateix) es més gran que y_i de S, x_e >= y_i. Pero es veritat aixo? El sumatori que comprovem es fa per la versio de ILP amb x_e i y_i, pero un cop feta la relaxacio com sabem si aixo continua funcionant? Suposant que aixo continua funcionant, llavors tenim que x_e >= y_i >= a i entra en contradiccio amb x_e < a/s. Correcte.

L'unic que no acabo de veure clar es si aixo se mante a la relaxacio

[AsLogd]

Un fallo tonto:

𝑦𝑖∗ ≥ 𝛼 ⟺ 𝑖 ∈ 𝑉(𝑇). Així, podem afirmar que 𝑖 ∉ 𝑉(𝑇) ⇒ 𝑦𝑖∗ ≤ 𝛼

Hauria de ser y*_i < a a la segona implicacio no?

[AsLogd]

Una altre cosa: a l'apartat d) es parla del opt(G) fent referencia a les variables indicadores de LP (amb el asterisc). Per ser l'optim de veritat aixo hauria de ser el resultat de ILP (sense el asterisc), no?

[DavidMoranPomes]

Si faig el que dius tu, el problema no té solució, perque no tenim cap equació referent als valors sense asterisc ^^'

[DavidMoranPomes]

Vale, espera, tinc una idea. Ho arreglo i ho pujo, a veure que tal

[AsLogd]

Vale, ben solucionat ^

[cclaverol]

A mi el c em sembla correcte. Fixeu-vos que és una relaxació del ILP, així que aquesta restricció, que teníem al ILP, no canvia, s'ha de complir per definició.

[gonsp]

Qué es lo que no sabéis si está bien del apartado c?

[AsLogd]

Creo que estamos de acuerdo en que todo correcto

[DavidMoranPomes]

@GonMolon yo no me fío de mi demostración de que x*_e ≥ alpha

[gonsp]

Ok, yo también lo veo bien

[gonsp]

En el apartado c, cuando demuestras x_e \in T >= alpha/2, también lo podrías hacer para x_e \in T >= alpha, no? (osea x_e >= alpha en vez de alpha/2)

[DavidMoranPomes]

Precisamente por eso no me gusta. El problema es que no tengo claro que siempre puedas encontrar S tal que d(S) = {e}.

[gonsp]

Sii, sí que puedes. Sabes que T es un árbol, pues simplemente metes un vértice de e en una partición y el otro vértice en la otra. En la primera partición metes todos los vértices que están contectados con el primer vértice y que esos paths no pasan por e. En la segunda partición metes todos los vértices que están contectados con el segundo vértice que no pasan por e. Como es un árbol, sabes que no hay ciclos así que no puede haber otra edge entre los nodos de la primera partición con los de la segunda, por lo que los edges del corte solo será e

[DavidMoranPomes]

El problema es que la partición se hace sobre E, no sobre T. Puede haber otras aristas en E adyacentes a los extremos de e que formen un ciclo por fuera :(

[DavidMoranPomes]

En particular, para un grafo con minCut k, el tamaño de d(S) siempre será ≥ k

[gonsp]

Ah cierto cierto

[AsLogd]

I no es suficient dient que e=(i,j) \in d(S) sabent que e \in T? Com que e \in T, llavors y_j,y_i >=a i x_e >= a. Es a dir, dius que e pertany al cut d(S), pero com que saps que es de T, saps que els dos vertexos tambe estan a T i per tant x_e >= a

Edit: Ah vale, acabo de entendre el que deies abans xD Edit2: bueno, not sure. No pot haber un cicle que conecti els dos vertexos per que saps que e \in T, saps que aquell ha de ser l'unic cami, no?