Adaptive Approximation Algorithms for Ranking, Routing and Classification

Abstract

This dissertation aims to consider different problems in the area of stochastic optimization, where we are provided with more information about the instantiation of the stochastic parameters over time. With uncertainty being an inseparable part of every industry, several applications can be modeled as discussed. In this dissertation we focus on three main areas of applications: 1) ranking problems, which can be helpful for modeling product ranking, designing recommender systems, etc., 2) routing problems which can cover applications in delivery, transportation and networking, and 3) classification problems with possible applications in medical diagnosis and chemical identification. We consider three types of solutions for these problems based on how we want to deal with the observed information: static, adaptive and a priori solutions. In Chapter II, we study two general stochastic submodular optimization problems that we call Adaptive Submodular Ranking and Adaptive Submodular Routing. In the ranking version, we want to provide an adaptive sequence of weighted elements to cover a random submodular function with minimum expected cost. In the routing version, we want to provide an adaptive path of vertices to cover a random scenario with minimum expected length. We provide (poly)logarithmic approximation algorithms for these problems that (nearly) match or improve the best-known results for various special cases. We also implemented different variations of the ranking algorithm and observed that it outperforms other practical algorithms on real-world and synthetic data sets. In Chapter III, we consider the Optimal Decision Tree problem: an identification task that is widely used in active learning. We study this problem in presence of noise, where we want to perform a sequence of tests with possible noisy outcomes to identify a random hypothesis. We give different static (non-adaptive) and adaptive algorithms for this task with almost logarithmic approximation ratios. We also implemented our algorithms on real-world and synthetic data sets and compared our results with an information theoretic lower bound to show that in practice, our algorithms' value is very close to this lower bound. In Chapter IV, we focus on a stochastic vehicle routing problem called a priori traveling repairman, where we are given a metric and probabilities of each vertices being active. We want to provide an a priori master tour originating from the root that is shortcut later over the observed active vertices. Our objective is to minimize the expected total wait time of active vertices, where the wait time of a vertex is defined as the length of the path from the root to this vertex. We consider two benchmarks to evaluate the performance of an algorithm for this problem: optimal a priori solution and the re-optimization solution. We provide two algorithms to compare with each of these benchmarks that have constant and logarithmic approximation ratios respectively.