アイテムの簡略レコードを表示する

Resource Allocation in Networked and Distributed Environments

dc.contributor.advisorSrinivasan, Aravinden_US
dc.contributor.authorParthasarathy, Srinivasanen_US
dc.date.accessioned2007-02-01T20:20:16Z
dc.date.available2007-02-01T20:20:16Z
dc.date.issued2006-08-30en_US
dc.identifier.urihttp://hdl.handle.net/1903/4056
dc.description.abstractA central challenge in networked and distributed systems is resource management: how can we partition the available resources in the system across competing users, such that individual users are satisfied and certain system-wide objectives of interest are optimized? In this thesis, we deal with many such fundamental and practical resource allocation problems that arise in networked and distributed environments. We invoke two sophisticated paradigms -- linear programming and probabilistic methods -- and develop <em>provably-good approximation algorithms</em> for a diverse collection of applications. Our main contributions are as follows. Assignment problems: An assignment problem involves a collection of objects and locations, and a load value associated with each object-location pair. Our goal is to assign the objects to locations while minimizing various cost functions of the assignment. This setting models many applications in manufacturing, parallel processing, distributed storage, and wireless networks. We present a <em>single</em> algorithm for assignment which generalizes many classical assignment schemes known in the literature. Our scheme is derived through a fusion of linear algebra and randomization. In conjunction with other ideas, it leads to novel guarantees for multi-criteria parallel scheduling, broadcast scheduling, and social network modeling. Precedence constrained scheduling: We consider two precedence constrained scheduling problems, namely sweep scheduling and tree scheduling, which are inspired by emerging applications in high performance computing. Through a careful use of randomization, we devise the first approximation algorithms for these problems with near-optimal performance guarantees. Wireless communication: Wireless networks are prone to interference. This prohibits proximate network nodes from transmitting simultaneously, and introduces fundamental challenges in the design of wireless communication protocols. We develop fresh geometric insights for characterizing wireless interference. We combine our geometric analysis with linear programming and randomization, to derive near-optimal algorithms for latency minimization and throughput capacity estimation in wireless networks. In summary, the innovative use of linear programming and probabilistic techniques for resource allocation, and the novel ways of connecting them with application-specific ideas is the pivotal theme and the focal point of this thesis.en_US
dc.format.extent1282046 bytes
dc.format.mimetypeapplication/pdf
dc.language.isoen_US
dc.titleResource Allocation in Networked and Distributed Environmentsen_US
dc.typeDissertationen_US
dc.contributor.publisherDigital Repository at the University of Marylanden_US
dc.contributor.publisherUniversity of Maryland (College Park, Md.)en_US
dc.contributor.departmentComputer Scienceen_US
dc.subject.pqcontrolledComputer Scienceen_US
dc.subject.pquncontrolledcombinatorial optimizationen_US
dc.subject.pquncontrolledrandomizationen_US
dc.subject.pquncontrolledapproximation algorithmsen_US
dc.subject.pquncontrolledparallel schedulingen_US
dc.subject.pquncontrolledwireless communicationen_US
dc.subject.pquncontrolledwireless capacityen_US


このアイテムのファイル

Thumbnail

このアイテムは次のコレクションに所属しています

アイテムの簡略レコードを表示する