2nd  CRESCCO WORKSHOP

 ATHENS, GREECE, 6.12.2003-8.12.2003

List of Presentation Abstracts

Title: On Rectangle Packing: Maximizing Benefits

Speaker: Klaus Jansen (CAU)

Co­authors: Guochuan Zhang (CAU)

Related workpackage: WP3

Abstract: We consider the following rectangle packing problem: Given a set of rectangles, each of which is associated with a profit, we are requested to pack a subset of the rectangles into a bigger rectangle to maximize the total profit of rectangles packed. The rectangles may not overlap and may or may not be rotated. This problem is strongly NP-hard even for packing squares with identical profits. A simple $(3+\eps)$-approximation algorithm is presented. We further improve the algorithm by showing a worst-case ratio of at most $5/2+\eps$. Finally we devise a $(2+\eps)$-approximation algorithm. A number of restricted cases are also considered.

Title: Energy Consumption in Radio Networks: Selfish Agents and Rewarding Mechanisms 

Speaker: Andrea Clementi (Rome)

Co­authors: Christoph Ambuehl (Rome), Paolo Penna (UNISA), Gianluca Rossi (Rome), Riccardo Silvestri (Rome) 

Related workpackage: WP1, WP2

Abstract: We consider the \emph{range assignment} problem in ad-hoc wireless networks in the context of \emph{selfish agents}: a network manager aims in assigning transmission ranges to the stations so to achieve the strong connectivity of the network with a minimal \emph{overall energy}; stations are not directly controlled by the
manager and may refuse to transmit with a certain transmission range because this results in a power consumption proportional to that range. 

We study the existence of payment schemes which induce the stations to cooperate with a network manager computing a range assignment, that is, \emph{truthful mechanisms} for the range assignment problem. We provide both positive and negative results on the existence of truthful VCG-based mechanisms for this NP-hard problem. Our results give a strong evidence of the impact of the metric space when selfish agents are considered. We indeed prove that (i) in general, every truthful mechanism computes either an optimal solution or a solution of cost far-off the optimum, and (ii) there exists a polynomial-time truthful VCG-based mechanism achieving a constant approximation for practically relevant versions of the Euclidean case, which, in general, remain NP-hard.

Title: The Range Assignment Problem in Non-Homogeneous Static Ad-Hoc Networks

Speaker: Gianluca Rossi (Rome)

Co­authors: Christoph Ambuehl (Rome), Andrea Clementi (Rome), Miriam Di Ianni (Rome), Angelo
Monti (Rome), Riccardo Silvestri (Rome)

Related workpackage: WP1

Abstract: Given a finite set $S$ of points (i.e. the stations of a radio network) on a Euclidean space, a range assignment problem consists of assigning transmission ranges to the stations so as to minimize the total power consumption, provided that the transmission ranges of the stations ensure a given connectivity property of the resulting networks. Range assignment problems in Ad-Hoc wireless networks have been the subject of several recent studies. It turns out that the complexity of such problems strongly depends on the dimension of the Euclidean space, the energy cost function of the stations and on the required connectivity property.  All the above mentioned works on this problem deal with the {\em homogeneous case}, i.e., when all stations share the same energy cost function. More precisely, the cost a station $s$ pays to send a message to another station $t$ is $\gamma\dist(s,t)^\alpha$, where $\gamma$ and $\alpha$ are fixed constant. However, this assumption does not well model realistic scenarios in which the energy cost of a station varies dramatically depending on the particular enviroment conditions of its location. 

We thus introduce the weighted version of the range assignment problem in which the cost function a station $s$ pays to transmit to another station $t$ depends on $t$ and can be {\em any} monotone function of $\dist(s,t)$. Then, we provide a set of algorithmic results for this more general version of the range assignment problems and discuss some interesting related open questions.

Title: Introduction to Mascopt: a library for graph manipulation

Speaker: Jean-Francois Lalande (UNSA/CNRS)

Co­authors: Bruno Bongiovanni (UNSA/CNRS), Michel Syska (UNSA/CNRS), Yann Verhoeven (UNSA/CNRS)

Related workpackage: WP4, WP5

Abstract: We present in this talk the Mascopt software (Mascotte Optimization) which provides a set of tools for network optimization problems. Examples of problems are routing, grooming, survivability, or virtual network design. We present the first stage of the development process which produced the graph library package and ready to use implementation of existing algorithms or linear programs. This library has been designed to respect object-oriented modeling and to be user friendly rather than focusing on speed of optimization algorithms which use it. We explain the history of the writing of our library and the difficulties which appears when implementing combinatorial algorithms using graph models. We also present a basic description of the mascopt functionalities that developers, familiar with objects, can use effectively for their own experimentations.

