SINR Diagram with Interference Cancellation

Chen Avin, Asaf Cohen, Yoram Haddad, Erez Kantor, Zvi Lotker, Merav Parter and David Peleg

Abstract:
This paper studies the reception zones of a wireless network in the SINR model with receivers that employ interference cancellation (IC). IC is a recently developed technique that allows a receiver to decode interfering signals, and cancel them from the received signal in order to decode its intended message.
We first derive the important topological properties of the reception zones and their relation to high-order Voronoi diagrams and other geometric objects. We then discuss the computational issues that arise when seeking an efficient description of the zones. Our main fundamental result states that although potentially there are exponentially many possible cancellation orderings, and as a result, reception zones, in fact there are much fewer nonempty such zones. We prove a linear bound (hence tight) on the number of zones and provide a polynomial time algorithm to describe the diagram. Moreover, we introduce a novel parameter, the
Compactness Parameter, which influences the tightness of our bounds. We then utilize these properties to devise a logarithmic time algorithm to answer point-location queries for networks with IC.

Guest: Merav Parter
Host: Shantanu Das

Metastability of Logit Dynamics for Coordination Games

Vincenzo Auletta, Diodato Ferraioli, Francesco Pasquale, Giuseppe Persiano

Abstract:

Logit Dynamics [Blume, Games and Economic Behavior, 1993] is a randomized best response dynamics for strategic games: at every time step a player is selected uniformly at random and she chooses a new strategy according to a probability distribution biased toward strategies promising higher payoffs. This process defines an ergodic Markov chain, over the set of strategy profiles of the game, whose unique stationary distribution is the long-term equilibrium concept for the game. However, when the mixing time of the chain is large (e.g. exponential in the number of players), the stationary distribution loses its appeal as equilibrium concept, and the transient phase of the Markov chain becomes important. In several cases it happens that on a time-scale shorter than mixing time the chain is “quasi-stationary”, meaning that it stays close to some small set of the state space, while in a time-scale multiple of the mixing time it jumps from one quasi-stationary configuration to another; this phenomenon is usually called “metastability”.
In this paper we give a quantitative definition of “metastable probability distributions” for a Markov chain and we study the metastability of the Logit dynamics for some classes of coordination games. In particular, we study no-risk-dominant coordination games on the clique (which is equivalent to the well-known Glauber dynamics for the Ising model) and coordination games on a ring (both the risk-dominant and no-risk-dominant case). We also describe a simple “artificial” game that highlights the distinctive features of our metastability notion based on distributions.

Guest: Francesco Pasquale

Host: Merav Parter

Wireless Connectivity and Capacity

Abstract:

Given $n$ wireless transceivers located in a plane, a fundamental problem in wireless communications is to construct a strongly connected digraph on them such that the constituent links can be scheduled in fewest possible time slots, assuming the SINR model of interference.
In this paper, we provide an algorithm that connects an arbitrary point set in $O(\log n)$ slots, improving on the previous best bound of $O(\log^2 n)$ due to Moscibroda. This is complemented with a super-constant lower bound on our approach to connectivity. An important feature is that the algorithms allow for bi-directional (half-duplex) communication.
One implication of this result is an improved bound of $\Omega(1/\log n)$ on the worst-case capacity of wireless networks, matching the best bound known for the extensively studied average-case.
We explore the utility of oblivious power assignments, and show that essentially all such assignments result in a worst case bound of $\Omega(n)$ slots for connectivity. This rules out a recent claim of a $O(\log n)$ bound using oblivious power. On the other hand, using our result we show that $O(\min(\log \Delta, \log n \cdot (\log n + \log \log \Delta)))$ slots suffice, where $\Delta$ is the ratio between the largest and the smallest links in a minimum spanning tree of the points.
Our results extend to the related problem of minimum latency aggregation scheduling, where we show that aggregation scheduling with $O(\log n)$ latency is possible, improving upon the previous best known latency of $O(\log^3 n)$. We also initiate the study of network design problems in the SINR model beyond strong connectivity, obtaining similar bounds for biconnected and $k$-edge connected structures.

Host: Merav Parter

Approximation Algorithms for Stochastic Orienteering

Anupam Gupta Ravishankar Krishnaswamy Viswanath Nagarajan R. Ravi

Abstract: In the Stochastic Orienteering problem, we are given a metric, where each node also has a job located there with some deterministic reward and a random size. (Think of the jobs as being chores one needs to run, and the sizes as the amount of time it takes to do the chore.) The goal is to adaptively decide which nodes to visit to maximize total expected reward, subject to the constraint that the total distance traveled plus the  total size of jobs processed is at most a given budget of B. (I.e., we get reward for all those chores we finish by the end of the day). The (random) size of a job is not known until it is completely processed. Hence the problem combines aspects of both the stochastic
knapsack problem with uncertain item sizes and the deterministic orienteering problem of using a limited travel time to maximize gathered rewards located at nodes.

