An improved approximation algorithm for requirement cut

Anupam Gupta; Viswanath Nagarajan; R. Ravi

doi:10.1016/j.orl.2010.02.009

An improved approximation algorithm for requirement cut

Anupam Gupta, Viswanath Nagarajan, R. Ravi

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

This note presents improved approximation guarantees for the requirement cut problem: given an n-vertex edge-weighted graph G=(V,E), and g groups of vertices X₁,...,X_g ⊆ V with each group Xi having a requirement ri between 0 and |X_i|, the goal is to find a minimum cost set of edges whose removal separates each group Xi into at least ri disconnected components. We give a tight Θ(logg) approximation ratio for this problem when the underlying graph is a tree, and show how this implies an O(logk·logg) approximation ratio for general graphs, where k=|∪^g_i=1=1gX_i|≤n.

Original language	English (US)
Pages (from-to)	322-325
Number of pages	4
Journal	Operations Research Letters
Volume	38
Issue number	4
DOIs	https://doi.org/10.1016/j.orl.2010.02.009
State	Published - Jul 2010

Keywords

Approximation algorithms
Graph partitioning

ASJC Scopus subject areas

Software
Management Science and Operations Research
Industrial and Manufacturing Engineering
Applied Mathematics

Access to Document

10.1016/j.orl.2010.02.009

Cite this

@article{7e10b53c4f1e42adb721b0a7891b779e,

title = "An improved approximation algorithm for requirement cut",

abstract = "This note presents improved approximation guarantees for the requirement cut problem: given an n-vertex edge-weighted graph G=(V,E), and g groups of vertices X1,...,Xg ⊆ V with each group Xi having a requirement ri between 0 and |Xi|, the goal is to find a minimum cost set of edges whose removal separates each group Xi into at least ri disconnected components. We give a tight Θ(logg) approximation ratio for this problem when the underlying graph is a tree, and show how this implies an O(logk·logg) approximation ratio for general graphs, where k=|∪gi=1=1gXi|≤n.",

keywords = "Approximation algorithms, Graph partitioning",

author = "Anupam Gupta and Viswanath Nagarajan and R. Ravi",

year = "2010",

month = jul,

doi = "10.1016/j.orl.2010.02.009",

language = "English (US)",

volume = "38",

pages = "322--325",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier",

number = "4",

}

TY - JOUR

T1 - An improved approximation algorithm for requirement cut

AU - Gupta, Anupam

AU - Nagarajan, Viswanath

AU - Ravi, R.

PY - 2010/7

Y1 - 2010/7

N2 - This note presents improved approximation guarantees for the requirement cut problem: given an n-vertex edge-weighted graph G=(V,E), and g groups of vertices X1,...,Xg ⊆ V with each group Xi having a requirement ri between 0 and |Xi|, the goal is to find a minimum cost set of edges whose removal separates each group Xi into at least ri disconnected components. We give a tight Θ(logg) approximation ratio for this problem when the underlying graph is a tree, and show how this implies an O(logk·logg) approximation ratio for general graphs, where k=|∪gi=1=1gXi|≤n.

AB - This note presents improved approximation guarantees for the requirement cut problem: given an n-vertex edge-weighted graph G=(V,E), and g groups of vertices X1,...,Xg ⊆ V with each group Xi having a requirement ri between 0 and |Xi|, the goal is to find a minimum cost set of edges whose removal separates each group Xi into at least ri disconnected components. We give a tight Θ(logg) approximation ratio for this problem when the underlying graph is a tree, and show how this implies an O(logk·logg) approximation ratio for general graphs, where k=|∪gi=1=1gXi|≤n.

KW - Approximation algorithms

KW - Graph partitioning

UR - http://www.scopus.com/inward/record.url?scp=77955309248&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77955309248&partnerID=8YFLogxK

U2 - 10.1016/j.orl.2010.02.009

DO - 10.1016/j.orl.2010.02.009

M3 - Article

AN - SCOPUS:77955309248

SN - 0167-6377

VL - 38

SP - 322

EP - 325

JO - Operations Research Letters

JF - Operations Research Letters

IS - 4

ER -

An improved approximation algorithm for requirement cut

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this