NP-Completezza per il programma lineare intero

Question

Questo è un problema dei compiti a casa, quindi non voglio la soluzione.Ho bisogno di un suggerimento che problema per ridurre il seguente e / o come iniziare.Stavamo pensando a TSP o set indipendente ma non abbiamo potuto inventare una soluzione.

abbiamo $ i \ ldots j $ negozi e $ i \ ldots n $ possibili posti aCostruisci un nuovo magazzino.I costi per costruire un nuovo magazzino sono $ c_j $ .Tra ogni negozio e magazzino è un percorso di costo $ d_ {i, j} $ .Ogni negozio deve essere collegato ad almeno un magazzino.

Il problema decisionale è: Esiste un set di magazzini e percorsi in modo che la somma sia più piccola di un dato numero $ k $ .

Answer 1

Questo è un classico Facility Location Problem . Quell'articolo di Wikipedia suggerisce che la durezza NP può essere dimostrata dalla riduzione da Set Cover . .

Poiché l'Asker ha ora dichiarato di aver trovato una soluzione riducendo da copertura vertice , andrò avanti e rivelerò la riduzione da coperchio del set :

Per ogni valore, creare un negozio; Per ogni set, creare un magazzino. Assegnare il costo di ciascun magazzino 1. Assegnare il costo del percorso da un magazzino a un negozio per essere un valore arbitrariamente piccolo se quel set di magazzino contiene il valore del negozio o un valore arbitrariamente grande altrimenti. Quindi la soluzione minima del costo per il problema della struttura si basa con precisione il set di magazzini corrispondenti al coperchio minimo del set nel problema originale.


. La $ K $ Valore viene utilizzato per trasformare il problema di ottimizzazione (minimizzare i set / costi) in un problema decisionale (esiste una soluzione senza più di $ k $ Imposta / costo?). La $ K $ dall'istanza del coperchio impostata sarà la stessa della $ k $ nel problema della struttura Istanza Se è consentito impostare i valori "arbitrariamente piccoli" su esattamente 0 - altrimenti potrebbe essere necessario distinguere il valore con qualche importo, ma meno di 1 purché si scelgono i pesi "arbitrariamente piccoli" per essere abbastanza piccoli. Hai solo bisogno del totale di ogni costo "arbitrariamente piccolo" per essere inferiore a 1, e ogni costo "arbitrariamente grande" per essere maggiore della somma dei costi di tutti i magazzini e tutti i percorsi "arbitrariamente piccoli".

. Si noti che, se solo i costi interi sono ammessi nel problema dei servizi, è comunque possibile ottenere lo stesso risultato ridimensionando tutti i costi con il loro minimo comune multiplo.