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.

Weekly Problems Scales: Instruments for Sexually Abused Youth and Their Nonoffending Parents in Treatment

This study’s purpose was to determine if efficient measures could be created to assess multiple problematic behaviors identified in youth who were sexually abused and in treatment. Because of the lack of easily administered brief instruments that assess multiple domains of interest in this population, complementary parent and child assessment measures were developed. The Weekly Problems Scale–Child Version (WPSC) and the Weekly Problems Scale–Parent Version (WPS-P) were created to monitor the weekly progress of the child and family in treatment and focus specifically on common areas of difficulties in this population. Exploratory factor analysis was conducted to assist in identifying the number of underlying dimensions in the scales. Results indicate that the WPS-C and WPS-P demonstrate adequate internal consistency, temporal stability, and construct validity. The WPS-C and WPSP display significant promise as research and clinical assessment tools for use with youth who are sexually abused and their nonoffending parents in treatment.