Title: Energy Balanced Data Propagation in Wireless Sensor Network.

Speaker: Charilaos Efthymiou (CTI)

Co­authors: Sotiris Nikoletseas (CTI) and Jose Rolim (Geneva)

Related workpackage: WP1

Abstract: We study the problem of energy-balanced data propagation in wireless sensor networks. The energy balance property guarantees that the average per sensor energy dissipation is the same for all sensors in the network, during the entire execution of the data propagation protocol. This property is important since it prolongs the network's lifetime by avoiding early energy depletion of sensors.   

We propose a new algorithm that in each step decides whether to propagate data one-hop towards the final destination (the sink), or to send data directly to the sink. This randomized choice balances the (cheap) one-hop transimssions with the direct transimissions to the sink, which are more expensive but ``bypass" the sensors lying close to the sink. Note that, in most protocols, these close to the sink sensors tend to be overused and die out early. By a detailed analysis we precisely estimate the probabilities for each propagation choice in order to guarantee energy balance. The needed estimation can easily be performed by current sensors using simple to obtain information. Under some assumptions, we also derive a closed form for these probabilities.  The fact (shown by our analysis) that direct (expensive) transmissions to the sink are needed only rarely, shows that our protocol, besides energy-balanced, is also energy efficient.

Title: Efficient Colouring of Squares of Planar Graphs

Speaker: Maria Andreou (CTI)

Coauthors: Paul Spirakis (CTI)

Related workpackage: WP1

Abstract: In this work we provide a new colouring algorithm, which colours the {\em square} of any planar graph $G$ using at most $1.5 \D(G) + c$ colours, where $c$ is a constant such that $c \leq 26$ and $\D(G)$ is the maximum degree of $G$ and $\D(G) \geq 8$.  In 1977 Wegner conjectured the above bound for $c = 1$ in . The best currently known upper bound for the chromatic number of the square of $G$ is $1.66 \D(G) + 24$ due to Molloy and Salavatipour .

Title: Scheduling in Networks

Speaker: Aleksei Fishkin (CAU)

Related workpackage: WP3, WP5

Abstract: In the first part of the talk, we start with a short overview of some hardware (broadcast and point-to-point links, wireless, LAN, WAN, Internet) and software (protocols and layer hierarchy) issues in the modern networks. Then, we move to the problems of providing different services between protocol layers. Normally, network resources are restricted. So, in order to satisfy some particular quality of service (QoS), say low delay and high reliability, resources must be correctly allocated to users over time. The (bin, strip, rectangle) packing problems and the multiprocessor
(parallel, dedicated, malleable) task scheduling problems can help to model such situations. 

In the second part of the talk we discuss some simple approximation algorithms for the strip-packing problem. We formulate the problem, gives the ideas of algorithms, and demonstrate some experimental results.

Title: Optimal localization is sensor networks

Speaker: Claude Tadonki (Geneva)

Coauthors: Jose Rolim (Geneva), Mitali Singh (University of Southern California), Janka Chlebikova (CAU)

Related workpackage: WP1

Abstract: The localization problem is an important topic in sensors network management. At the initial step, a given subset of sensors a directly localized trough specialized system like GPS, and the localization of the remaining sensors is performed by a dynamic process in which a node knowing its coordinates communicates them to its neighbors. In this paper, we investigate the problem of finding a minimum subset for the localization problem in sensors network. We formulate the problem as a pure combinatorial problem and we attempt to prove its NP-Completeness. Polynomial results are pointed out for some boundary cases..

Title: Towards dynamical modelling of broadcast and localisation in wireless network sensors

Speaker: Pierre Leone (Geneva)

Related Workpackage: WP1, WP5

Abstract: In the following we describe models for the broadcast and localisation processes in wireless network sensors. The networks we consider are made up of wireless sensors equiped with directional antenna allowing directional transmission of datas inside of sector of disk. The region of the space covered by an emitting sensor is described with radius $r$ and angle $\alpha$. The radius expresses how far can emit the sensor and the angle expresses directionality. We consider a region of the space of unit area in which are thrown out randomly $N$ sensors with a uniform distribution. Models have to take into account possible collisions. Because of the hardware ressources, collisions cannot be detected. Models assume that the events, reception or transmission, occur at discrete time $n=0,1,2,\ldots$.

