Cut problems in graphs with a budget constraint

被引：11

作者：

Engelberg, Roee ^{[1
]}

Koenemann, Jochen ^{[2
]}

Leonardi, Stefano ^{[3
]}

Naor, Joseph ^{[1
]}

机构：

[1] Technion, Comp Sci Dept, IL-32000 Haifa, Israel

[2] Univ Waterloo, Dept Combinator & Optimizat, Waterloo, ON N2L 3G1, Canada

[3] Univ Roma La Sapienza, Dipartimento Informat & Sistemist, I-00198 Rome, Italy

来源：

JOURNAL OF DISCRETE ALGORITHMS | 2007年 / 5卷 / 02期

关键词：

Approximation algorithms; Budget problems; Graph theory; Cut problems; Combinatorial optimization;

D O I：

10.1016/j.jda.2006.05.002

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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. (C) 2006 Elsevier B.V. All rights reserved.

引用

页码：262 / 279

页数：18

共 23 条

[1]

Arora S., 2004, P 36 ANN ACM S THEOR, P222

[2] An O(log k) approximate min-cut max-flow theorem and approximation algorithm [J].