Cut Problems in Graphs with a Budget Constraint | Zendy

Roee Engelberg | Zendy; Jochen Könemann | Zendy; Stefano Leonardi | Zendy; Joseph Naor | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Cut Problems in Graphs with a Budget Constraint

Author(s) -

Roee Engelberg,

Jochen Könemann,

Stefano Leonardi,

Joseph Naor

Publication year - 2006

Publication title -

lecture notes in computer science

Language(s) - English

Resource type - Book series

SCImago Journal Rank - 0.249

H-Index - 400

eISSN - 1611-3349

pISSN - 0302-9743

DOI - 10.1007/11682462_41

Subject(s) - approximation algorithm , maximum cut , constraint (computer aided design) , computer science , mathematical optimization , constant (computer programming) , budget constraint , algorithm , mathematics , theoretical computer science , graph , geometry , neoclassical economics , economics , programming language

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research