We start by considering the modelisation of the broadcast. Consider a particular sensor which desires to send datas through the entire network. The process we consider is the following : The sensor sends the datas at time $n=0$. Each sensors receiving datas propagate them through the network transmitting at time $n=1$. The process go on indefinitely or stop because nobody receive any datas. The model would be helpful to evaluate important parameters of the network such that the number of sensors to ensure full broadcast (dependant on the caracteristics of the sensors $\alpha$, $r$).

The model is based on the observation that $p=\frac{1}{2}\alpha r^2$ is the probability that a given sensor belongs to the area covered by an emitting sensor. So, if we assume that at time $n$ we have $Z_n$ emitting sensors the probability that a given sensor receives the datas from one and only one emitting sensor (without any collisions) is $p q^{Z_n-1}$. If we inroduce $X_i$, $i=1,\ldots,Z_n$ the random varaiables counting the number of sensors receiving datas, without collisions, from emitting sensor $i$ we get
\begin{equation}\label{znmodel}
Z_{n+1}=\sum_{i=1}^{Z_n} X_i.
\end{equation}
Random variables $X_i$ depend on time $n$ but this is not explicit in the notation to simplify. At time $n$ we have $X_i\sim B(N,p q^{Z_n-1})$ and then $Z_{n+1}\sim B(N Z_n, pq^{Z_n-1})$. Although $Z_{n+1}$ can be greater than $N$ we can prove that this does not happen with high probability (the probability that this happen is ${\cal O}(\frac{1}{N^c})$ with $c>0$ a constant) and so the model is meanigful.

Let us now introduce
\begin{equation*}
M_n=\frac{Z_n}{(\frac{N p}{q})^n q^{Z_0+Z_1+\ldots+Z_{n-1}}}.
\end{equation*}
We can show that $M_n$ is a martingale with respect to the $\sigma-$algebra generated by random variables $Z_1,\ldots, Z_{n-1}$. The martingale is ($L^1$) bounded, positive and so converges. This observation implies that in case of convergence to a non-zero values of $M_n$, the stochastic process $\bigl(Z_n\bigr)_{n\ge 0}$ can be seen as a random perturbation of the dynamical system described by
\begin{equation}\label{ds}
\tilde Z_{n+1} = \frac{N p}{q} \tilde Z_n q^{\tilde Z_n}.
\end{equation}
The dynamical systems $(\ref{ds})$ shows interesting qualitative behaviors depending on $p$. It can be shown that a cycle appears for $p$ large enough and this seems to survice random perturbations in the sense that the behavior is also observed on numerical experiments of $(\ref{znmodel})$.

The model we introduce for the modelisation of the localisation process is based on previous work in Geneva. Numerical experiments were presented which were supporting the idea of modelling the network using binomial distribution and independance of the sensors. 

Further work will consider simulation of the wireless network in order to make explicit the qualitative behaviors forecasted with our model. We hope such experiments will lead to confirmation of the model or give ways how to modify it.

Title: Simple On-line Algorithms for Call Control in Cellular Networks

Speaker: Evi Papaioannou (UoP)

Coauthors: Ioannis Caragiannis (UoP), Christos Kaklamanis (UoP)

Related workpackage: WP1

Abstract: We address an important communication issue arising in wireless cellular networks that utilize Frequency Division Multiplexing (FDM) technology. In such networks, many users within the same geographical region (cell) can communicate simultaneously with other users of the network using distinct frequencies. The spectrum of the available frequencies is limited; thus, efficient solutions to the call control problem are essential. The objective of the call control problem is, given a spectrum of available frequencies and users that wish to communicate, to maximize the benefit, i.e., the number of users that communicate without signal interference. We consider cellular networks of distance reuse $k\geq 2$ and we study the on-line version of the problem using competitive analysis. 

In cellular networks of distance reuse 2, the previously best known algorithm that beats the lower bound of $3$ on the competitiveness of deterministic algorithms works on networks with one frequency, achieves a competitive ratio against oblivious adversaries which is between $2.469$ and $2.651$, and uses a number of random bits at least proportional to the size of the network. We significantly improve this result by presenting a series of simple randomized algorithms that have competitive ratios significantly smaller than $3$, work on networks with arbitrarily many frequencies, and use only a constant number of random bits or a comparable weak random
source. The best competitiveness upper bound we obtain is $7/3$. 