In this paper, we present a constant-factor ap-approximation algorithm for the best non-adaptive policy for the Stochastic Orienteering problem. We also show a small adaptivity gap, i.e., the existence of a non-adaptive policy whose reward is at least an ­$\Omega(1/\log \log B)$ fraction of the optimal expected reward, and hence we also get an $O(\log \log B)$ approximation algorithm for the adaptive problem.

Finally we address the case when the node rewards are also random and could be correlated with the waiting time, and give a non-adaptive policy which is an $O(\log n \log B)$-approximation to the best adaptive policy on n-node metrics with budget B.

Guest: Ravishankar Krishnaswamy
Host: Zvi Lotker

The Notion of a Rational Convex Program, and an Algorithm for the Arrow-Debreu Nash Bargaining Game

Vijay Vazirani

Abstract: We introduce the notion of a rational convex program (RCP) and we classify the known RCPs into two classes: quadratic and logarithmic. The importance of rationality is that it opens up the possibility of computing an optimal solution to the program via an algorithm that is either combinatorial or uses an LP-oracle. Next we deﬁne a new Nash bargaining game, called ADNB, which is derived from the linear case of the Arrow-Debreu market model. We show that the convex program for ADNB is a logarithmic RCP, but unlike other known members of this class, it is non-total.
Our main result is a combinatorial, polynomial time algorithm for ADNB. It turns out that the reason for infeasibility of logarithmic RCPs is quite different from that for LPs and quadratic RCPs. We believe that our ideas for surmounting the new difficulties will be useful for dealing with other non-total RCPs as well. We give an application of our combinatorial algorithm for ADNB to an important “fair” throughput allocation problem on a wireless channel. Finally, we present a number of interesting questions that the new notion of RCP raises.

Guest: Vijay Vazirani
Host: Zvi Lotker

On the communication and streaming complexity of maximum bipartite matching

Ashish Goel, Michael Kapralov and Sanjeev Khanna

Abstract Consider the following communication problem. Alice holds a graph $G_A=(P,Q,E_A)$ and Bob holds a graph $G_B=(P,Q,E_B)$, where |P|=|Q|=n. Alice is allowed to send Bob a message m that depends only on the graph GA. Bob must then output a matching $M\subseteq E_A \cup E_B$. What is the minimum message size of the message m that Alice sends to Bob that allows Bob to recover a matching of size at least $(1-\epsilon)$ times the maximum matching in $G_A\cup G_B$? The minimum message length is the one-round communication complexity of approximating bipartite matching. It is easy to see that the one-round communication complexity also gives a lower bound on the space needed by a one-pass streaming algorithm to compute a $(1-\epsilon)$ approximate bipartite matching. The focus of this work is to understand one-round communication complexity and one-pass streaming complexity of maximum bipartite matching. In particular, how well can one approximate these problems with linear communication and space? Prior to our work, only a 1/2-approximation was known for both these problems.
We show that for any  $\delta>0$, a $(2/3+\delta)$-approximation requires a communication complexity of $n^{1+\Omega(1/\log\log n)}$ .
We also consider the natural restrictingon of the problem in which $G_A$ and $G_B$ are only allowed to share vertices on one side of the bipartition, which is motivated by applications to one-pass streaming with vertex arrivals. We show that a 3/4-approximation can be achieved with a linear size message in this case, and this result is best possible in that super-linear space is needed to achieve any better approximation.
Finally, we build on our techniques for the restricted version above to design one-pass streaming algorithm for the case when vertices on one side are known in advance, and the vertices on the other side arrive in a streaming manner together with all their incident edges. This is precisely the setting of the celebrated (1-1/e)-competitive randomized algorithm of Karp-Vazirani-Vazirani (KVV) for the online bipartite matching problem. We present here the first deterministic one-pass streaming (1-1/e)-approximation algorithm using O(n) space for this setting.

Guest: Michael Kaparalov
Host: Yvonne-Anne Pignolet

Approximate Duality of Multicommodity Multiroute Flows and Cuts: Single Source Case

Petr Kolman and Christian Scheideler

Abstract:

Given an integer h, a graph $G = (V, E)$ with arbitrary positive edge capacities and k pairs of vertices $(s_1,t_1),(s_2, t_2),\dots,(s_k,t_k)$, called terminals, an h-route cut is a set $F \subset E$ of edges such that after the removal of the edges in F no pair $s_i-t_i$ is connected by h edge-disjoint paths (i.e., the connectivity of every $s_i-t_i$ pair is at most $h-1$ in $(V, E \setminus F))$. The h-route cut is a natural generalization of the classical cut problem for multicommodity flows (take h = 1). The main result of this paper is an $O(h^{5}2^{2h}(h+log k)^2)$-approximation algorithm for the minimum h-route cut problem in the case that $s_1 = s_2 =\dots= s_k$, called the single source case. As a corollary of it we obtain an approximate duality theorem for multiroute multicommodity flows and cuts with a single source. This partially answers an open question posted in several previous papers dealing with cuts for multicommodity multiroute problems.

