Back to results

West Virginia University

An Empirical Analysis of Approximation Algorithms for the Unweighted Tree Augmentation Problem

Abstract

dc:description.abstract

In this thesis, we perform an experimental study of approximation algorithms for the tree augmentation problem (TAP). TAP is a fundamental problem in network design. The goal of TAP is to add the minimum number of edges from a given edge set to a tree so that it becomes 2-edge connected. Formally, given a tree T = (V, E), where V denotes the set of vertices and E denotes the set of edges in the tree, and a set of edges (or links) L ⊆ V × V disjoint from E, the objective is to find a set of edges to add to the tree F ⊆ L such that the augmented tree (V, E ∪ F) is 2-edge connected. Our goal is to establish a baseline performance for each approximation algorithm on actual instances rather than worst-case instances. In particular, we are interested in whether the algorithms rank on practical instances is consistent with their worst-case guarantee rankings. We are also interested in whether preprocessing times, implementation difficulties, and running times justify the use of an algorithm in practice. We profiled and analyzed five approximation algorithms, viz., the Frederickson algorithm, the Nagamochi algorithm, the Even algorithm, the Adjiashivili algorithm, and the Grandoni algorithm. Additionally, we used an integer program and a simple randomized algorithm as benchmarks. The performance of each algorithm was measured using space, time, and quality comparison metrics. We found that the simple randomized is competitive with the approximation algorithms and that the algorithms rank according to their theoretical guarantees. The randomized algorithm is simpler to implement and understand. Furthermore, the randomized algorithm runs faster and uses less space than any of the more sophisticated approximation algorithms.

Degree

thesis:*
Name thesis:degree_name
MS
Level thesis:degree_level
Thesis
Discipline thesis:degree_discipline
Not Listed

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Restanio, Jacob Thomas
Contributors dc:contributor
  • Krishnamurthy Subramani
  • Donald Adjeroh
  • Piotr Wojciechowski

Subjects

dc:subject × 3

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
West Virginia University
Base URL
researchrepository.wvu.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Restanio, Jacob Thomas. An Empirical Analysis of Approximation Algorithms for the Unweighted Tree Augmentation Problem. Thesis thesis, https://doi.org/10.33915/etd.12089