The Probabilistic Set-Covering Problem

Noah Weninger

Abstract

This week we revisit the stochastic orienteering problem in which we are given a metric graph where each node has a deterministic reward and a random size. The goal is to adaptively decide on which nodes to visit to maximize the expected reward, while not exceeding the budget B on the distance plus the size of jobs processed. We will discuss a non-adaptive approximation algorithm for this problem which was presented in a paper by Gupta, Krishnaswamy, Nagarajan, and Ravi. If time permits, we will examine its performance relative to the best adaptive policy.

Date
Oct 21, 2022 12:00 PM
Location
MC6029 or Zoom