Cornell University
Approximation Algorithms For Stochastic Combinatorial Optimization, With Applications In Sustainability
Abstract
dc:description.abstractAs ecologists and foresters produce an increasing range of probabilistic data, mathematical techniques that address the fundamental interactions between stochastic events and spatial landscape features have the potential to provide valuable decision support in the sustainable management of natural resources. The heart of this thesis explores two models motivated by pressing environmental issues: limiting the spread of wildfire and invasive species containment. We formulate stochastic spatial models in graphs that capture key tradeoffs, and prove a number of original optimization results. Since even deterministic cases in highly-restricted graph classes are NP-Hard (that is, they can not efficiently be solved to optimality), our studies focus on approximation algorithms that efficiently produce solutions which are provably near-optimal. Our models also represent natural generalizations of ideas in the optimization and computer science literature. In particular, while much recent attention has been devoted to questions about connecting stochastically chosen sets, our applications in sustainable planning suggest extensions of deterministic graphcutting models; we explore novel problems in stochastic disconnection.
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
-
- Spencer, Gwen
- Chair dc:contributor.chair
-
- Shmoys, David B
- Committee members dc:contributor.committeemember
-
- Kleinberg, Robert David
- Williamson, David P
Subjects
dc:subject × 7Rights
- Language dc:language.iso
- en_US
Identifiers
dc:identifier.*- Dc Identifier Bibid
- 8251279