Ein geometrischer Ansatz zur Zwischenlage

Ein Input zum Zwischenlagenproblem enthält m Einschränkungen über n reellen Variablen (Punkte). Jede Einschränkung besteht aus drei Punkten, wobei einer der Punkte im Intervall definiert durch die anderen beiden liegen muss. Die Reihenfolge der anderen beiden Punkte (d. h. welcher der größte und welcher der kleinste ist) ist nicht festgelegt. Dieses Problem tritt in Fragen im Zusammenhang mit physischer Kartierung in der Molekularbiologie auf. 1979 zeigte Opatrny, dass das Problem, zu entscheiden, ob die n Punkte total geordnet werden können, während die m Zwischenlageneinschränkungen eingehalten werden, NP-vollständig ist SIAM J. Comput. , 8 (1979), S. 111--114. Darüber hinaus ist das Problem MAX SNP vollständig, und für jedes > 47/48 ist das Finden einer totalen Ordnung, die mindestens von den m Einschränkungen erfüllt, NP-schwer (auch wenn alle Einschränkungen erfüllbar sind). Es ist einfach, eine Ordnung der Punkte zu finden, die 1/3 der m Einschränkungen erfüllt (z. B. durch zufällige Auswahl der Ordnung). Dieses Papier präsentiert einen Algorithmus in polynomialer Zeit, der entweder bestimmt, dass es keine praktikable Lösung gibt, oder eine totale Ordnung findet, die mindestens 1/2 der m Einschränkungen erfüllt. Der Algorithmus übersetzt das Problem in eine Menge quadratischer Ungleichungen und löst eine semidefinite Relaxation davon in Rⁿ. Die n Lösungs Punkte werden dann auf eine zufällige Linie durch den Ursprung projiziert. Die behauptete Leistungs garantie wird unter Verwendung einfacher geometrischer Eigenschaften der semidefinierten Programmierung (SDP) Lösung gezeigt.