CRESCCO 2004 WORKSHOP

October 16, 2004

Rome, Italy

List of Presentation Abstracts

Title: A Survey of Routing in Small Worlds

Speaker (Invited): Pierre Fraigniaud (Université Paris-Sud/Centre National de la Recherche Scientifique, France)

Abstract: This talk will survey the recent results related to routing in augmented graphs. From the seminal work of Kleinberg, we will mostly concentrate our attention on d-dimensional meshes augmented with links chosen at random. Greedy routing in these graphs aims at modeling the behavior of entities looking for information in a societal network, and at giving formal support to Milgram's experiment. The many different types of greedy routing strategies will be surveyed, and their applications to the design of overlay networks for P2P applications discussed.

Title: On efficient weighted rectangle packing with large resources

Speaker: Aleksei Fishkin (Christian-Albrechts-Universitaet zu Kiel, Germany)

Joint work with: Olga Gerber and Klaus Jansen 

Abstract: We address the problem of packing of a list $L$ of $n$ rectangles with weights into a dedicated rectangle $R$ so that the weight of the packed rectangles is maximized. We consider the case of large resources, that is, $R$ has width $a>0$ and height $b>0$, whereas each rectangle in $L$ has width in $(0,a]$ and height in $(0,\eps^3 \cdot b]$, for some small $\eps>0$.
We present an algorithm which finds a packing of a sublist of $L$ whose total weight is at least $(1-\eps)\OPT(L)$, where $\OPT(L)$ is the optimum. The running time of the algorithm is polynomial in $n$ and $1/\eps$.

Title: Monotone algorithms for truthful mechanisms

Speaker: Paolo Penna (Universita degli Studi di Salerno, Italy)

Abstract: Several problems related to the Internet turn out to be problems involving so called *selfish agents*, that is, problems in which a set of "players" can possibly misreport some information to the system in order to get some benefit (i.e., a better utility). Such a selfish behavior of the agents can lead the system to compute non-optimal (or unfeasible) solutions.

Title: Design of fault-tolerant networks for satellites

Speaker: Jean-Claude Bermond (Universite de Nice, Sophia-Antipolis /Centre National de la Recherche Scientifique, France)

Abstract: This talk deals with the design of networks to be placed on satellites, a problem proposed by Alcatel Space Industries. These networks should connect inputs (corresponding to signals arriving at the satellite) to outputs (corresponding to Travelling Wave Tube Amplifiers), even in the case of failures of amplifiers. The networks are made of links (wave guides) and expensive switches. Hence, we want to minimize the number of switches subject to the following conditions: each input and each output is connected to exactly one switch; each switch is adjacent to exactly four links; there are n inputs and n+k outputs; among the n+k outputs, k can fail permanently; and finally all the input signals should be sent to valid amplifiers (outputs) via disjoint paths. We survey the results obtained by the MASCOTTE team on this subject. There are variants of the problem according to whether each signal needs a specific amplifier or can be sent to any of the amplifiers (that is, all the amplifiers have the same function). In the first case we show how the problem is related to the construction of permutation networks. Furthermore, we also construct networks tolerating blocking of switches. In the case of identical amplifiers, the aim is to design networks having as few switches as possible and satisfying the following property: there exist n edge-disjoint paths from the n inputs to any set of n outputs chosen from the n+k total number of outputs. We show how to use flow theory and various tools to determine the minimum number of switches for small fixed k. We also show that in the case k = n, the problem is related to the existence of expanders. 

Title: Dynamical models for wireless sensor networks

