PhD Proposal: Approximation Algorithms for Novel Scheduling Problems

Resource allocation and job scheduling are among the most fundamental problems in Computer Science. Broadly, resource allocation refers to the process of assigning scarce resources to different competing tasks while optimizing certain performance criteria. In this proposal, we identify several novel resource allocation problems that arise in the context of scheduling jobs in datacenters.
The first scenario that we consider is the presence of soft precedence constraints between jobs. Traditionally, algorithm designers consider precedence constraints between jobs to be sacrosanct and design algorithms that generate schedules that satisfy all constraints while optimizing different performance criteria (such as average completion time or makespan). However for many applications such as in internet telephony and project scheduling, some precedence constraints are "soft", i.e., they are allowed to be violated at a certain cost especially if the violation leads to a much better schedule. We formalize different variants of job scheduling with soft precedence constraints and conduct the first systematic study of these problems. Since most of the problems we consider are NP-complete, we focus on finding good approximation algorithms.
The second problem that we consider concerns the placement of middleboxes such as firewalls in a datacenter. In the 'Infrastructure as a Service' paradigm of cloud computing, clients run autonomous virtual machines (VMs) on servers hosted by the cloud service provider. Much of the traffic between these VMs needs to be routed through a firewall for security reasons. This scenario motivates the formulation of the Firewall Placement problem that seeks to minimize the number of firewalls necessary subject to a bound on the maximum congestion in the network. For the general capacitated firewall placement problem, we design an efficient algorithm that guarantees the optimal number of firewalls but violates congestion by a factor of two.
Examining Committee:
Committee Chair: Dr. Samir Khuller
Dept's Representative Dr. V.S. Subrahmanian
Committee Member(s): Dr. Mohammad Taghi Hajiaghayi
Dr. William Gasarch