MaxCut e duale
Salve,
avrei un problema da esporre, che spero mi aiutiate a risolvere.
Espongo tutto il problema in vari pezzi:
Ad un corso di algoritmi, si è parlato del problema NP, Max-Cut (taglio massimo).
Subito si può pensare al suo corrispondente problema contrario Min-Cut (taglio minimo). Il modo consueto per risolvere questo problema, è usare il problema di flusso massimo,
e precisamente dal teorema flusso massimo-taglio minimo.
sempre al corso, si è parlato di Dualità, solamente però nella Programmazione Lineare per dimostrare che l'algoritmo del simplesso da sempre una soluzione ottima.
Il problema di flusso massimo/taglio minimo, può essere ridotto ad un problema di Programmazione Lineare.
La mia domanda: il duale del problema di flusso massimo/taglio minimo con LP, a cosa corrisponde? Cioè che problema risolve?
cioè, se nella programmazione lineare il problema di flusso diventa:
massimizzare "flusso" (primale)
il duale è:
minimizzare "flusso"
il problema duale se viene risolto, a che problme corrisponde:
flusso minimo/taglio minimo?
flusso minimo?
e estremizzando: flusso minimo/taglio massimo?
Lasciando da parte il problema di flusso:
il duale del problema di Max-Cut (taglio massimo) è Min-Cut (taglio minimo)?
Forse non ho esposto in modo chiarissimo, ma se avente intuito il mio dubbio, spero rispondiate.
Ringrazio chi aiuta
avrei un problema da esporre, che spero mi aiutiate a risolvere.
Espongo tutto il problema in vari pezzi:
Ad un corso di algoritmi, si è parlato del problema NP, Max-Cut (taglio massimo).
Subito si può pensare al suo corrispondente problema contrario Min-Cut (taglio minimo). Il modo consueto per risolvere questo problema, è usare il problema di flusso massimo,
e precisamente dal teorema flusso massimo-taglio minimo.
sempre al corso, si è parlato di Dualità, solamente però nella Programmazione Lineare per dimostrare che l'algoritmo del simplesso da sempre una soluzione ottima.
Il problema di flusso massimo/taglio minimo, può essere ridotto ad un problema di Programmazione Lineare.
La mia domanda: il duale del problema di flusso massimo/taglio minimo con LP, a cosa corrisponde? Cioè che problema risolve?
cioè, se nella programmazione lineare il problema di flusso diventa:
massimizzare "flusso" (primale)
il duale è:
minimizzare "flusso"
il problema duale se viene risolto, a che problme corrisponde:
flusso minimo/taglio minimo?
flusso minimo?
e estremizzando: flusso minimo/taglio massimo?
Lasciando da parte il problema di flusso:
il duale del problema di Max-Cut (taglio massimo) è Min-Cut (taglio minimo)?
Forse non ho esposto in modo chiarissimo, ma se avente intuito il mio dubbio, spero rispondiate.
Ringrazio chi aiuta
Risposte
Ho trovato risposta alle domande che ho posto, su questo sito:
http://www2.units.it/orts/didattica/Lez ... to_min.htm
il duale di max-cut ovviamente non è min-cut.
http://www2.units.it/orts/didattica/Lez ... to_min.htm
il duale di max-cut ovviamente non è min-cut.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo