## Decomposition-based methods for Connectivity Augmentation Problems

dc.contributor.author | Neogi, Rian | |

dc.date.accessioned | 2021-09-03 15:59:26 (GMT) | |

dc.date.available | 2021-09-03 15:59:26 (GMT) | |

dc.date.issued | 2021-09-03 | |

dc.date.submitted | 2021-08-31 | |

dc.identifier.uri | http://hdl.handle.net/10012/17338 | |

dc.description.abstract | In this thesis, we study approximation algorithms for Connectivity Augmentation and related problems. In the Connectivity Augmentation problem, one is given a base graph G=(V,E) that is k-edge-connected, and an additional set of edges $L \subseteq V\times V$ that we refer to as links. The task is to find a minimum cost subset of links $F \subseteq L$ such that adding F to G makes the graph (k+1)-edge-connected. We first study a special case when k=1, which is equivalent to the Tree Augmentation problem. We present a breakthrough result by Adjiashvili that gives an approximation algorithm for Tree Augmentation with approximation guarantee below 2, under the assumption that the cost of every link $\ell \in L$ is bounded by a constant. The algorithm is based on an elegant decomposition based method and uses a novel linear programming relaxation called the $\gamma $-bundle LP. We then present a subsequent result by Fiorini, Gross, Konemann and Sanita who give a $3/2+\epsilon$ approximation algorithm for the same problem. This result uses what are known as Chvatal-Gomory cuts to strengthen the linear programming relaxation used by Adjiashvili, and uses results from the theory of binet matrices to give an improved algorithm that is able to attain a significantly better approximation ratio. Next, we look at the special case when k=2. This case is equivalent to what is known as the Cactus Augmentation problem. A recent result by Cecchetto, Traub and Zenklusen give a 1.393-approximation algorithm for this problem using the same decomposition based algorithmic framework given by Adjiashvili. We present a slightly weaker result that uses the same ideas and obtains a $3/2+\epsilon $ approximation ratio for the Cactus Augmentation problem. Next, we take a look at the integrality ratio of the natural linear programming relaxation for Tree Augmentation, and present a result by Nutov that bounds this integrality gap by 28/15. Finally, we study the related Forest Augmentation problem that is a generalization of Tree Augmentation. There is no approximation algorithm for Forest Augmentation known that obtains an approximation ratio below 2. We show that we can obtain a 29/15-approximation algorithm for Forest Augmentation under the assumption that the LP solution is half-integral via a reduction to Tree Augmentation. We also study the structure of extreme points of the natural linear programming relaxation for Forest Augmentation and prove several properties that these extreme points satisfy. | en |

dc.language.iso | en | en |

dc.publisher | University of Waterloo | en |

dc.subject | Approximation Algorithms | en |

dc.subject | Combinatorial Optimization | en |

dc.subject | Connectivity Augmentation | en |

dc.title | Decomposition-based methods for Connectivity Augmentation Problems | en |

dc.type | Master Thesis | en |

dc.pending | false | |

uws-etd.degree.department | Combinatorics and Optimization | en |

uws-etd.degree.discipline | Combinatorics and Optimization | en |

uws-etd.degree.grantor | University of Waterloo | en |

uws-etd.degree | Master of Mathematics | en |

uws-etd.embargo.terms | 0 | en |

uws.contributor.advisor | Cheriyan, Joseph | |

uws.contributor.affiliation1 | Faculty of Mathematics | en |

uws.published.city | Waterloo | en |

uws.published.country | Canada | en |

uws.published.province | Ontario | en |

uws.typeOfResource | Text | en |

uws.peerReviewStatus | Unreviewed | en |

uws.scholarLevel | Graduate | en |