Ph.D Thesis | |

Ph.D Student | Freund Ari |
---|---|

Subject | On-Line and Off-Line Approximation Algorithms for Various Resource Allocation and Scheduling Problems and for the Multiway Cut Problem |

Department | Department 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-dua*l 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
cu*t 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.