In cellular networks of distance reuse $k>2$, we present simple randomized on-line call control algorithms with competitive ratios which significantly beat the lower bounds on the competitiveness of deterministic ones and use only $O(\log k)$ random bits. Furthermore, we show a new lower bound on the competitiveness of on-line call control algorithms in cellular networks of distance reuse $k\geq 5$.

Title: Sharing The Cost of Multicast Transmissions in Wireless Networks

Speaker: Carmine Ventre (UNISA)

Coauthors: Paolo Penna (UNISA)

Related workpackage: WP1, WP2

Abstract: We investigate the problem of sharing the cost of a multicast transmission in a wireless network where each node (radio station) of the network corresponds to a (set of) user(s) potentially interested in receiving the transmission. As in the model considered by Feigenbaum \emph{et al} [2001], users may act \emph{selfishly} and report a false "level of interest'' in receiving the transmission trying to be charged less by the system. We consider the issue of designing so called \emph{truthful mechanisms} for the problem of maximizing the \emph{net worth} (i.e., the overall "happiness'' of the users minus the cost of the transmission) for the case of \emph{wireless} networks. Intuitively, truthful mechanism guarantee that no user has an incentive in reporting a false valuation of the transmission. Unlikely the "wired'' network case, here the cost of a set of connections implementing a multicast tree is \emph{not} the sum of the single edge costs, thus introducing a complicating factor in the problem. We provide both positive and negative results on the existence of optimal algorithms for the problem and their use to obtain VCG truthful mechanisms achieving the same performances.

Title: Energy-Efficient Broadcasting in Ad-Hoc Networks: Combining MSTs with Shortest-Path Trees

Speaker: Paolo Penna (UNISA)

Coauthors: Carmine Ventre (UNISA)

Related workpackage: WP1, WP5

Abstract: We investigate the problem of constructing a multicast tree in *ad-hoc* networks. In particular, we address the issue of the *power consumption*, that is, the overall energy that the stations must spend to implement such a tree. We focus on two extreme cases of multicast: *broadcast* (one-to-all) and *unicast* (one-to-one). Minimum Spanning Trees (MSTs) and Shortest-Path Trees (SPTs) yield optimal solutions for broadcast and unicast, respectively. Unfortunately, they do not guarantee any optimality for the ``counterpart'', that is, MSTs are non-optimal for unicast, while SPTs are non-optimal for broadcast. 

In this work, we experimentally evaluate the performances of an algorithm combining MST solutions with SPT ones. Our approach is based on the construction of Light Approximate Shortest-path Trees (LASTs) of a given directed weighted graph, introduced by Khuller et al [1995]. LASTs approximate *simultaneously* the cost of the MST and the distances of the SPT rooted at a source node, thus yielding, also in the worst case, optimal solutions for both unicast and broadcast. Rather surprisingly, this ``compromise'' between MSTs and SPTs, has a very good performance w.r.t the broadcast tree obtained from a MST. Indeed, for randomly-generated instances, the broadcast tree obtained with LASTs is in some cases better (and never much worse) than the broadcast tree obtained from MSTs. This important fact shows that LASTs are not only interesting in theory, but they have practical relevant applications. Indeed, their use in our experiments also provides new insights on the approximation ratio of the MST broadcast algorithm for randomly-generated instances.

Title: A Combinatorial Approximation Algorithm for the Multicommodity Flow Problem

Speaker: Herve Rivano (UNSA/CNRS)

Coauthors: David Coudert (UNSA/CNRS), Jean-Francois Lalande (UNSA/CNRS)

Related workpackage: WP4, WP5

Abstract: This work is motivated by the need for approximation algorithms for the integral multicommodity flow problem which arise in numerous optimization scenarios, including the design of telecommunication networks. In a previous work, we have given an incremental randomized rounding algorithm using a sequence of fractional multicommodity flow computations. We show that a (1+e)-approximation of the fractional maximum multicommodity flow problem would not significantly affect the quality of the randomized rounding scheme. Moreover, combinatorial algorithms for approximate multicommodity flow exist in the literature and present the advantage of small memory requirement compared to linear programming.  We improve on one of the most efficient known algorithms by using dynamic shortest paths computations. We also present an incremental approach. This approach is not correctly analyzed but experimental results show a significant speed-up.

Title: How to Route and Tax Selfish Unsplittable Traffic

Speaker: Vincenzo Auletta (UNISA)

