The Library
Approximation algorithms for geometric, caching and scheduling problems
Tools
Adamaszek, Anna (2012) Approximation algorithms for geometric, caching and scheduling problems. PhD thesis, University of Warwick.
Full text not available from this repository, contact author.
Official URL: http://webcat.warwick.ac.uk/record=b2585179~S1
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 quasipolynomial 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 minimumlength 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 quasipolynomial 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.
Item Type:  Thesis or Dissertation (PhD)  

Subjects:  Q Science > QA Mathematics  
Library of Congress Subject Headings (LCSH):  Approximation algorithms, Mathematical optimization, Online algorithms, Vehicle routing problem, Cache memory  Mathematical models, Buffer storage (Computer science)  Mathematical models, System analysis  
Official Date:  May 2012  
Dates: 


Institution:  University of Warwick  
Theses Department:  Department of Computer Science  
Thesis Type:  PhD  
Publication Status:  Unpublished  
Supervisor(s)/Advisor:  Czumaj, Artur  
Sponsors:  University of Warwick. Centre for Discrete Mathematics and its Applications ; Engineering and Physical Sciences Research Council (EPSRC) (EP/D063191/1)  
Extent:  vi, 151 leaves : illustrations  
Language:  eng 
Request changes or add full text files to a record
Repository staff actions (login required)
View Item 