Please use this identifier to cite or link to this item:
Full metadata record
DC FieldValueLanguage
dc.contributor.advisorShen, Hongen
dc.contributor.advisorSheng, Michaelen
dc.contributor.advisorMichalewicz, Zbigniewen
dc.contributor.authorLiao, Kewenen
dc.description.abstractNowadays, data storage, server replicas/mirrors, virtual machines, and various kinds of services can all be regarded as different types of resources. These resources play an important role in today’s computer world because of the continuing advances in information technology. It is usual that similar resources are grouped together at the same site, and can then be allocated to geographically distributed clients. This is the resource allocation paradigm considered in this thesis. Optimizing solutions to a variety of problems arising from this paradigm remains a key challenge, since these problems are NP-hard. For all the resource allocation problems studied in this thesis, we are given a set of sites containing facilities as resources, a set of clients to access these facilities, an opening cost for each facility, and a connection cost for each allocation of a facility to a client. The general goal is to decide the number of facilities to open at each site and allocate the open facilities to clients so that the total cost incurred is minimized. This class of the problems extends the classical NP-hard facility location problems with additional abilities to capture various practical resource allocation scenarios. To cope with the NP-hardness of the resource allocation problems, the thesis focuses on the design and analysis of approximation algorithms. The main techniques we adopt are linear programming based, such as primal-dual schema, linear program rounding, and reductions via linear programs. Our developed solutions have great potential for optimizing the performances of many contemporary distributed systems such as cloud computing, content delivery networks, Web caching, and Web services provisioning.en
dc.subjectapproximation algorithms; resource allocation; optimizationen
dc.titleApproximation algorithms for resource allocation optimization.en
dc.contributor.schoolSchool of Computer Scienceen
dc.provenanceThis electronic version is made publicly available by the University of Adelaide in accordance with its open access policy for student theses. Copyright in this thesis remains with the author. This thesis may incorporate third party material which has been used by the author pursuant to Fair Dealing exceptions. If you are the owner of any included third party copyright material you wish to be removed from this electronic version, please complete the take down form located at:
dc.description.dissertationThesis (Ph.D.) -- University of Adelaide, School of Computer Science, 2014en
Appears in Collections:Research Theses

Files in This Item:
File Description SizeFormat 
01front.pdf127.92 kBAdobe PDFView/Open
02whole.pdf925.47 kBAdobe PDFView/Open
  Restricted Access
Library staff access only227.98 kBAdobe PDFView/Open
  Restricted Access
Library staff access only2.67 MBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.