Zuweisung verteilter Speicher unter Maximierung der minimalen gewichteten Bandbreite

Bei dem betrachteten Speicherproblem werden Daten mit verschiedenen Zugriffswahrscheinlichkeiten auf Speicher mit verschiedenen Bandbreiten und Kapazitäten aufgeteilt, dabei sind Replikate erlaubt. Es wird die nach Zugriffswahrscheinlichkeit gewichtete kleinste Bandbreite der Daten maximiert. Wir zeigen, dass sowohl das diskrete Speicherproblem, bei dem die Bandbreite der Speicher jeweils gleichmäßig auf die dort abgelegten Daten aufgeteilt wird, als auch das kontinuierliche Speicherproblem, bei dem die Bandbreite der Speicher beliebig auf abgelegte Daten verteilt werden darf, NP-schwer ist. Es können also, wenn P ̸ = NP, keine effizienten Algorithmen für eine optimale Lösung existieren. Stattdessen zeigen wir jeweils einen 1/2-Approximationsalgorithmus.