Vi förbättrar approximationsförhållandet för två optimeringsproblem i plana grafer. För nodviktade Steinerträd, ett klassiskt nätverksoptimeringsproblem, är det bästa möjliga approximationsförhållandet i allmänna grafer (log n), och inget bättre var tidigare känt för planar grafer. Vi ger en konstant-faktor approximation för planar grafer. Vår algoritm generaliserar att tillåta som inmatning någon icke-trivial mindre slutna graf familj, och generaliserar också för att ta itu med andra optimeringsproblem såsom Steiner skog, prissamla Steiner träd, och nätverk-formation spel. Det andra problemet vi tar itu med är grupp Steiner träd: ges en graf med kant vikter och en samling av grupper (undergrupper av noder), hitta en minsta vikt ansluten subgraf som innehåller minst en nod från varje grupp. Det bästa approximationsförhållandet som är känt i allmänna grafer är O(log 3 n) eller O(log 2 n) när värdgrafen är ett träd. Vi får en O(log n polylog n) approximation algoritm för specialfall där grafen är planar inbäddad och varje grupp är uppsättningen av noder på ett ansikte. Vi får samma approximationsgrad för minimiviktsturnén som måste besöka varje grupp.
al REF fick en 6-approximation för det nodeviktade Steiner-skogsproblemet.
Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs
{'venue': 'TALG', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}