Back to search

Cornell University

Prize-Collecting Network Design

Abstract

dc:description.abstract

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

Degree

thesis:*
Name thesis:degree_name
Ph. D., Operations Research
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Operations Research
Grantor
Cornell University
Year dc:date.issued
2012

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Qian, Jiawei
Chair dc:contributor.chair
  • Williamson, David P
Committee members dc:contributor.committeemember
  • Henderson, Shane G.
  • Kleinberg, Robert David

Subjects

dc:subject × 3

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Dc Identifier Bibid
7745231

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Qian, Jiawei. Prize-Collecting Network Design. Doctor of Philosophy thesis, Cornell University, 2012. https://hdl.handle.net/1813/29363