Ph.D Thesis

Ph.D StudentFreund Ari
SubjectOn-Line and Off-Line Approximation Algorithms for Various
Resource Allocation and Scheduling Problems and
for the Multiway Cut Problem
DepartmentDepartment of Computer Science
Supervisor PROF. Joseph Naor


We study various resource allocation and scheduling problems and the undirected multiway cut problem.  Our work concentrates on algorithmic aspects of these problems---particularly, on achieving good worst-case approximation results or proving the difficulty of achieving them.

In our work on scheduling problems we study several problems, using various approaches.  Specifically, we consider the following.

·        A family of problems in which we are given a limited, reusable, resource which is to be shared among several activities.  Each activity is characterized by one or more time intervals in which it may be scheduled, the amount of resource it requires, and the profit to be accrued by carrying it out.  The problem is to select and schedule a feasible subset of the activities so as to maximize the total profit accrued.  This framework models problems such as real-time scheduling of jobs on parallel machines, bandwidth allocation for sessions in a communications network, and dynamic storage allocation.  We obtain small constant factor approximation ratios using a unified algorithm based on a new version of the local ratio technique.  The algorithm can be interpreted within the primal-dual schema as well.

·        Scheduling advertisements on a WWW page.  We are given a banner of fixed dimensions and a collection of rectangular advertisements. Several small ads can be displayed side by side simultaneously, provided that they all fit within the banner.  Also, the banner contents can be changed periodically.  Each advertisement is characterized by its size, the number of times it should be displayed within a periodic schedule, and the profit associated with it.  The objective is to select and schedule a maximum profit subset of ads.  We obtain small constant approximation ratios for the general problem and for two special cases by rounding a fractional solution to a knapsack relaxation of the problem.

·        On-line packet switching.  A switch must route packets incoming on n input channels through a single slow output channel.  At each time slot it serves a single input channel, i.e., it transmits one packet from an input channel to the output channel.  The objective is to schedule the service of the various input channels so as to minimize the maximum buffer size needed to avoid data loss.  We study the problem in the on-line setting and obtain logarithmic upper and lower bounds.

In our work on multiway cut we study the integrality gap of the Calinescu-Karloff-Rabani (CKR) relaxation.  We obtain a lower bound of 8/7 (asymptotically) on the integrality gap of the CKR relaxation.  The previous best lower bound was 12/11.  The best upper bound to date is approximately 1.3438.