Advanced Network Design Techniques and Problems

Degrees and Network Design: New Problems and Approximations Guy Kortsarz Rutgers University. Joint work with Dinitz and Li

The problems we study Survivable network design: given an edge- weighted graph G and a requirement rij between every pair of vertices i,j find a minimum weights subgraph H so that for every i,j the minimum cut between i and j in H is at least rij Jain gave a ratio 2 approximation

Adding Degree bounds Survivable network design with degree bound: Adding degree bounds in the constraints: a constant bi-criteria approximation is known. Lau et al

Lp SND Consider the Lp norm of the degrees in the solution. Bound the Lp norm by an input parameter B. Under this constraint minimize the cost. The L2 norm for example: low degrees and few edges

Lp SND We generalize the Jain algorithm ratio 2 for the costs. The Lp constraint is violated by 21/p 51-1/p. Using convex programming and some tricks.

The Group Steiner Problem We are given an undirected graph G(V,E,r) with weights on the edges and a collection of groups {Ui } so that Ui V Required: A tree of minimum cost rooted at r that contains at least one vertex of every Ui

Blue, red, green, purple yellow black groups Blue, red, green, purple yellow black groups 10 8 8 8 4 1 7 7 4 6 6 3 3 4 14 2 R

Blue, red, green, purple yellow black groups Blue, red, green, purple yellow black groups 4 1 3 3 1 2 R

Degree bounded Group Steiner on bounded treewidth graphs (O(log2 n),O(log2 n)) bicriteria approximation

The Set Cover Problem The Set Cover problem: choose a minimum weight collection of stars that covers X X Y c=8 c=5 c=4 c=7 c=9

A Set Cover of weight 9. X Y w=5 w=4

The Group Steiner Problem on trees Set Cover and the sets are leaves of a tree with weights 3 3 2 10 1 1 1 1 1 1 1

Choosing a Set Cover of size 5 is better than choosing a Set Cover of size 1. 3 3 2 1 1 1 1 1

Approximating GS on general graphs A paper by FRT: reduce any metric into a (random) tree so that expected weights do not shrink and can increase by O(log n). Garg, Konjevod, Ravi an O((log n)2) approximation on trees

LP for trees Min ec(e)w(e) c(e) are fractional capacities. Any cut that separates a group gi and the root r must have a capacity of at least 1

Approximating GS on trees Let p(e) be the parent edge of e. Add e to the solution with probability c(e)/c(p(e)). Discard edges that have no path to the root.

When is an edge c1 chosen? r c4 c3 c2 c1

c2,c3,c4 must be chosen as well r c4 c3 c2 c1

Probability that c1 is chosen is (c1/c2) (c2/c3) (c3/c4) c4 =c1 r c4 c3 c2 c1

The expected cost is the fractional weight ec(e)w(e)

Every group is covered w.p at least 1/O(log N) with N the largest group size. Thus O(log N log k) rounds suffice to cover all groups with high probability. For general graphs O(log N log k log n) because the FRT gives log n loss.

Hardness of approximation Hardness of approximation Halperin, Krauthgamer: (log 2- n) hardness on trees. It almost matched the upper bound. Next, Group Steiner on trees with the addition of degree bounds on vertices. Bounding the degree is Set Cover hard.

A tight algorithm. A tight algorithm. X. Guo, G. Kortsarz, B Laekhanukit, S. Li D. Vaz J. Xian (O(log2 n), O(log n) ) ratio, polynomial time for GST on trees with degree bounds Complex.

Next step: bounded treewidth graphs These are essentially graphs so that every induced subgraph has a constant size separator. Next step: bounded treewidth graphs Many problems that are polynomial on a tree via Dynamic programming, are also polynomial on Bounded treewidth graphs. Using the bag representation

Bag representation Bag representation G=(V,E) a T=(VT, ET) h g a g h b b a b c a c f a g f g h f f c c d e c d e t Xt = {d,e,c} e d The bags with a given vertex v are a subtree

A very general method A very general method We may assume that the optimum tree is a Binary tree hence has a vertex separator. This gives a decomposition of the optimum We wish to have a state tree of all decompositions But this requires too much information Therefore, we maintain only the portal (separating vertices) information.

This method was used to get This method was used to get O(log^2 n/loglog n) approximation for the Directed Steiner tree problem in quasi- polynomial time (tight for quasi-polynomial algorithms) The Directed Steiner Tree problem with Degree Bound. Polylogarithmic approximation in quasi- polynomial times.

Why is it better in BTW graphs? Why is it better in BTW graphs? In Bounded Treewidth graphs we don t need to keep the information about the degrees in the state trees. It can be handled by linear programming. This allows a polynomial-size state tree. The rounding is similar to GKR rounding but much more complex analysis.

Open problems Open problems What is the best approximation for general graphs? Nothing is known for polynomial time. Is it possible to reduce the degree ratio on bounded treewidth graphs to O(log n)? What is the best ratio for the Directed Steiner tree problem with degree bounds? Group Steiner is a special case of the Directed Steiner problem.

Open problems Open problems Group Steiner with low costs and low Lp norm?