Back to search

Cornell University

Approximation Algorithms For Stochastic Combinatorial Optimization, With Applications In Sustainability

Abstract

dc:description.abstract

As 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 × 7

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Dc Identifier Bibid
8251279

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

Spencer, Gwen. Approximation Algorithms For Stochastic Combinatorial Optimization, With Applications In Sustainability. Doctor of Philosophy thesis, Cornell University, 2012. https://hdl.handle.net/1813/31423