Search
Skip to Search Results-
Fall 2020
Scheduling problems are problems to assign jobs to machines at particular times while trying to optimize some objective function. In this work, we study one such problem, called Generalized Path Scheduling (GPS) problem, in which the machines form a path and each job is assigned a subpath of...
-
Fall 2016
In this thesis, we present approximation algorithms for various NP-hard vehicle routing problems, as well as for a related maximum group coverage problem. Our main contribution is a framework to build good constant-factor approximation algorithms for variants of the multi-depot $k$-travelling...
-
Fall 2015
In this thesis, we consider two closely related clustering problems, Min Sum k-Clustering (MSkC) and Balanced k-Median (BkM). In Min Sum k-clustering, one is given a graph and a parameter k, and has to partition the vertices in the graph into k clusters to minimize the sum of pairwise distances...
-
Approximation Algorithms for Multi-processor Task Scheduling Problems on Identical Parallel Processors
DownloadFall 2013
In this thesis we present approximation algorithms for some multi-processor task scheduling problems. In a scheduling problem, there is a set of processors P that can be used to process a set of tasks T and the goal is to find a feasible scheduling of the tasks on the processors, while optimizing...
-
Fall 2013
In this thesis, we consider min-max vehicle routing problems, specifically min-max tour cover and star cover problems. Given a metric (V,c) and a number k, a set of tours (respectively stars) in G is called a k-tour cover (respectively k-star cover), if they cover all the vertices of G. In the...
-
Fall 2011
In this thesis, we present a variety of approximation algorithms for the Unsplittable Flow on Paths problem and some Traveling Salesman problems. The main contribution to the Unsplittable Flow on Paths problem is a logarithmic approximation algorithm which is the first non-trivial approximation...