Group Seminar
"Algorithms and Complexity"
Winter term 2009/10
Junior-Prof. Dr. Robert Elsässer
Seminars are on Tuesday from 11:00-13:00 in Building 106, Room 04 007.
27.01.2010
SINR Diagrams: Towards Algorithmically Usable SINR Models of Wireless Networks
Chen Avin, Ben-Gurion University of the NegevThe rules governing the availability and quality of connections in a wireless network are described by physical models such as the signal-to-interference & noise ratio (SINR) model. For a collection of simultaneously transmitting stations in the plane, it is possible to identify a reception zone for each station, consisting of the points where its transmission is received correctly. The resulting SINR diagram partitions the plane into a reception zone per station and the remaining plane where no station can be heard. SINR diagrams appear to be fundamental to understanding the behavior of wireless networks, and may play a key role in the development of suitable algorithms for such networks, analogous perhaps to the role played by Voronoi diagrams in the study of proximity queries and related issues in computational geometry. So far, however, the properties of SINR diagrams have not been studied systematically, and most algorithmic studies in wireless networking rely on simplified graph-based models such as the unit disk graph (UDG) model, which conveniently abstract away interference-related complications, and make it easier to handle algorithmic issues, but consequently fail to capture accurately some important aspects of wireless networks. The current paper focuses on obtaining some basic understanding of SINR diagrams, their properties and their usability in algorithmic applications. Specifically, based on some algebraic properties of the polynomials defining the reception zones we show that assuming uniform power transmissions, the reception zones are convex and relatively well-rounded. These results are then used to develop an efficient approximation algorithm for a fundamental point location problem in wireless networks.
Joint work with: Yuval Emek, Erez Kantor, Zvi Lotker, David Peleg and Liam Roditty.
The talk take place in building 101-01-016 at 11:00 (c.t.)
15.12.2009
Load Balancing by Randomized Rounding
Thomas SauerwaldWe analyze a "randomized rounding"-based algorithm for balancing indivisible loads on graphs. The aim is minimizing the discrepancy, i.e., the difference between the maximum and minimum load. In every time-step paired nodes balance their load as evenly as possible. Previous algorithms assumed that the excess token (if any) is kept by the node with the larger load. In this case it is easy to construct initial load distributions such that the discrepancy is not smaller than the diameter of the graph. To bypass this problem, we consider an algorithm which directs the excess token randomly to one of the participating nodes.
In the first part of the talk, we analyze this algorithm on hypercubes with n nodes. We show that after log n steps, the discrepancy is log log n + O(1) (with high probability). We also prove that after 3*log n steps, the discrepancy drops to 2. In the second part of the talk we consider general graphs. We show that in comparison to the previous algorithm, we get an improvement of roughly a square root of the achieved discrepancy in the same number of steps. For expanders, our algorithm even achieves a constant discrepancy in O(log (Kn) (log log n)^3) steps, where K is the discrepancy of the initial load. Hence our algorithm almost eliminates the gap between divisible and indivisible loads.
9.12.2009
Randomization Techniques for Efficient Information Dissemination and Network Exploration
Robert ElsässerThis talk consists of two parts. In the first part, we analyze the runtime and number of message transmissions generated by simple randomized broadcasting algorithms in graphs modeling certain real world networks. We first consider the so called random phone call model introduced by Karp, Schindelhauer, Shenker, and Vöcking (FOCS'2000). In this model it is assumed that in each time step every node chooses a neighbor, uniformly at random, and establishes a communication channel to this node. The channels can then be used for bi-directional communication in this step. We show that an apparently minor change in the ability of the nodes implies an exponential decrease in the average communication overhead produced by broadcasting algorithms in the random phone call model.
In the second part of the talk we consider the cover time of random walks, i.e., the expected number of time steps a random walk needs to visit all vertices of a graph. Speeding up random walks to reduce the cover time is a very important task in the theory of computing. First, we assume that the walk can explore among the neighbors of the currently visited vertex, and analyze the speed up of this modified exploration strategy in many important network classes. Then, we consider multiple walks which start at the same vertex, and provide (almost) tight bounds for the ratio between the cover time of one and the cover time of k independent walks.
The talk take place in building 101-02-016 at 16:00 (c.t.)
8.12.2009
SRPT and Completion Time Scheduling
Tim NonnerWe consider the problem of on-line scheduling jobs that are released over time on multiple identical machines with preemption, where the used performance measure is the total completion time. This problem is denoted P | r_j, prmt | sum_j C_j. Improving a 15 year old bound of 2, we show that the well-known algorithm SRPT (Shortest Remaining Processing Time) is 1.86-competitive. To obtain this result, we use some nice probabilistic tricks.
10.11.2009
Rumor spreading in random graphs with power law degree distribution
Adrian Ogierman (Universität Paderborn)Efficient broadcasting is a fundamental problem in distributed computing. One of the main questions is how to spread a message of a node to all nodes of an unknown network under certain time and traffic constraints. We present an algorithm, which solves this problem in a random graph with power law degree distribution within O(log n) rounds by using O(n log log n) message transmissions. Our communication model is based on the random phone call model introduced by Karp, Schindelhauer, Shenker and Vöcking (FOCS 2000), in which every node is allowed to choose in each time step a random neighbor uniformly at random, and to open a bidirectional communication channel to this node. In our case, however, we allow the nodes to choose a constant number of different neighbors, uniformly at random. We show that this simple modification leads to an exponential improvement in the number of message transmissions if the runtime of the algorithm is required to be asymptotically optimal (i.e., O(log n)).