We study budgeted variants of classical cut problems: the Multiway Cut problem, the Multicut problem, and the k-Cut problem, and provide approximation algorithms for these problems. Specifically, for the budgeted multiway cut and the k-cut problems we provide constant factor approximation algorithms. We show that the budgeted multicut problem is at least as hard to approximate as the sparsest cut problem, and we provide a bi-criteria approximation algorithm for it.
Cut problems in graphs with a budget constraint / Engelberg, R; Koenemann, J; Leonardi, Stefano; Naor, J.. - In: JOURNAL OF DISCRETE ALGORITHMS. - ISSN 1570-8667. - 5(2):(2007), pp. 262-279. [10.1016/j.jda.2006.05.002]
Cut problems in graphs with a budget constraint
LEONARDI, Stefano;
2007
Abstract
We study budgeted variants of classical cut problems: the Multiway Cut problem, the Multicut problem, and the k-Cut problem, and provide approximation algorithms for these problems. Specifically, for the budgeted multiway cut and the k-cut problems we provide constant factor approximation algorithms. We show that the budgeted multicut problem is at least as hard to approximate as the sparsest cut problem, and we provide a bi-criteria approximation algorithm for it.| File | Dimensione | Formato | |
|---|---|---|---|
|
VE_2007_11573-103828.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
248.14 kB
Formato
Adobe PDF
|
248.14 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
