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.
2006
LATIN 2006
Bi-criteria approximation algorithms; Budget constraints; Constant factor approximation
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
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].
File allegati a questo prodotto
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/60797
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 10
  • ???jsp.display-item.citation.isi??? 5
social impact