Approximation Algorithms and Models for Problems in Distributed Systems

Recent advances in network technologies have given rise to many interesting problems in the area of computer science that lies at the crossroads of distributed computing and approximation algorithms. This dissertation focuses on the design and analysis of approximation algorithms for optimization problems that usually arise in resource constrained and dynamic networks (e.g. wireless ad-hoc networks and sensor networks) and large-scale storage systems that are crucial components in data-intensive applications (e.g. search engine clusters, sensor networks, cloud and grid computing). In particular, we consider the following two fundamental network optimization problems: channel assignment in multi-channel wireless networks and data migration in heterogeneous large-scale storage systems. For these problems, we define a Soft Edge Coloring model, we design approximation and online algorithms and, prove hardness and impossibility results.