-
Notifications
You must be signed in to change notification settings - Fork 0
/
proposal.html
executable file
·10 lines (9 loc) · 1.19 KB
/
proposal.html
1
2
3
4
5
6
7
8
9
<html>
<title>Thesis Proposal</title>
<body>
<h3>Approximation Techniques for Stochastic Optimization Problems</h3>
<br>
Abstract:
The focus of this thesis is on the design and analysis of algorithms for Stochastic Optimization problems, i.e., those where there is some form of uncertainty in the input. More specifically, we consider designing approximation algorithms for Stochastic Optimization problems in the fields of Network Design and Scheduling.
The exact problems we study in this thesis are the following: (a) the Survivable Network Design problem with a random collection of input terminals, (b) the Stochastic Knapsack problem with random sizes/rewards for jobs, (c) the Multi-Armed Bandits problem, where the individual Markov Chains make random transitions, and finally (d) the Stochastic Orienteering problem, where the tasks at each node have random processing times. We explore different techniques for solving these problems and present algorithms for all the above problems with near-optimal approximation guarantees. We also believe that the techniques are fairly general and have wider applicability than the context in which they are used in this thesis.
<br><br> <a href = "proposal.pdf">[PDF]</a>