🚀 go-pugleaf

---------- Forwarded message ----------
Date: Wed, 15 Oct 2008 17:27:53 -0400 (EDT)
From: malekian@cs.umd.edu
To: theory-local@cs.umd.edu
Subject: [Theory-local] CATS talk, thursday october 16th, 11 am, AVW 4185

Time : 11 am
Location: AVW 4185
Date : Thursday October 16th
Speaker: Nitish Korula
Title: Single-Sink Network Design Problems with Vertex-Connectivity
Requirements
Abstract: We study single-sink network design problems in undirected
graphs with vertex connectivity requirements. The input to these problems
is an edge-weighted undirected graph G = (V, E), a sink/root vertex r, a
set of terminals T \subseteq V, and an integer k. The goal is to connect
each terminal t \in T to the root r via k vertex-disjoint paths. In the
connectivity problem, the objective is to find a min-cost subgraph of G
that contains the desired paths. When k=1, this is the well-known Steiner
Tree problem, and there is a 2-approximation for this problem when k \le
2, but for k \ge 3, the first non-trivial approximation was obtained very
recently by Chakraborty, Chuzhoy and Khanna, who describe and analyze an
algorithm with an approximation ratio of k^{O(k^2)} log^4 n. In this
paper,  we show a k^{O(k)} log |T|-approximation bound for a very simple
greedy algorithm. Our analysis is based on the dual of a natural linear
program and is of independent technical interest. We use the insights from
this analysis to obtain simple approximation algorithms for more general
problems in which the cost of an edge depends on the number of terminals
that use it.

Our results show that for each of these problems, simple and natural
algorithms that have been developed for k = 1 have good performance for
small k > 1.


_______________________________________________
Theory-local mailing list
Theory-local@mcfeely.cs.umd.edu
https://mailman.cs.umd.edu/mailman/listinfo/theory-local