Andreas Brieden, TU München (Koautor: P. Gritzmann)
Für einen Graph auf Knoten bezeichne die Kardinalität einer maximalen stabilen Menge in , das zu gehörige Stable-Set-Polytop und eine Relaxation von , d.h. . Der geometrische Rank von ist definiert als das kleinste , so daß an einer ganzzahligen Ecke angenommen wird und somit entspricht.
Es gilt , wobei trivial aus folgt und bedeutet, daß mit linearer Optimierung über berechnet werden kann.
Für beliebiges gibt es Relaxationen, deren geometrischer Rank nach oben durch beschränkt und für die das Separationsproblem in polynomieller Zeit gelöst werden kann. Andererseits ist unter der Annahme Separation für Relaxationen mit endlichem geometrischen Rank (also unabhängig von der jeweiligen Knotenzahl ) nicht in polynomieller Zeit möglich.
E-Mail: | brieden@ma.tum.de |
Homepage: | www-m9.ma.tum.de/~brieden/ |