Posso utilizzare l'algoritmo ungherese per trovare il costo massimo?

Question

L'algoritmo ungherese risolve il problema dell'assegnazione in tempo polinomiale. Dati i lavoratori e le attività e una matrice n × n che contiene il costo di assegnare ciascun lavoratore a un'attività, può trovare l'assegnazione di riduzione dei costi.

Voglio trovare la scelta per cui il costo è max? Posso farlo usando ungherese o un metodo simile? O questo può essere fatto solo in modo esponenziale?

Answer 1

Come Davide disse nel commento:

Multiply the cost matrix by -1 for maximization. 

Answer 2

Wikipedia dice:

Se l'obiettivo è quello di trovare l'assegnazione che produce il costo massimo, il problema può essere modificato per adattarlo all'impostazione sostituendo ogni costo con il costo massimo sottratto dal costo .

Quindi, se ho capito bene: tra tutti i costi che hai come input, trovi il valore massimo. Quindi sostituisci ogni costo x entro il max - x. In questo modo hai ancora costi positivi e puoi eseguire l'algoritmo ungherese.

Detto in modo diverso: l'ungherese cerca di ridurre al minimo il costo dell'assegnazione. Quindi, se stai cercando il massimo, puoi annullare i costi: x -> -x. Tuttavia, alcune implementazioni (non so se tutte o nessuna) richiedono numeri positivi. Quindi l'idea è di aggiungere un valore costante a ciascun costo per avere numeri positivi. Questo valore costante non modifica l'effetto risultante.