1st CRESCCO WORKSHOP
SANTORINI, GREECE, 4.6.2003-6.6.2003
List of Presentation Abstracts
Title: EnergyEfficient Wireless Network Design
Speaker: Panagiotis Kanellopoulos (UoP)
Coauthors: Ioannis Caragiannis (UoP) and Christos Kaklamanis (UoP)
Related workpackage: WP1
Abstract: A crucial issue in ad hoc wireless networks is to efficiently support communication patterns that are typical in traditional (wired) networks. These include broadcasting, multicasting, and gossiping (alltoall communication). Since, in ad hoc networks energy is a scarce resource, the important engineering question to be solved is to guarantee a desired communication pattern minimizing the total energy consumption. Motivated by this question, we study a series of wireless network design problems and present new approximation algorithms and inapproximability results.
Title: On the Approximation Ratio of the MSTbased Heuristic for the EnergyEfficient Broadcast Problem in Static AdHoc Radio Networks
Speaker: Gianluca Rossi (Rome)
Coauthors: Andrea Clementi (Rome), Gurvan Huiban (Rome), Paolo Penna (UNISA), and Yann Verhoeven (Rome)
Related workpackage: WP1
Abstract: We present a technique to evaluate the approximation ratio on random instances of the Minimum Energy Broadcast Problem in AdHoc Radio Networks which is known to be NPhard and approximable within 12. Our technique relies on polynomial-time computable lower bound on the optimal cost of any instance. The main result of this paper is that the approximation ratio has never achieved a value greater than 6.4. Furthermore, the worst values of this ratio are achieved for small network sizes. We also provide a clear geometrical motivation of such good approximation results.
Title: The Minimum Broadcast Range Assignment Problem on Linear MultiHop Wireless Networks
Speaker: Andrea Clementi (Rome)
Coauthors: Miriam Di Ianni (Rome)
Related workpackage: WP1
Abstract: Given a set N of radio stations located on an Euclidean space, a source station s, and an integer h (1£ h £|N|-1), the Minimum BoundedHop Broadcast Range Assignment problem consists in finding a range assignment for N of minimum total power consumption that allows broadcast operations from s to every station in N in at most h hops. The problem is known to be NPhard on ddimensional spaces for any d³ 2 and some efficient approximation algorithms have been proposed in the literature. In this paper, we address the case in which the stations are arbitrarily located along a line (i.e., the linear case). We provide the first polynomialtime algorithm that returns an optimal solution for any instance of the linear case. The algorithm works in O(h|N| 2 ) time.
Title: Algorithms and Experiments on Colouring Squares of Planar Graphs
Speaker: Maria Andreou (CTI)
Coauthors: Sotiris Nikoletseas and Paul Spirakis (CTI)
Related workpackage: WP1
Abstract: In this work we study the important problem of colouring squares of planar graphs (SQPG). We design and implement two new algorithms that colour in a different way SQPG. We call these algorithms MDsatur and RC. We have also implemented and experimentally evaluated the performance of most of the known approximation colouring algorithms for SQPG. We compare the quality of the colourings achieved by these algorithms, with the colourings obtained by our algorithms and with the results obtained from two wellknown greedy colouring heuristics. The heuristics are mainly used for comparison reasons and unexpectedly give very good results. Our algorithm MDsatur outperforms the known algorithms as shown by the extensive experiments we have carried out.
The planar graph instances whose squares are used in our experiments are "nonextremal" graphs obtained by LEDA and hard colourable graph instances that we construct. The most interesting conclusions of our experimental study are: 1) all colouring algorithms considered here have almost optimal performance on the squares of "nonextremal"' planar graphs. 2) all known colouring algorithms especially designed for colouring SQPG, give significantly better results, even on hard to colour graphs, when the vertices of the input graph are randomly named. On the other hand, the performance of our algorithm, MDsatur, becomes worse in this case, however it still has the best performance compared to the others. MDsatur colours the tested graphs with 1,1 OPT colours in most of the cases, even on hard instances, where OPT denotes the number of colours in an optimal colouring. 3) we construct worst case instances for the algorithm of Fotakis et al., which show that its theoretical analysis is tight.
Title: Radiocolorings in Periodic Planar Graphs: PSPACECompleteness and Efficient Approximations for the Optimal Range of Frequencies
Speaker: Viki Papadopoulou (CTI)
Coauthors: Dimitris Fotakis (MPI), Sotiris Nikoletseas (CTI), and Paul Spirakis (CTI)
Related workpackage: WP1
Abstract: The Frequency Assignment Problem (FAP) in radio networks is the problem of assigning frequencies to transmitters exploiting frequency reuse while keeping signal interference to acceptable levels. The FAP is usually modelled by variations of the graph coloring problem. The Radiocoloring (RC) of a graph G(V, E) is an assignment function F: V®N such that |F(u)-F(v)|³ 2, when u, v are neighbors in G, and |F(u)-F(v)|³ 1 when the distance of u; v in G is two. The range of frequencies used is called span. Here, we consider the optimization version of the Radiocoloring Problem (RCP) of finding a radiocoloring assignment of minimum span, called min span RCP. In this paper, we deal with a variation of RCP: that of satisfying frequency assignment requests with some periodic behavior. In this case, the interference graph is an (infinite) periodic graph. Infinite periodic graphs model finite networks that accept periodic (in time, e.g. daily) requests for frequency assignment. Alternatively, they may model very large networks produced by the repetition of a small graph.
A periodic graph G is defined by an infinite two-way sequence of repetitions of the same finite graph Gi (Vi, Ei ). The edge set of G is derived by connecting the vertices of each iteration Gi to some of the vertices of the next iteration Gi+1, the same for all Gi . The model of periodic graphs considered here is similar to that of periodic graphs in Orlin [STOC'81], Marathe et al [J. Comp.'98]. We focus on planar periodic graphs, because in many cases real networks are planar and also because of their independent mathematical interest. We give two basic results:
Title: Modeling Dynamic Networks with Evolving Graphs, and Algorithms
Speaker: Afonso Ferreira (CNRS/UNSA)
Coauthors: Sandeep Bhadra, Binh BuiXuan, and Aubin Jarry (CNRS/UNSA)
Related workpackage: WP1
Abstract: The technologies deployed in communication networks are plenty, different, and in constant evolution. Most of the time, studying specific solutions geared for each innovation leads to the systematic recycling of the same basic algorithmic techniques, to the detriment of advances both in research and engineering. One way to avoid this pitfall is to work on unifying questions, based on relevant structural and algorithmic modeling of networking problems. As an example, very general combinatorial structures, as graphs, allowed researchers to take into account the main characteristics of classic networks in order to study fundamental algorithmic problems like shortest paths and flow networks. With respect to dynamic networks, their variations over time are unfortunately hard to be effectively captured in a classical graph model. In this talk we propose a new graph theoretical tool the evolving graphs , which helps to model the changes undergone by a network over time. We show how to compute and formally analyze least cost journeys (the analog of paths in usual graphs) in a class of dynamic networks, with link transmission delays. Cost measures investigated here are hop count (shortest journeys), arrival date (foremost journeys), and time span (fastest journeys). We also show how to compute multicast trees with minimum overall transmission time. We first show that computing different types of strongly connected components in evolving digraphs is NP Complete, and then propose an algorithm to build all rooted directed minimum spanning trees in strongly connected dynamic networks.
Title: A Brief Introduction to Sensor Networks
Speaker: Jose Rolim (Geneva)
Related workpackage: WP1
Abstract: We give an introduction to sensor networks. These networks belong to the category of (static) ad hoc wireless networks and are composed of a large numbers of extremely small sensing and communication devices. We discuss current sensor technologies (radio vs. laser) and their advantages and limitations, present real prototypes of sensors, and explain how these devices can be used. We outline the fundamental properties of sensor networks using standard models of distributed computation and propose several interesting foundational and engineering questions (energy efficiency, routing, coverage, etc.). For basic problems like broadcasting and coverage, we report interesting simulation results.
Title: Deterministic Truthful Approximation Mechanisms for Scheduling Related Machines
Speaker: Paolo Penna (UNISA)
Coauthors: Vincenzo Auletta, Roberto De Prisco, Paolo Penna, and Pino Persiano (UNISA)
Related workpackage: WP2, WP3
Abstract: We consider the problem of scheduling jobs on parallel related machines owned by selfish agents. We provide deterministic polynomial time (2+epsilon) approximation algorithms and suitable payment functions that yield truthful mechanisms for several NP-hard restrictions of this problem. Up to our knowledge, our result is the first non trivial polynomial time deterministic truthful mechanism for this NP-hard problem. Our result also yields a family of deterministic polynomial time truthful (4+epsilon) approximation mechanisms for any fixed number of machines. The only previously known mechanism for this problem (proposed by Archer and Tardos [FOCS 2001]) is randomized and truthful under a weaker notion of truthfulness. To obtain our results we introduce a technique to transform the PTAS by Graham into a deterministic truthful mechanism.
Title: Scheduling Selfish Jobs on Related Machines (selfish routing vs payment schemes)
Speaker: Vincenzo Auletta (UNISA)
Coauthors: Vincenzo Auletta, Roberto De Prisco, Paolo Penna, and 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 as 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 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 solutions. 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 Koutsoupias and Papadimitriou [1999] shows that, without payments and allowing selfish routing, Nash equilibria yield (in the worst case) Omega(log n / log log n ) approximate solutions, even for unitary weighted traffic. Although similar approximability results for identical machines have been achieved by Feldman et al [2003], their model assumes that the algorithm is provided with the correct traffic weights, thus not applying to our case and explain how these devices can be used. We outline the fundamental properties of sensor networks using standard models of distributed computation and propose several interesting foundational and engineering questions (energy efficiency, routing, coverage, etc.). For basic problems like broadcasting and coverage, we report interesting simulation results.
Title: Scheduling parallel jobs on networks
Speaker: Guochuan Zhang (CAU)
Coauthors: Klaus Jansen (CAU) and Deshi Ye (Zhejiang University)
Related workpackage: WP3
Abstract: We consider a parallel computer system with an interconnection topology, such as PRAMs, Lines and Meshes. Several processors can execute a job simultaneously if they are connected in the underlying network. A parallel job requires a fixed number of processors or a specified subsystem of a certain size for its execution at a time. Our goal is to assign the parallel jobs to the processors so that the makespan is minimized or the throughput is maximized. In many cases parallel job scheduling is related to rectangle packing. Steinberg [SIAM J Computing 26, 401-409, 1997] gave a sufficient condition to determine if a number of rectangles can be packed into a rectangular bin. We make a further extension of his theorem and apply it to several parallel job scheduling problems. We either improve the previous results or obtain some new results.
Title: Combinatorial techniques for memory power state scheduling in energyconstrained systems
Speaker: Claude Tadonki (Geneva)
Coauthors: Mitali Singh (University of Southern California), Jose Rolim (Geneva) and Viktor K. Prasanna (University of Southern California)
Related workpackage: WP3
Abstract: Energy has emerged as a critical constraint for a large number of portable, wireless devices. For data intensive applications, a significant amount of energy is dissipated in the memory. Advanced memory architectures support multiple power states of memory banks, which can be exploited to reduce energy dissipation in the system. We present a general methodology using combinatorial graph scheduling techniques, which can be used for obtaining efficient memory power management schedules for algorithms. Additional techniques like tiling further improve the efficiency of our approach. We demonstrate the efficiency of our techniques by designing and simulating optimal memory management schedules for two well known algorithms, Transitive Closure and Fast Fourier Transform. Our simulation results show that we can obtain over 98% energy reduction in the memory energy for Transitive Closure using our methodology.
Title: Scheduling Multicast Traffic in Star Coupled WDM LANs: The Open Block Problem
Speaker: Aleksei Fishkin (CAU)
Coauthors: Alexander Ageev (Sobolev Institute), Alexander Kononov (University of Taiwan), and Sergey Sevastianov (Sobolev Institute)
Related workpackage: WP3, WP4
Abstract: Wavelength Division Multiplexing (WDM) is the current favorite technology for building optical communication networks. WDM supports multiple wavelengths (channels) on a single fiber. In broadcast WDM local area networks (LANs), where all nodes are combined using a passive star coupler, information transmitted on any channel is broadcast to the entire set of nodes, but it is only received by those with a receiver listening on that channel. This broadcast future makes it possible to design scheduling algorithms such that a single transmission of a multicast packet can reach all nodes in the packet's destination set simultaneously. In two basic cases, the problem of scheduling multicast traffic in Star Coupled WDM LANs can be modeled as the multiprocessor dedicated task scheduling problem and the open shop problem. Here, considering the general case, we introduce a new scheduling problem, called the open block problem. We derive a number of polynomial time solvable cases, provide hardness results, and present several approximation algorithms.
Title: Traffic Grooming in WDM Networks
Speaker: Michel Syska (CNRS/UNSA)
Coauthors: JeanClaude Bermond, O. de Rivoyre, and Stephane Perennes (CNRS/UNSA)
Related workpackage: WP4
Abstract: We address the problem of traffic grooming in WDM networks. For rings networks with all-to-all uniform unitary traffic we optimally solve the problem for practical values and infinite congruence classes of values for given grooming ratio. For networks with arbitrary topology we introduce the model of pipes and provide bounds for the all to all traffic.
Title: Approximate Path Coloring with Applications to Wavelength Assignment in WDM Optical Networks
Speaker: Ioannis Caragiannis (UoP)
Coauthors: Christos Kaklamanis (UoP)
Related workpackage: WP4
Abstract: Motivated by the wavelength assignment problem in WDM optical networks, we study path coloring problems in graphs. Given a set of paths P on a graph G, the path coloring problem is to color the paths of P so that no two paths traversing the same edge of G are assigned the same color and the total number of colors used is minimized. The problem has been proved to be NP hard even for trees and rings. Using optimal solutions to fractional path coloring, a natural relaxation of path coloring, on which we apply a randomized rounding technique combined with existing coloring algorithms, we obtain new upper bounds on the minimum number of colors sufficient to color any set of paths on any graph. The upper bounds are either existential or constructive. The existential upper bounds are significantly better than existing ones provided that the cost of the optimal fractional path coloring is sufficiently large and the dilation of the set of paths is small. Our algorithmic applications include improved approximation algorithms for path coloring in rings and bidirected trees. Our results extend to variations of the original path coloring problem arizing in multifiber WDM optical networks.