Approximation algorithms for geometric, caching and scheduling problems

Preview

PDF WRAP_Theses_Adamaszek_2012.pdf - Submitted Version - Requires a PDF viewer. Download (5MB) | Preview

Request Changes to record.

Abstract

In this thesis we study approximation algorithms for optimization problems, which is one of the core areas of modern theoretical computer science. We focus on two areas of approximation. First we consider geometric problems, and we present approximation algorithms for the capacitated location routing problem and the capacitated network design problem in the Euclidean plane. Next, we investigate two well known caching and scheduling problems, the generalized caching problem and the reordering buffer management problem. We do this in an online setting, i.e. when instead of getting the whole input data at once, the data arrives in parts,, during the execution of the algorithm.

In the capacitated location routing problem a fleet of vehicles with bounded capacity must serve a set of customers. The goal is to choose the depots for the vehicles from a set of possible locations, and fix the routes of the vehicles, to minimize the cost of opening the depots and the length of the routes. We present a quasi-polynomial time approximation scheme for the problem, and a polynomial time approximation scheme for some range of input parameters.

In the capacitated geometric network design problem we are given two sets of points in the plane, sources and sinks, where each source wants to send and each sink wants to receive a given amount of flow. The goal is to construct a minimum-length network with bounded edge capacity that allows to route the requested flow from sources to sinks. In addition to the sources and sinks, any other points in the plane can be used as vertices of the network. We present a quasi-polynomial time approximation scheme for the problem, and a polynomial time approximation scheme when the edge capacity is not too large.

The generalized caching problem is a classical problem in the area of online algorithms. We are given a set of pages, each page with an arbitrary size and fetching cost, and a cache of bounded size. At each time step a specific page is requested. If the page is not in the cache, it must be fetched into the cache, possibly evicting some other pages. The goal is to design an algorithm that specifies which pages to evict from the cache, minimizing the total cost incurred on the request sequence. We give a randomized online algorithm for the generalized caching problem which is asymptotically optimal, solving a long standing open problem.

The reordering buffer management problem is also a well known problem in the area of online algorithms. A stream of colored items arrives at a service station equipped with a reordering buffer of a given capacity. The cost of servicing the items depends on the processing order: servicing an item, when the previous item had a different color, incurs a context switching cost depending on the color of the current item. A scheduling strategy has to decide which item to service next, to minimize the cost of the output sequence. We show lower bounds on the competitive ratio of a deterministic and randomized online algorithm, and a deterministic online algorithm which nearly matches the lower bound.

Request changes or add full text files to a record

Repository staff actions (login required)

View Item