Prize-Collecting Network Design

Other Titles
Network design is an active research area in discrete optimization that focuses on problems arising from the construction of communication networks. The prize-collecting version of these problems allow some connectivity requirements to be violated in exchange for paying a penalty. In this dissertation, we consider prize-collecting network design problems in two settings, in which inputs for the problem are either known in advance or revealed over time. In the first setting, we give a 3-approximation algorithm for the prizecollecting Steiner forest problem using iterative rounding. In the second setting, we give an O(log n)-competitive algorithm for the constrained forest problem with 0-1 proper connectivity requirement functions using the primal-dual method and extend our algorithm to solve its prize-collecting version. Computational experiments are carried out to compare this online algorithm with the corresponding offline optimal solutions on a set of random generated largescale instances for the special case of the prize-collecting Steiner tree problem. In addition, we study the problem of finding the worst-case integrality gap between the traveling salesman problem and its subtour LP relaxation. We restrict ourselves to the special case in which costs between cities are either one or two. We give a proof of upper bound of 106 81 for this integrality gap. By carrying out computational experiments, we find the worst-case integrality gap to be for small number of cities, n [LESS-THAN OR EQUAL TO] 12. 10 9
Journal / Series
Volume & Issue
Date Issued
Network design; Approximation algorithm; Online algorithm
Effective Date
Expiration Date
Union Local
Number of Workers
Committee Chair
Williamson, David P
Committee Co-Chair
Committee Member
Henderson, Shane G.
Kleinberg, Robert David
Degree Discipline
Operations Research
Degree Name
Ph. D., Operations Research
Degree Level
Doctor of Philosophy
Related Version
Related DOI
Related To
Related Part
Based on Related Item
Has Other Format(s)
Part of Related Item
Related To
Related Publication(s)
Link(s) to Related Publication(s)
Link(s) to Reference(s)
Previously Published As
Government Document
Other Identifiers
Rights URI
dissertation or thesis
Accessibility Feature
Accessibility Hazard
Accessibility Summary
Link(s) to Catalog Record