Allocation Algorithms for Networks with Scarce Resources

Simple item page
dc.contributor.advisorKhuller, Samiren_US
dc.contributor.authorSarpatwar, Kanthi Kiranen_US
dc.contributor.departmentComputer Scienceen_US
dc.contributor.publisherDigital Repository at the University of Marylanden_US
dc.contributor.publisherUniversity of Maryland (College Park, Md.)en_US
dc.date.accessioned2015-06-25T05:51:09Z
dc.date.available2015-06-25T05:51:09Z
dc.date.issued2015en_US
dc.description.abstractMany fundamental algorithmic techniques have roots in applications to computer networks. We consider several problems that crop up in wireless ad hoc networks, sensor networks, P2P networks, and cluster networks. The common challenge here is to deal with certain bottleneck resources that are crucial for performance of the underlying system. Broadly, we deal with the following issues. Data: The primary goal in resource replication problems is to replicate data objects on server nodes with limited storage capacities, so that the latency of client nodes needing these objects is minimized. Previous work in this area is heuristic and without guarantees. We develop tight (or nearly) approximation algorithms for several problems including basic resource replication - where clients need all objects and server can store at most one object, subset resource replication - where clients require different subsets of objects and servers have limited non-uniform capacity, and related variants. Computational resources: To facilitate packing of jobs needing disparate amounts of computational resources in cluster networks, an important auxiliary problem to solve is that of container selection. The idea is to select a limited number of ``containers'' that represent a given pool of jobs while minimizing ``wastage'' of resources. Subsequently, containers representing jobs can be packed instead of jobs themselves. We study this problem in two settings: continuous - where there are no additional restrictions on chosen containers, and discrete - where we must choose containers from a given set. We show that the continuous variant is NP-hard and admits a polynomial time approximation scheme. Contrastingly, the discrete variant is shown to be NP-hard to approximate. Therefore, we seek bi-approximation algorithms for this case. Energy resources: Wireless ad hoc networks contain nodes with limited battery life and it is crucial to design energy efficient algorithms. We obtain tight approximation (up to constant factors) guarantees for partial and budgeted versions of the connected dominating set problem, which is regarded as a good model for a virtual backbone of a wireless ad hoc network. Further, we will discuss approximation algorithms for some problems involving target monitoring in sensor networks and message propagation in radio networks. We will end with a discussion on future work.en_US
dc.identifierhttps://doi.org/10.13016/M2ZG9K
dc.identifier.urihttp://hdl.handle.net/1903/16519
dc.language.isoenen_US
dc.subject.pqcontrolledComputer scienceen_US
dc.subject.pquncontrolledApproximation Algorithmsen_US
dc.subject.pquncontrolledResource Allocationen_US
dc.subject.pquncontrolledTheoretical Computer Scienceen_US
dc.titleAllocation Algorithms for Networks with Scarce Resourcesen_US
dc.typeDissertationen_US

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Sarpatwar_umd_0117E_16014.pdf
Size:
1.04 MB
Format:
Adobe Portable Document Format
Download

Collections

UMD Theses and Dissertations
Computer Science Theses and Dissertations