Approximation algorithms for network design and partitioning problems
Shuchi Chawla, Siddharth Barman · 2012
We develop new approximation algorithms for three graph-theoretic optimization problems. Two of these problems arise in communication networks and the third comes up in the context of classification and labeling. Below we describe these problems and present an overview of our main results. Information Network Design: We develop a model for information networks with a cost structure that captures savings obtained by redundant-data elimination. This model presents an expressive and algorithmically interesting framework as it allows us to represent information flow and still maintain the tractable nature of classical network-design. We consider two problems within this framework and develop algorithms that achieve logarithmic and constant-factor approximation for them. Multi-Route Cuts: A fundamental problem in combinatorial optimization is to find a low-cost cut which disconnects the underlying graph. A natural generalization of finding small cuts is the multi-route cut problem where the goal is to determine a low-cost set of edges or nodes whose removal reduces the connectivity of the graph to below a certain threshold. This problem arises in the context of reliability of service in networks. We provide the first non-trivial approximations for variants of the problem. When the connectivity thresholds are either two or infinity, we obtain polylogarithmic approximations to cost. For arbitrary thresholds, we develop bicriteria approximation algorithms; in particular, we obtain approximations to cost while ensuring that the connectivity drops below a constant times the threshold. Packing Multiway Cuts: Problems involving classification and labeling of interconnected objects arise in many contexts such as machine learning and computational biology. An important class of labeling problems reduces to packing cuts in a graph where the goal is to determine nearly-disjoint cuts that satisfy containment constraints. We develop constant-factor approximation algorithms for the multiway cut packing problem; where, given a collection of subsets of vertices, the objective is to produce separating cuts (one for each subset) that are as edge disjoint as possible.