15. ÖMG-Kongress
Jahrestagung der Deutschen Mathematikervereinigung

16. bis 22. September 2001 in Wien

Sektion 3 - Diskrete Mathematik, Algorithmen
Dienstag, 18. September 2001, 17.30, Hörsaal 23

 

Stabile Mengen, Relaxationen und geometrischer Rank

Andreas Brieden, TU München (Koautor: P. Gritzmann)

 

Für einen Graph $G$ auf $n$ Knoten bezeichne $\alpha$ die Kardinalität einer maximalen stabilen Menge in $G$, $P_S(G)$ das zu $G$ gehörige Stable-Set-Polytop und $P(G)$ eine Relaxation von $P_S(G)$, d.h. $P_S(G)\subset P(G)\subset [0,1]^n$. Der geometrische Rank $g$ von $P(G)$ ist definiert als das kleinste $p$, so daß $\max \{\Vert x\Vert _p: x\in P(G)\}$ an einer ganzzahligen Ecke angenommen wird und somit $\alpha^{1/p}$ entspricht.

Es gilt $1\leq g(P(G)) \leq \infty$, wobei $g(P(G)) \leq \infty$ trivial aus $P(G)\subset [0,1]^n$ folgt und $g(P(G))=1$ bedeutet, daß $\alpha$ mit linearer Optimierung über $P(G)$ berechnet werden kann.

Für beliebiges $k\in N$ gibt es Relaxationen, deren geometrischer Rank nach oben durch $1+\log (n/k)$ beschränkt und für die das Separationsproblem in polynomieller Zeit gelöst werden kann. Andererseits ist unter der Annahme $NP\neq ZPP$ Separation für Relaxationen mit endlichem geometrischen Rank (also unabhängig von der jeweiligen Knotenzahl $n$) nicht in polynomieller Zeit möglich.

E-Mail:	brieden@ma.tum.de
Homepage:	www-m9.ma.tum.de/~brieden/

Zeitplan der Sektion   Tagesübersicht   Liste der Vortragenden