Discrete location theory is concerned with combinatorial optimization problems in which spatial considerations play a prominent role. For example, one basic discrete location problem asks for a specified number of points in a given metric space to be marked so that the sum, over all points, of the distance to the nearest marked point is minimized. Peer-to-peer computing is an emerging discipline concerned with the seamless interconnection of dynamic collections of nodes for the purpose of sharing computational resources such as bandwidth, storage, and CPU. A good first-order model of peer-to-peer networks assumes that the nodes reside in a metric space, and that the cost of communication between a pair of nodes is given by the corresponding distance in the underlying metric space. Because the internode distances in peer-to-peer networks tend to vary significantly, spatial considerations play a prominent role in peer-to-peer computing. This project addresses a number of basic questions in discrete location theory, emphasizing questions that arise in applications to peer-to-peer computing.
Discrete location theory is not a new subject, having been studied within the operations research community for decades. Many of the basic problems in this area are NP-hard, so practitioners have generally resorted to heuristics in order to search for optimal or near-optimal solutions. Unfortunately, with few exceptions, the solutions returned by these heuristics can be arbitrarily far from optimal. In recent years, there has been an explosion of interest in the design and analysis of provably good approximation algorithms for NP-hard optimization problems. This research has shed considerable light on the approximability of a number of basic discrete location problems, for example, establishing that the optimal solution to the facility location problem can be approximated to within a factor of 1.52 in polynomial time, but that achieving a factor of 1.463 would violate a standard hardness assumption. Given such theoretical advances, it is natural to ask whether these provably good approximation algorithms are preferable to existing heuristics in practice. For the most part this is not the case, since the running times of these approximation algorithms, while polynomial, tend to be considerably higher than those of existing heuristics. For the discrete location problems addressed in this project, the primary objective of this project is to develop constant-factor approximation algorithms that are comparable to (or improve upon) existing heuristics in terms of running time and ease of implementation.
Peer-to-peer computing is a young field with obvious potential, but significant technical challenges remain to be addressed before this potential can be realized. More scalable than client-server, peer-to-peer enables a wide-range of large-scale applications that cannot be supported by existing server farms. Furthermore, peer-to-peer computing holds the promise of delivering supercomputer-like performance to the average user. But before such lofty goals can be achieved, existing peer-to-peer systems need to be significantly refined and extended in order to comprehensively address issues related to locality, concurrency, fault tolerance, self-stabilization, heterogeneity, cost sharing, and security. This project investigates novel approaches to the design of practical and provably efficient peer-to-peer infrastructure, emphasizing locality-related concerns.
