Combinatorial optimization and decision-making with applications in Computational Sustainability
Loading...
No Access Until
Permanent Link(s)
Collections
Other Titles
Authors
Abstract
Combinatorial optimization and decision-making problems are critical in many real-world computational sustainability problems. The main goals for these projects are often to provide decision-support tools for various groups and institutions to help solve complex computation problems encountered in sustainable planning and development. This thesis mainly focuses on two real-world applications of combinatorial optimization and decision-making in computational sustainability. The first is a multiobjective optimization problem inspired by the real-world problem of placing hydropower dams in the Amazon basin. We propose a fully polynomial-time approximation scheme based on Dynamic Programming (DP) for computing the Pareto frontier within an arbitrarily small error margin on tree-structured networks. We also developed a complementary mixed integer programming (MIP) approach for approximating the Pareto frontier and methods for approximating high-dimensional Pareto frontiers. The second is an online matching problem coordinating citizen scientists for invasive species survey efforts. We developed a learning-augmented matching algorithm that can utilize partial information and provides good performance and approximation guarantees. For both applications, we provide not only practical solutions to real-world problems but also novel computational algorithms and techniques.
Journal / Series
Volume & Issue
Description
133 pages
Sponsorship
Date Issued
2022-08
Publisher
Keywords
Approximation Algorithm; Combinatorial Optimization; Computational Sustainability; Hydropower; Multiobjective Optimization
Location
Effective Date
Expiration Date
Sector
Employer
Union
Union Local
NAICS
Number of Workers
Committee Chair
Gomes, Carla P.
Committee Co-Chair
Committee Member
Bindel, David S.
Davis, Damek Shea
Davis, Damek Shea
Degree Discipline
Applied Mathematics
Degree Name
Ph. D., Applied Mathematics
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)
References
Link(s) to Reference(s)
Previously Published As
Government Document
ISBN
ISMN
ISSN
Other Identifiers
Rights
Attribution 4.0 International
Rights URI
Types
dissertation or thesis