AF: Small: Approximation Algorithms for Network Design

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

Fundamental problems in network design have served as benchmarks for the development of new techniques and evaluating their effectiveness in combinatorial optimization. This proposal will investigate a class of connectivity problems including the traveling salesperson problem and its closely related variants such as the bridge connectivity augmentation problem, two-edge-connected subgraph problem and vertex connectivity network design problems, in order to design improved approximation algorithms by advancing current techniques and developing new methods. The proposal also develops new theoretical models for network design problems from practice that incorporate sub-additive demands in information aggregation, and that integrate inventory storage and vehicle routing costs in logistics planning. Due to the ubiquity of their applications, and the fundamental nature of their theory, network design problems are important both in practice and theory. New methods developed can be incorporated into practical heuristic approaches for solving prototypically hard optimization problems of real-life scale that arise in a host of applications from communications to logistics networks. The theoretical analysis developed will improve the mathematically provable quality of fast heuristic solutions for this important class of computational optimization problems.