Cut problems in graphs with a budget constraint |
| |
| Authors: | Roee Engelberg Jochen Knemann Stefano Leonardi Joseph Naor |
| |
| Institution: | aComputer Science Department, Technion, Haifa 32000, Israel;bDepartment of Combinatorics and Optimization, University of Waterloo, 200 University Avenue West, Waterloo, ON N2L 3G1, Canada;cDipartimento di Informatica e Sistemistica, Università di Roma “La Sapienza”, Via Salaria 113, 00198 Roma, Italy |
| |
| 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. |
| |
| Keywords: | Approximation algorithms Budget problems Graph theory Cut problems Combinatorial optimization |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
