Abstracts: DIMAP Algorithms Day 2014
Alexandr Andoni (Microsoft Research)
Parallel Algorithms for Geometric Graph Problems
Motivated by modern parallel computing models (think MapReduce), we give a new algorithmic framework for geometric graph problems. Our framework applies to problems such as the Minimum Spanning Tree (MST) problem over a set of points in a low-dimensional space, which is useful for hierarchical agglomerative clustering. Our algorithm computes a $(1+epsilon)$-approximate MST in a *constant* number of rounds of communication, while using total space and communication proportional to the size of the data only.
Our framework proves to have implications beyond the parallel models as well. For example, we consider the Earth-Mover Distance (EMD) problem, for which we obtain a new near-linear time algorithm as well as a first streaming algorithm (assuming we can pre-sort the points). Technically, our framework for EMD shows how to effectively break up a "big Linear Programming problem" into a number of "small Linear Programming problems", which can be later recombined using a dynamic programming approach.
Our results also address open questions from [Sarathkumar-Agarwal, STOC'12], as well as a well-known open question on streaming EMD (http://sublinear.info/index.php?title=Open_Problems:7).
Graham Cormode (University of Warwick)
Parameterized Streaming Algorithms for Vertex Cover
As graphs continue to grow in size, we seek ways to effectively process such data at scale. The model of streaming graph processing, in which a compact summary is maintained as each edge insertion/deletion is observed, is an attractive one. However, few results are known for optimization problems over such dynamic graph streams. In this work, we introduce a new approach to handling graph streams, by instead seeking solutions for the parameterized versions of problems where we are given a parameter k and the objective is to decide whether there is a solution bounded by k. By combining kernelization techniques with randomized sketch structures, we obtain the first streaming algorithms for parameterized versions of Vertex Cover and Maximal Matching.
Edith Elkind (University of Oxford)
Preference Aggregation on Structured Domains
Arrow's famous impossibility theorem (1951) states that there is no perfect voting rule: for three or more candidates, no voting rule can satisfy a small set of very appealing axioms. However, this is no longer the case if we assume that voters' preferences satisfy certain restrictions, such as being single-peaked or single-crossing. In this talk, we discuss single-peaked and single-crossing elections, as well as some other closely related restricted preference domains, and associated algorithmic questions.
Leszek Gąsieniec (University of Liverpool)
Ephemeral Networks with Random Availability of Links
In this work we consider temporal networks in which the connections are available only at random times (randomly available temporal networks). Our networks are ephemeral, i.e., their links appear sporadically within a given maximum time (lifetime of the network). More precisely, our temporal networks notion concerns networks, whose edges (arcs) are assigned one or more random discrete-time labels drawn from a set of natural numbers. The labels of an edge indicate the discrete moments in time at which the edge is available. In such networks, information (e.g., messages) have to follow temporal paths, i.e., paths, the edges of which are assigned a strictly increasing sequence of labels.
We first examine a very hostile network: a clique, each edge of which is known to be available randomly exactly once during the time period (1,2,...,n), where n is the number of vertices. How fast can a vertex send a message to all other vertices in such a network? To answer this, we define the notion of the "temporal diameter" for the random temporal clique and prove that it is O(log n) with high probability and in expectation. This result is similar to the results known for the random phone-call model. Our model, however, is weaker. Our availability assumptions are different and randomness is provided only by the input.
We later show that the temporal diameter of the clique is crucially affected by the clique's lifetime. We also establish the lower bound Omega(log n) on the number of random instances at which each edge is available in order to guarantee a temporal path between any pair of the network nodes. Finally, we compare this bound to the optimal deterministic allocation of labels of availability that guarantees a temporal path between any pair of nodes. For this reason, we introduce the notion of the Price of Randomness (PoR) and we show the respective upper bound for general networks.
Aleksander Mądry (EPFL)
From Graphs to Matrices, and Back: Bridging the Combinatorial and the Continuous
Graphs are ubiquitous in all modern sciences, serving as models for a variety of complex systems (e.g., the web graph, social networks, road systems, protein interactions, and the brain). This motivates a need for algorithmic tools that are capable of analyzing and computing on graphs in an efficient manner. A need that is even more pressing now that the graphs we are dealing with tend to be massive, rendering traditional methods no longer adequate.
In this talk, I will discuss an emerging theme in the design of graph algorithms that approaches problems in the area by connecting combinatorial properties of graphs to linear-algebraic properties of certain associated matrices. In particular, I will describe an application of this approach to the maximum flow problem - a task of key importance in optimization and operations research. The obtained algorithms improve upon the classic results of Even-Tarjan and Hopcroft-Karp.
I will also briefly outline how this line of work brings a new perspective on some of the core continuous optimization primitives. Most notably, how it lets us gain an alternative understanding of the convergence behavior of interior-point methods - a fundamental tool in continuous optimization - suggesting an avenue for making progress on certain outstanding questions in that field.