We study budgeted variants of classical cut problems: the Multiway Cut problem, the Multicut problem, and the k-Cut problem, arid 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. © Springer-Verlag Berlin Heidelberg 2006.
Cut problems in graphs with a budget constraint / Roee, Engelberg; Jochen, Koenemann; Leonardi, Stefano; Joseph, Naor. - 3887 LNCS:(2006), pp. 435-446. (Intervento presentato al convegno LATIN 2006 tenutosi a Valdivia; Chile nel March 2006) [10.1007/11682462_41].
Cut problems in graphs with a budget constraint
LEONARDI, Stefano;
2006
Abstract
We study budgeted variants of classical cut problems: the Multiway Cut problem, the Multicut problem, and the k-Cut problem, arid 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. © Springer-Verlag Berlin Heidelberg 2006.| File | Dimensione | Formato | |
|---|---|---|---|
|
VE_2006_11573-60797.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
344.21 kB
Formato
Adobe PDF
|
344.21 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