Speaker: Pierre Leone (Centre Universitaire d'Informatique, Universite de Geneve, Switzerland)

Joint work with: Jose Rolim

Abstract: We start the talk with some general remarks related with dynamical modelling of wireless networks: various modelisations of the PHY and the MAC layers. We describe some applications and discuss capacity and  stability of wireless networks considering the classical ALOHA protocol. Next, we turn to our contribution. We introduce a dynamical model for wireless sensor networks. We obtain a convergent martingale for the broadcast process in such networks. To our  knowledge, such martingales were unknown previously. We look at a formal model using the formalisms of martingales, dynamical systems and Markov chains, each formalism providing complementary and coherent information with each other. The model is validated in its scope of application with numerical simulation of wireless sensor networks, we make explicit the situations where the model is realistic. We also provide a formal analysis of the quasi-stationary distribution. The model is based on hypothesis which are more fulfilled when the emission radius $r$ becomes larger and emission angle $\alpha$ smaller in order to keep the expected number of connections $\frac{N}{2}\alpha r^2$ constant. In the situation where the hypothesis are 'almost' fulfilled good agreement between numerical experiments and results of the model are observed.

Title: Efficient Assignment of Critical Resources: Frequencies, Links, Energy power

Speaker: Viki Papadopoulou (Computer Technology Institute, Greece)

Joint work with: CTI site

Abstract: We study important optimization issues or real network concerning the management and sharing of critical communication resources such as Frequencies, Links and Energy Power. We consider three basic fundamental relative problems:  

(i) The Frequency Assignment Problem in ordinary and Succinct Networks, where the frequencies are the critical resources. The objective is to establish communication using minimum bandwidth. We review on important basic results obtained by our group concerning proving hardness results and providing exact or approximation algorithms. 

(ii) Routing of Selfish Flows. Here the links are the critical resources. We consider the problem as a selfish routing game or a congestion game, where n players, corresponding to flows, wish selfishly to be satisfied (routed in the minimum expected latency). We explore the existence and tractability of Nash Equilibria in such games. 

(iii) Accomplishment of Large Sensing tasks (data propagation) in Sensor Networks. Here the critical resource is the energy. We provide energy efficient load balancing communication protocols for data propagation.

Title: Approximation algorithms for energy-efficient communication in ad hoc wireless networks

Speaker: Ioannis Caragiannis (University of Patras, Greece)

Joint work with: Christos Kaklamanis and Panagiotis Kanellopoulos

Abstract: Efficiently supporting communication patterns that are common in traditional (wired) networks is an important problem in ad hoc wireless network as well. These patterns include broadcasting, multicasting,
gossiping (all-to-all communication), and multiconnectivity. Since establishing communication in ad hoc wireless networks strongly depends on the use of energy, the important question to be solved is to guarantee a desired communication pattern minimizing the total energy consumption. Depending on the properties of the desired communication pattern, we define a series of communication problems where the minimization of energy is the main concern and present approximation algorithms and inapproximability results.

The talk will give an overview of results presented in the following papers:

(1) I. Caragiannis, C. Kaklamanis, and P. Kanellopoulos. New Results for Energy-Efficient Broadcasting in Wireless Networks. In Proc. of the 13th Annual International Symposium on Algorithms and Computation (ISAAC '02), LNCS 2518, Springer, pp. 332-343, 2002.

(2) I. Caragiannis, C. Kaklamanis, and P. Kanellopoulos. Energy-Efficient Wireless Network Design. In Proc. of the 14th Annual International Symposium on Algorithms and Computation (ISAAC '03), LNCS 2906, Springer, pp. 585-594, 2003.

Title: Algorithms for the Hop-Restricted Range Assignment Problems and other Extensions

Speaker: Miriam Di Ianni (Universita degli Studi di Roma "Tor Vergata", Italy)

Joint work with: C. Ambuehl, A.E.F. Clementi, M. Di Ianni, N. Lev-Tov, A. Monti, D. Peleg, G. Rossi and R. Silvestri

Abstract: This talk concerns the problem of computing minimal energy-cost range assignments in ad-hoc wireless networks allowing a station to perform broadcast (one-to-all communication) and anti-broadcast (all-to-one communication) operations in at most a constant number (h) of hops. In particular, the well-studied real case in which the stations are located on the plane and the cost to transmit from one station to another is proportional to some constant power (p) of the distance between the stations is considered.

The general version of the h-hops broadcast range assignment problem (i.e., when transmission costs are arbitrary) is a well-known NP-hard problem, even for h=2. In this talk the results in [1] are presented, i.e. a polynomial-time algorithm for finding an optimal 2-hops broadcast range assignment and a polynomial-time approximation scheme (PTAS) for the the h-hops broadcast range assignment for any fixed constant h. The results hold independently from P.

As to the anti-broadcast, an investigation on fast and easy-to-implement heuristics working for any constant h>0 and P=1 has been performed in [2], on instances obtained by choosing at random n points in a square of side length L. This formulation makes the anti-broadcast problem equivalent to that of computing height-bounded rooted minimum spanning trees of geometric graphs. The results of [2] are presented in this talk: 1) a general lower bound on the solution cost that holds with high probability 2) an easy-to-implement, very fast heuristic and the proof that its solution cost matches the lower bound; 3) the analysis of three simple heuristics based on classical greedy algorithms (Prim's and Kruskal's ones) for the MST problem. Rather surprisingly, they asymptotically do not do better (with high probability) than the trivial heuristic that connects all points directly to the root.

Finally, the weighted version of the previously mentioned range assignment problem is considered, in which the cost paid by a station to transmit to some other station does not depend only on their distance but also on the environmental conditions of the transmitting station. The set of algorithmic results for this more general version of the range assignment problems provided in [3] are discussed in this talk. 

[1] C. Ambuehl, A.E.F. Clementi, M. Di Ianni, N. Lev-Tov, A. Monti, D. Peleg, G. Rossi and R. Silvestri, "Efficient Algorithms for Low-Energy Bounded-Hop Broadcast in Ad-Hoc Wireless Networks", Proc. of STACS'04. 

[2] A.E.F.Clementi, M.Di Ianni, A.Monti, G.Rossi and R.Silvestri, "Analysis of Fast Heuristics for the Minimum $h$-Hops Spanning Tree Problem on Random Instances of the Plane", manuscript.

[3] C.Ambuehl, A.E.F.Clementi, M.Di Ianni, A.Monti, G.Rossi and R.Silvestri, "The Range Assignment Problem in Non-Homogeneous Static Ad-Hoc Networks", Proc. of IPDPS-WMAN04.