Approximation Algorithms for Survivable Multicommodity Flow Problems with Applications to Network Design

Multicommodity flow (MF) problems have a wide variety of applications in areas such as VLSI circuit design, network design, etc., and are therefore very well studied. The fractional MF problems are polynomial time solvable while integer versions are NP-complete. However, exact algorithms to solve the fractional MF problems have high computational complexity. Therefore approximation algorithms to solve the fractional MF problems have been explored in the literature to reduce their computational complexity. Using these approximation algorithms and the randomized rounding technique, polynomial time approximation algorithms have been explored in the literature. In the design of high-speed networks, such as optical wavelength division multiplexing (WDM) networks, providing survivability carries great significance. Survivability is the ability of the network to recover from failures. It further increases the complexity of network design and presents network designers with more formidable challenges. In this work we formulate the survivable versions of the MF problems. We build approximation algorithms for the survivable multicommodity flow (SMF) problems based on the framework of the approximation algorithms for the MF problems presented in [1] and [2]. We discuss applications of the SMF problems to solve survivable routing in capacitated networks.

EXPERIMENTAL INVESTIGATION OF FOLDED PLATE GIRDERS AND SLAB JOINTS USED IN MODULAR CONSTRUCTION

The folded plate girder, a newly proposed bridge girder, is investigated through this thesis. The folded plate girder is cold bent out of a single sheet of steel. The cold bending eliminates the costly and inconsistent shop welds found in traditional girders. The folded plate girder is meant for application in short span bridges. The girder was subjected to an equivalent 75 year lifetime loading to investigate the fatigue performance. The rebar detail used in the closure region between adjacent slabs has been investigated in the past by the NCHRP 12-68 project. This thesis will proposes a hooked rebar detail as a cost effective alternative to the previously recommended headed rebar detail. The proposed hooked rebar detail looks to improve upon the headed bar detail by increasing the clear cover, and reducing the cost of fabrication and shipment of the rebar. Six specimens containing closure regions are subjected to both positive and negative moment loading in order to investigate their behavior and failure modes under ultimate load.