[Discrete-math-seminar] Seminar today, Thursday Oct 5

[Robert Ellis]

Please join us for today's seminar, 1:15pm in E1 124.

Gruia Calinescu (IIT Computer Science)

Title: Min-Energy Broadcast with Hitch-hiking

Abstract: Recently, there have been papers indicating that the maximal 
ratio combiner device can result in energy savings in wireless ad hoc 
networks by using Hitch-hiking. We study the Min-Energy Broadcast with 
Hitch-hiking problem, an idealized version of broadcast using 
hitch-hiking, a problem studied experimentally in the INFOCOM 2004 paper 
of Agarwal et. al. Min-Energy Broadcast with Hitch-hiking captures the 
maximum savings one can achieve in broadcasting using maximal ratio 
combiners. We show that the optimum of the classical Min-Energy Broadcast 
problem is at most O(\log^2 n) times the optimum of Min-Energy Broadcast 
with Hitch-hiking, where n is the number of nodes in the networks. We show 
that this bound is tight up to a constant. All the results hold for 
Unicast as well.

In the special case when the nodes are on a line and the power requirement 
for node u to reach node v is d(u,v)^kappa, where d(u,v) the Euclidean 
distance between u and v and kappa is the signal attenuation exponent, 
which is assumed to be in between 2 and 5, we show that the optimum of the 
Min-Energy Broadcast problem is at most a constant times optimum of 
Min-Energy Broadcast with Hitch-hiking.

A formal definition of Min-Energy Broadcast with Hitch-hiking is given 
below. The input consists of a complete directed graph G=(V,E) with power 
requirement function c : E -> R+, and a source s in V. The output consists 
of a permutation tau = v1, v2, ..., vn of V with v_1 = s and power 
assignment p(v) of every vertex v. For every 1 <=i < j <= n, define 
q(vi,vj) = p(vi)/c(vi,vj). An output is feasible if for every j > 1 we 
have sum_{i=1}^{j-1} q(vi,vj) >= 1. The objective is to minimize 
sum_{i=1}^n p(vi).