Coauthors: Roberto De Prisco (UNISA), Paolo Penna (UNISA), Pino Persiano (UNISA)

Related workpackage: WP2, WP3

Abstract: We study the problem of assigning unsplittable traffic to a set  of m links with different speeds so to minimize the maximum link congestion (i.e., the makespan).  We consider the case of *selfish agents* owning each piece of the traffic. In particular, we introduce a variant of the model by Koutsoupias and Papadimitriou [1999]  in which jobs cannot directly choose the link but can manipulate the system by reporting false  values to a \emph{scheduler} assigning the traffic to the links. 

We provide upper and lower bounds for the existence of a so called approximate *mechanism*, i.e., a scheduling algorithm and a payment function inducing a Nash equilibrium when all agents report their true values; in this case the algorithm computes an approximate solution.  Our positive results for $m$ identical links show the effectiveness of introducing such a scheduler since, in this case, $(1+\epsilon)$-approximate solutions are guaranteed in polynomial time. In contrast, the result by Koutzopias and Papadimitriou [1999] shows that, without payments and allowing selfish routing, Nash equilibria yield (in the worst case) $\Omega(\frac{\log m}{\log \log m})$-approximate solutions, even for unitary weighted traffic. Similar approximability results for identical machines have been achieved by Feldman \emph{et al} [2003]. However these results do not hold in our setting because their model assumes that the algorithm is provided with the correct traffic weights.

Title: The Power of Verification for One-Parameter Agents

Speaker: Paolo Penna (UNISA)

Coauthors: Vincenzo Auletta (UNISA), Roberto De Prisco (UNISA), Pino Persiano (UNISA)

Related workpackage: WP2, WP3

Abstract: We study combinatorial optimization problems involving one-parameter selfish agents. In particular, we show that, if agents can lie in one direction (that is they either overbid or underbid) then *any* (polynomial-time) c-approximation algorithm, for the optimization problem without selfish agents, can be turned into a (polynomial-time) $(c+\epsilon)$-approximation truthful mechanism, for any $\epsilon >0$.  

We apply these results to the $Q||C_max$ problem in the case of agents owning machines of different speeds. In this case, the agents bids can be \emph{verified} (only) if the corresponding machine receives at least one job. Using this property, we characterize the allocation algorithms A that admit a payment function P such that M=(A,P) is a truthful mechanism. In addition, we give a $(1+\epsilon)$-approximation truthful mechanism for $Q||C_max$ when machine speeds are bounded by a constant. The best previously known result for this problem is a randomized $(3+\epsilon)$-approximation mechanism due to Archer and Tardos [2001].  

Finally, we consider the classical scheduling problem $Q||\Sum w_j C_j$ which does not admit an exact mechanism if verification is not allowed. By contrast, we show that an exact mechanism for $Q||\Sum w_j C_j$ exists when verification is allowed.

Title: Energy-efficient broadcasting in ad hoc wireless networks: experimental results

Speaker: Ioannis Caragiannis (UoP)

Coauthors: Stavros Athanassopoulos (UoP), Christos Kaklamanis (UoP) and Panagiotis Kanellopoulos (UoP)

Related workpackage: WP1, WP5

Abstract: Algorithms for computing broadcast trees of minimum energy in ad hoc wireless networks usually start with a trivial tree containing the root node which grows to a spanning tree by including at each step a structure covering previously uncovered nodes which minimizes a measure related to energy. This structure may be an edge of minimum energy in MST-based algorithms, an edge of minimum incremental energy in BIP, a star of minimum average energy per new covered node in BAIP, a minimum energy path in shortest path-based algorithms, etc. The aim of our work is to investigate which is the best structure to add at each step and according to which optimization criterion. 

We present the implementation of some new algorithms for computing broadcast trees and compare their efficiency to known algorithms with respect to the energy consumption. In addition to the well-known algorithms MST, BIP, SPT, and BAIP, we have implemented a new algorithm called DSPF (Densest Shortest Path First), and two algorithms which utilize the ``potential power saving idea'': the recently proposed algorithm SP3SF based on growing the tree by adding paths at each step which minimize the additional power minus the potential power saving, and the new algorithm DSP3SF which selects paths of minimum average additional energy (taking potential power savings into account). We have run several implementations of our algorithms by adjusting their parameters. Our experimental results on randomly generated networks on the euclidean plane indicate that algorithm DSP3SF is superior to all known algorithms while DSPF is superior to all known algorithms which do not utilize the potential power saving idea.