Show simple item record

dc.contributor.authorQian, Jiaweien_US
dc.identifier.otherbibid: 7745231
dc.description.abstractNetwork 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 9en_US
dc.subjectNetwork designen_US
dc.subjectApproximation algorithmen_US
dc.subjectOnline algorithmen_US
dc.titlePrize-Collecting Network Designen_US
dc.typedissertation or thesisen_US Research Universityen_US of Philosophy D., Operations Research
dc.contributor.chairWilliamson, David Pen_US
dc.contributor.committeeMemberHenderson, Shane G.en_US
dc.contributor.committeeMemberKleinberg, Robert Daviden_US

Files in this item


This item appears in the following Collection(s)

Show simple item record