Computer Science – Data Structures and Algorithms
Scientific paper
2008-10-03
Computer Science
Data Structures and Algorithms
The conference version of this paper is to appear at SODA 2009. This is the full version
Scientific paper
We consider the following "multiway cut packing" problem in undirected graphs: we are given a graph G=(V,E) and k commodities, each corresponding to a set of terminals located at different vertices in the graph; our goal is to produce a collection of cuts {E_1,...,E_k} such that E_i is a multiway cut for commodity i and the maximum load on any edge is minimized. The load on an edge is defined to be the number of cuts in the solution crossing the edge. In the capacitated version of the problem the goal is to minimize the maximum relative load on any edge--the ratio of the edge's load to its capacity. Multiway cut packing arises in the context of graph labeling problems where we are given a partial labeling of a set of items and a neighborhood structure over them, and, informally, the goal is to complete the labeling in the most consistent way. This problem was introduced by Rabani, Schulman, and Swamy (SODA'08), who developed an O(log n/log log n) approximation for it in general graphs, as well as an improved O(log^2 k) approximation in trees. Here n is the number of nodes in the graph. We present the first constant factor approximation for this problem in arbitrary undirected graphs. Our approach is based on the observation that every instance of the problem admits a near-optimal laminar solution (that is, one in which no pair of cuts cross each other).
Barman Siddharth
Chawla Shuchi
No associations
LandOfFree
Packing multiway cuts in capacitated graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Packing multiway cuts in capacitated graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Packing multiway cuts in capacitated graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-410120