Back to search

University of Waterloo

Submodular Maximization Subject to Information Constraints

Abstract

dc:description.abstract

In general, submodular maximization is relevant in many problems in controls, robotics and machine learning, because it models many computationally difficult problems. A simple greedy strategy can provide strong approximation guarantees for many of these problems. We wish to expand the set of scenarios where submodular maximization can be applied. More specifically, in this thesis we study submodular maximization problems where decision-makers are subject to information constraints. The first type of information constraint we explore is when decision-makers can only partially observe the submodular objective function. This scenario can arise when an objective function is expensive to compute or physical constraints prevent the evaluation of the objective function. We formalize the problem and then show that in general, strong performance cannot be guaranteed. We then present two different greedy strategies that provide strong approximation guarantees when only having limited access to the objective under additional assumptions about the submodular objective. The second information constraint we explore is in the context of distributed submodular maximization. In these scenarios, a team of agents wishes to maximize a submodular objective collaboratively but are constrained to make decisions based on a subset of the other agents' actions. We are interested in what types of functions are challenging for agents to optimize given their information structure. We explore how submodular functions that exhibit worst-case performance can be formulated through a linear program. This approach provides a means to numerically compute worst-case performance bounds as well as functions where a team of agents will exhibit their worst-case performance. Using this technique, we provide theoretical performance bounds based on their information structure that are tighter than the known bounds in the literature.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2022

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Downie, Andrew
Advisor dc:contributor.advisor
  • Smith, Stephen L.

Subjects

dc:subject × 3

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/18141

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Downie, Andrew. Submodular Maximization Subject to Information Constraints. University of Waterloo, 2022. http://hdl.handle.net/10012/18141