Guest: Christian Scheideler
Host: Shantanu Das

Exact Distance Oracles for Planar Graphs

Shay Mozes and Christian Sommer

Abstract:

We present new and improved data structures that answer exact node-to-node distance queries in planar graphs. Such data structures are also known as distance oracles. For any directed planar graph on n nodes with non-negative lengths we obtain the following:

• Given a desired space allocation S \in $n \log\log n, n^2$, we show how to construct in $\~{O}(S)$ time a data structure of size O(S) that answers distance queries in $\~{O}(n/\sqrt{S})$ time per query. As a consequence, we obtain an improvement over the fastest algorithm for k-many distances in planar graphs whenever $k \in \[\sqrt{n},n)$.
• We provide a linear-space exact distance oracle for planar graphs with query time $O(n^{1/2+\epsilon})$ for any constant $\epsilon > 0$. This is the first such data structure with provable sublinear query time.
• For edge lengths $\geq 1$, we provide an exact distance oracle of space $\~{O}(n)$ such that for any pair of nodes at distance $l$ the query time is $\~{O} (min\{l,\sqrt{n}\})$. Comparable query performance had been observed experimentally but could not be proven.

Our data structures are based on the following new tool: given a non-self-crossing cycle C with $c = O(\sqrt{n})$ nodes, we can preprocess G in $\~{O}(n)$ time to produce a data structure of size $O(n \log{\log{c}})$ that can answer the following queries in $\~{O}(c)$ time: for a query node u, output the distance from u to all the nodes of C. This data structure builds on and extends a related data structure of Klein (SODA’05), which reports distances to the boundary of a face, rather than a cycle.
The best distance oracles for planar graphs until the current work are due to Cabello (SODA’06), Djidjev (WG’96), and Fakcharoenphol and Rao (FOCS’01). For $\sigma \in (1, \sfrac{4}{3})$ and space $S = n^\sigma$, we essentially improve the query time from $n^2/S$ to $\sqrt{n^2/S}$.

Guest: Shay Mozes
Host: Shantanu Das

Ultra-Fast Rumor Spreading in Social Networks

Nikolaos Fountoulakis, Konstantinos Panagiotou and Thomas Sauerwald

Abstract:
We analyze the popular push-pull protocol for spreading a rumor in networks. Initially, a single node knows of a rumor. In each succeeding round, every node chooses a random neighbor, and the two nodes share the rumor if one of them is already aware of it. We present the first theoretical analysis of this protocol on random graohs that have a power law degree distribution with an arbitrary exponent β ≥ 2.

Our main ﬁndings reveal a striking dichotomy in the performance of the protocol that depends on the exponent of the power law. More speciﬁcally, we show that if 2 < β < 3, then the rumor spreads to almost all nodes in Θ(log log n) rounds with high probability. On the other hand, if β > 3, then Ω(log n) rounds are necessary.

We also investigate the asynchronous version of the push-pull protocol, where the nodes do not operate in rounds, but exchange information according to a Poisson process with rate 1. Surprisingly, we are able to show that, if 2 < β < 3, the rumor spreads even in constant time, which is much smaller than the typical distance of two nodes. To the best of our knowledge, this is the ﬁrst result that establishes a gap between the synchronous and the asynchronous protocol.

Guest: Thomas Sauerwald
Host: Chen Avin

Information Dissemination via Random Walks in d-Dimensional Space

Henry Lam, Zhenming Liu, Michael Mitzenmacher, Xiaorui Sun and Yajun Wan

Abstract:
We study a natural information dissemination problem for multiple mobile agents in a bounded Euclidean space. Agents are placed uniformly at random in the d-dimensional space {-n, …, n}^d at time zero, and one of the agents holds a piece of information to be disseminated. All the agents then perform independent random walks over the space, and the information is transmitted from one agent to another if the two agents are sufficiently close. We wish to bound the total time before all agents receive the information (with high probability). Our work extends Pettarin et al’s work [10], which solved the problem for d = 2. We present tight bounds up to polylogarithmic factors for the case d = 3. (While our results extend to higher dimensions, for space and readability considerations we provide only the case d = 3 here.) Our results show the behavior when d >= 3 is qualitatively different from the case d = 2. In particular, as the ratio between the volume of the space and the number of agents varies, we show an interesting phase transition for three dimensions that does not occur in one or two dimensions.

Guest: Henry Lam
Host: Chen Avin