Vi anser Steiner K-cut problem som generaliserar både k-cut problem och multiway cut problem. Steiner k-cut-problemet definieras enligt följande. Med tanke på en kantviktad oriktad graf G = (V, E), en undergrupp av hörn X  på V som kallas terminaler, och ett heltal k ≤  på X, är målet att hitta en minsta vikt uppsättning kanter vars borttagning resulterar i k frånkopplade komponenter, som var och en innehåller minst en terminal. Vi ger två approximationsalgoritmer för problemet: en girig (2 − 2 k ) - approximation baserad på Gomory-Hu träd, och en (2‐ 2  på X) - approximation baserad på LP avrundning. Vi använder insikten från avrundningen för att utveckla en exakt biriktad formulering för det globala minimala skärproblemet (k-cut-problemet med k = 2).
Det bästa resultatet känt för detta problem är en 2 − 2 / k approximationsalgoritm på grund av Chekuri et al. Hoppa över det.
The Steiner k-Cut Problem ∗
{'venue': 'ICALP', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}