Many modern services need to routinely perform tasks on a large scale. This prompts us to consider the following question:How can we design efficient algorithms for large-scale computation?In this thesis, we focus on devising a general strategy to addr ...
We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality gap of th ...
Randomization is a fundamental tool used in many theoretical and practical areas of computer science. We study here the role of randomization in the area of submodular function maximization. In this area, most algorithms are randomized, and in almost all c ...
Many map-reduce frameworks as well as NoSQL systems rely on collection programming as
their interface of choice due to its rich semantics along with an easily parallelizable set of
primitives. Unfortunately, the potential of collection programming is not ...
Index join performance is determined by the efficiency of the lookup operation on the involved index. Although database indexes are highly optimized to leverage processor caches, main memory accesses inevitably increase lookup runtime when the index outsiz ...
In this paper we present the application of the interior-point decomposition (IPD) method, which was originally formulated for stochastic programming, to optimization problems involving multiple agents that are coupled through constraints and objectives. I ...
We consider the problem of solving a distributed optimization problem using a distributed computing platform, where the communication in the network is limited: each node can only communicate with its neighbors and the channel has a limited data-rate. A co ...
Many of the currently best-known approximation algorithms for NP-hard optimization problems are based on Linear Programming (LP) and Semi-definite Programming (SDP) relaxations. Given its power, this class of algorithms seems to contain the most favourable ...
The goal of query optimization is to map a declarative query (describing data to generate) to a query plan (describing how to generate the data) with optimal execution cost. Query optimization is required to support declarative query interfaces. It is a co ...
In this paper, we study the data exchange problem, where a set of users is interested in gaining access to a common file, but where each has only partial knowledge about it as side-information. Assuming that the file is broken into packets, the side-inform ...
Institute of Electrical and Electronics Engineers2016
