Vincenzo Auletta, Roberto De Prisco, Paolo Penna and Giuseppe Persiano:
"On Designing Truthful Mechanisms for Online Scheduling"
Abstract: We study the *online* version of the scheduling problem involving
*selfish agents* considered by Archer and Tardos [FOCS 2001]: jobs
must be scheduled on $m$ parallel related machines, each of them
owned by a different *selfish agent*.
Our study focuses on general techniques to translate
approximation/competitive algorithms into equivalent
approximation/competitive *truthful mechanisms*.
Our results show that this translation is more problematic in the
online setting than in the offline one. For $m=2$, we develop an
offline and an online ``translation'' technique which, allow to obtain
$f(\rho)$-approximation/competitive (polynomial-time) mechanism
starting from *any* $\rho$-approximation/competitive
(polynomial-time) algorithm, with $f(\rho)= \rho(1+\epsilon)$ in the
offline case, for every $\epsilon >0$. By contrast, one of our lower
bounds implies that, in general, online $\rho$-competitive
algorithms cannot be turned into $\rho(1+ \epsilon)$-competitive
mechanisms, for some $\epsilon>0$ and every $m\geq 2$.
We also investigate the issue of designing new online algorithms
from scratch so to obtain efficient competitive mechanisms, and
prove some lower bounds on a class of ``natural'' algorithms.
Finally, we consider the variant introduced by Nisan and Ronen [STOC
1999] in which machines can be *verified*. For this model, we give a
$O(1)$-competitive online mechanism for *any* number of machines and
prove that some of the above lower bounds can be broken.
Amos Beimel:
"On Private Computation in Incomplete Networks"
Abstract: Suppose that some parties are connected by an incomplete network of reliable and private channels. The parties cooperate to execute some protocol. However, the parties are curious -- after the protocol terminates each processor tries to learn information from the communication it heard. We say that a function can be computed privately in a network if there is a protocol in which each processor learns only the information implied by its input and the output of the protocol. The question we address in this paper is what functions can be computed privately in a given incomplete network. It is known that if a network is 2-connected then every pair of parties can communicate privately. Thus, the question is intersting only for non-2-connected networks. We first characterize the functions that can be computed privately in simple networks -- networks with one separating vertex and two 2-connected components. We then deal with private computations in arbitrary networks: we reduce this question to private computations of related functions on trees, and give sufficient and necessary conditions on the functions that can be computed privately on trees.
Jean-Claude Bermond and Laurent Braud and David Coudert:
"Traffic Grooming on the Path"
Abstract: In a WDM network, routing a request consists in assigning it a route in the physical network and a wavelength. If each request uses at most 1/C of the bandwidth of the wavelength, we will say that the grooming factor is C. That means that on a given edge of the network we can groom (group) at most C requests on the same wavelength. With this constraint the objective can be either to minimize the number of wavelengths (related to the transmission cost) or minimize the number of Add Drop Multiplexer (shortly ADM) used in the network (related to the cost of the nodes). Here we consider the case where the network is a path on N nodes, P_N. Thus the routing is unique. For a given grooming factor C minimizing the number of wavelengths is an easy problem, well known and related to the load problem. But minimizing the number of ADM's is NP-complete for a general set of requests and no results are known. Here we show how to model the problem as a graph partition problem and using tools of design theory we completely solve the case where C=2 and where we have a static uniform all-to-all traffic (requests being all pairs of vertices).
Davide Bilo, Guido Proietti:
"Range Augmentation Problems in Static Ad-Hoc Wireless Networks"
Abstract: Given a set $V$ of $n$ stations, a transmission power cost function
$c:V\times V\mapsto \mathbb{R^+}\cup\{+\infty\}$, an initial power
assignment $p_0: V\mapsto \mathbb{R^+}$, and a connectivity property
$\pi$, a \emph{range augmentation problem} consists of finding a
minimum power augmentation assignment $p$ such that
$p_f(\cdot)=p_0(\cdot)+p(\cdot)$ satisfies property $\pi$. In this
paper, we focus on the problem of increasing the connectivity of an
already existing connected network, to make it resilient to the
failure of either a wireless link or a station. For these problems
we give a ${\cal H}^2_n$-approximation greedy algorithm (where
${\cal H}_n$ is the $n$-th harmonic number) after proving that they
are both not approximable within $(1- o(1))\ln n$, unless
NP $\subset$ DTIME$(n^{{\cal O}(\log\log n)})$, even when $c$ is a
distance cost function restricted to three power levels, or it is a
distance cost function and $p_0$ induces a tree network. Moreover,
we prove that both problems remain APX-hard even if the initial
power assignment is uniform. In this latter scenario, we finally
show that any $\lambda$-approximation algorithm for the
corresponding problem in wired networks, is a $2\lambda$-approximation algorithm for the wireless case.
Tiziana Calamoneri and Paola Vocca:
"On the Approximability of the $L(h,k)$-Labelling"
Abstract: Given an undirected graph $G$, an \Lhk\ of $G$ assigns colors to
vertices from the integer set $\{0, \ldots,\lambda_{h,k}\}$, such
that any two vertices $v_i$ and $v_j$ receive colors $c(v_i)$ and
$c(v_j)$ satisfying the following conditions: \emph{i)} if $v_i$
and $v_j$ are adjacent then $|c(v_i)-c(v_j)|\geq h$; \emph{ii)} if
$v_i$ and $v_j$ are at distance two then
$|c(v_i)-c(v_j)|\geq k$.
The aim of the \Lhk\ problem is to minimize $\lambda_{h,k}$.
In this paper we study the approximability of the \Lhk\ problem on
bipartite graphs and extend the results to $s$-partite and
general graphs. Indeed, the decision version of this problem is
known to be NP-complete in general and, to our knowledge, there
are no polynomial solutions, either exact or approximate, for
bipartite graphs.
Here, we state some results concerning the approximability of the
\Lhk\ problem for bipartite graphs, exploiting a novel technique,
consisting in computing approximate vertex- and edge-colorings of
auxiliary graphs to deduce an $L(h,k)$-labelling for the input
bipartite graph. We derive an approximation algorithm with
performance ratio bounded by $\frac{4}{3} D^2$, where, $D$ is
equal to the minimum even value bounding the minimum of the
maximum degrees of the two partitions.
One of the above coloring algorithms is in fact an approximating
edge-coloring algorithm for hypergraphs of maximum dimension $d$,
i.e. the maximum edge cardinality, with performance ratio $d$.
Furthermore, we consider a different approximation
technique based on the reduction of the \Lhk\ problem to the
vertex-coloring of the square of a graph. Using this approach we
derive an approximation algorithm with performance ratio bounded
by $\mbox{min}(h,2k)\sqrt{n}+o(k\sqrt{n})$, assuming $h \geq k$.
Hence, the first technique is competitive when $D=O(n^{1/4})$.
We then extend the latter approximation strategy to $s$-partite
graphs, obtaining an
$(\mbox{min}(h,sk)\sqrt{n}+o(sk\sqrt{n}))$-approximation ratio,
and to general graphs deriving an
$(h\sqrt{n}+o(h\sqrt{n}))$-approximation algorithm, assuming
$h\geq k$.
Finally, we prove that the \Lhk\ problem is not easier than
coloring the square of a graph.
Ioannis Caragiannis, Aleksei V. Fishkin, Christos Kaklamanis, Evi Papaioannou:
"A tight bound for online coloring of disk graphs"
Abstract: We present an improved upper bound on the competitiveness of the
online coloring algorithm {\sf First-Fit} in disk graphs which are
graphs representing overlaps of disks on the plane. We also show
that this bound is best possible for deterministic online coloring
algorithms that do not use the disk representation of the input
graph. We also present a related new lower bound for unit disk
graphs.
A. Clementi, M. Di Ianni, M. Lauria, A. Monti , G. Rossi, R. Silvestri:
"Divide et Impera is almost optimal for the bounded-hop MST problem on random Euclidean instances"
Abstract: The \ghmstd{h} problem is defined as follows: Given a
set $S$ of points in the $d$-dimensional Euclidean space and
$\root \in S$, find a minimum-cost spanning tree for $S$ rooted
at $\root$ with height at most $h$. We investigate the problem for
any constants $h$ and $d>0$. We prove the first non trivial lower
bound on the solution cost \emph{for almost all} Euclidean
instances (i.e. the lower-bound holds with hight probability).
Then we introduce an easy-to-implement, very fast divide et impera
heuristic and we prove that its solution cost matches the lower
bound.
Shantanu Das, Paola Flocchini, Amiya Nayak, Nicola Santoro:
"Distributed Exploration of an Unknown Graph"
Abstract: We consider a group of identical asynchronous agents, initially located at different nodes of an undirected simple graph. The nodes of the graph are unlabeled, and each contains a whiteboard where the visiting agents can write to and read from. The agents, initially, do not know the graph nor its topology. The only a-priori knowledge the agents may have is either the number $n$ of nodes, or the total number $k$ of agents. The goal is for the agents to construct a labelled map of the unknown graph, the same for all agents, so to be in complete agreement with each-other about their environment. This problem, called Labelled Map Construction, is closely related to a variety of other basic problems, including election and rendezvous. We are interested in efficient and generic protocols that can solve the problem, irrespective of the graph topology, where the cost of the algorithm is measured in terms of the total number of moves (or, edge traversals) made by the agents. We present a novel deterministic algorithm that, provided that $n$ and $k$ are co-prime (a necessary condition), constructs a map of the graph, elects a leader among the agents, and provides a unique labelling on the nodes of the graph. Our algorithm uses no more than $O(k\ m)$ edge traversals where $m$ is the number of edges in the graph. Our result improves on the finding by Barriere et al. for graphs with sense of direction, extending it to all labelled graphs, provided that one of $n$ or $k$ is known.
Yefim Dinitz and Noam Solomon:
"Two Absolute Bounds for Distributed Bit Complexity"
Abstract: The concept of distributed communication bit complexity
was introduced by Dinitz, Rajsbaum, and Moran.
They studied bit complexity of Consensus and Leader Election,
arriving at more or less exact bounds. This paper answers
two questions on Leader Election, which remained open.
The first is to close the gap between the known upper and lower bounds, for electing a leader by two linked processors.
The second is whether the known algorithm, sending
1.5n bits while electing a leader in a chain of even length n,
is optimal, in the case when $n$ is known to the processors.
For both problems, absolutely exact bounds are found.
Moreover, the lower bound proofs show that there is no
optimal algorithm other than the suggested one(s).
Stefan Dobrev, Jesper Jansson, Kunihiko Sadakane, Wing-Kin Sung:
"Finding Short Right-Hand-on-the-Wall Walks in Undirected Graphs"
Abstract: We consider the problem of {\em perpetual traversal} by a single
agent in an undirected graph $G$. Our requirements are: (1)
deterministic algorithm, (2) each node is visited within $O(n)$
moves, (3) the agent uses no memory, it can use only the label of
the link via which it arrived to the current node, (4) no marking of
the underlying graph is allowed and (5) no additional information is
stored in the graph (e.g. routing tables, spanning tree) except the
ability of each vertex to distinguish between the incident edges
(called {\em local orientation}). The traversal is {\em perpetual},
i.e. we do not require the algorithm to recognize that it has
already traversed the whole graph and that it can terminate.
This problem is unsolvable, as has been proven in \cite{Bu78, Rol80}
even for much less restrictive setting. Our approach is to somewhat
relax the requirement (5). We fix the following traversal algorithm:
{\em ``Start by taking the edge with the smallest label. Afterwards,
whenever you come to a node, continue by taking the successor edge
(in the local orientation) to the edge via which you arrived''} and
ask whether it is possible for any given undirected graph to assign
the local orientations in such a way that the resulting traversal
visits every node in $O(n)$ moves.
We give a positive answer to this question, by showing how to
construct such local orientations. This leads to an extremely
simple, memoryless, yet efficient traversal algorithm.
Pierre Fraigniaud, David Ilcinkas, Sergio Rajsbaum, S\'ebastien Tixeuil:
"An $\Omega (\log n)$ space lower bound for graph exploration with stop (extended abstract)"
Abstract: We consider the task of exploring graphs with anonymous nodes by a team of non-cooperative robots modeled as finite automata. These robots have no \emph{a priori} knowledge of the topology of the graph, or of its size. Each edge has to be traversed by at least one robot. We first show that, for any set of $q$ non-cooperative $K$-state robots, there exists a graph of size $O(qK)$ that no robot of this set can explore. This improves the $O(K^{O(q)})$ bound by Rollik (1980). Our main result is an application of this improvement. It concerns exploration with stop, in which one robot has to explore and stop after completing exploration. For this task, the robot is provided with a pebble, that it can use to mark nodes. We prove that exploration with stop requires $\Omega(\log n)$ bits for the family of graphs with at most $n$ nodes. On the other hand, we prove that there exists an exploration with stop algorithm using a robot with $O(D \log \Delta)$ bits of memory to explore all graphs of diameter at most $D$ and degree at most $\Delta$.
Markus Hinkelmann, Andreas Jakoby:
"Communications in Unknown Networks: Preserving the Secret of Topology."
Abstract: Cryptography investigates security aspects of data distributed in a
network. This kind of security does not protect the secrecy of the
network topology against being discovered if some kind of
communication has to be established. But there are several scenarios
where even the network topology has to be a part of the secret. In
this paper we study the question of communication within a secret
network where all processing nodes of the network have only partial
knowledge (e.g.routing tables) of the complete topology. We introduce
a model for measuring the loss of security of the topology when
communication takes place. We will investigate lower bounds on the
knowledge that can be deduced from the communication string. Several
kinds of routing tables are not sufficient to guarantee the secrecy of
topology. On the other hand, if a routing table allows to specify the
direction from which a message is coming from we can run a protocol
solving the all-to-all communication problem such that no processing
node can gain additional knowledge about the network. Finally, we
investigate the problem, whether a knowledge base can be generated
from local knowledge of the processing nodes without losing the state
of secrecy. It will be shown that this is not possible for static
networks and most kinds of dynamic networks.
Taisuke Izumi and Toshimitsu Masuzawa:
"An Improved Algorithm for Adaptive Condition-Based Consensus"
Abstract: Condition-Based Approach studies restrictions on the inputs of a
distributed problem, called conditions, to circumvent several
impossibility results. Especially, for the synchronous consensus
problem, the relation between conditions and time complexity bounds
has been studied. In our previous work, we introduced adaptiveness on
time complexity of the condition-based approach, and established the
adaptive condition-based approach: It classifies all possible input
vectors into the hierarchical sequence of conditions according to
their difficulty called legality level. For such hierarchy, adaptive
algorithms achieve time complexity depending on the legality level of
input vectors. In this paper, we propose an improved version of the
adaptive condition-based algorithms for synchronous consensus
that achives better time complexity than the previous one. On the
assumption that majority of processes are correct, the proposed
algorithm terminates within $\min\{f + 2, t+ 1\} - l$ rounds if
$l < f$, where $f$ and $t$ is the actual and the maximum numbers of
faults respectively, and $l$ is the legality level of input vectors.
Moreover, the algorithm terminates in $1$ round if $l \geq t$ and
$f=0$, and terminates within $2$ rounds if $l \geq f$ holds.
Compared with our previous algorithm, the proposed algorithm improves
time complexity by one round in the case of $f = t$ and $l > f$.
Branislav Katreniak:
"Biangular circle formation by asynchronous mobile robots"
Abstract: Consider a community of simple autonomous robots (decentralized, asynchronous, no common coordinate system, no identities, no direct communication, no memory of the past, deterministic) moving freely in the plane and able to sense the positions of the other robots. We study the task of forming an absolutely symmetric formation -- regular circle. We do not reach this goal for all initial configurations, in general we form only a less symmetric formation -- biangular circle. Existing algorithms for similar tasks (forming a regular circle) are known only for stronger models (synchronous) and only converge to the final formation. In this paper we present an algorithm that solves the biangular circle formation problem deterministically in finite time.
Ralf Klasing, Euripides Markou, Tomasz Radzik, Fabiano Sarracco:
"Hardness and approximation results for black hole search in arbitrary graphs"
Abstract: A black hole is a highly harmful stationary process residing in a
node of a network and destroying all mobile agents visiting the
node, without leaving any trace. We consider the task of locating a
black hole in a (partially) synchronous arbitrary network, assuming
an upper bound on the time of any edge traversal by an agent. The
minimum number of agents capable to identify a black hole is two.
For a given graph and a given starting node we are interested in the
fastest possible black hole search by two agents. We prove that
finding a fastest black hole search scheme in an arbitrary graph is
NP-hard, thus solving an open problem stated in \cite{CKMP04}.
We also give a $39/11$-approximation algorithm for this problem,
thus improving on the 4-approximation scheme observed in \cite{CKMP04}.
Finally, we show that any black hole search scheme that explores the
given input graph via some spanning tree cannot have an approximation
ratio better than 3/2. Note that black hole search schemes based on
spanning trees represent a very natural class of algorithms; our new
algorithm also belongs to this class. We believe that more general
classes of algorithms will be very
difficult to analyze.
Rastislav Kralovic, Richard Kralovic:
"On Semi-perfect 1-factorizations"
Abstract:
The perfect 1-factorization conjecture by A. Kotzig [K63] asserts the existence of
a 1-factorization of a complete graph K2n in which any two 1-factors induce
a Hamiltonian cycle. This conjecture is one of the prominent open problems in graph theory.
Apart from its theoretical significance it has a number of
applications, particularly in designing topologies for wireless communication.
Recently, a weaker version of this conjecture has been proposed
for the case of semi-perfect 1-factorizations.
A semi-perfect 1-factorization is a decomposition of a graph G into distinct
1-factors F1,...,Fk such that F1 U Fi
forms a Hamiltonian cycle for any 1<i≤k.
We show that complete graphs K2n, hypercubes Q2n+1 and tori
T2n x 2n admit
a semi-perfect 1-factorization.
Paolo Penna and Carmine Ventre:
"Free-riders in Steiner tree cost-sharing games"
Abstract: We consider cost-sharing mechanisms for the Steiner tree game. In
this well-studied *cooperative* game, each *selfish* user expresses
his/her willingness to pay for being connected to a source node $s$
in an underlying graph. A *mechanism* decides which users will be
connected and divides the cost of the corresponding (optimal)
Steiner tree among these users (*budget balance* condition). Since
users can form *coalitions* and misreport their willingness to pay,
the mechanism must be *group strategyproof*: even coalitions of
users cannot benefit from lying to the mechanism.
We present new *polynomial-time* mechanisms which satisfy a standard
set of axioms considered in the literature (i.e., budget balance,
group strategyproofness, voluntary participation, consumer
sovereignty, no positive transfer, cost optimality) and consider the
*free riders* issue recently raised by Immorlica et al. [SODA 2005]:
it would be desirable to avoid users that are connected for free. We
also provide a number of negative results on the existence of
*polynomial-time* mechanisms with certain guarantee on the number of
free riders. Finally, we extend our technique and results to a
variant considered by Bilò et al. [SPAA 2004] with applications to
*wireless* multicast cost sharing.
Giuseppe Prencipe:
"On The Feasibility of Gathering by Autonomous Mobile Robots"
Abstract: Given a set of $n$ autonomous mobile robots that can freely move on a two dimensional
plane, they are required to gather in a position of the plane not fixed in advance
(\gatheringP).
The main research question we address in this paper is: under which conditions this task
can be accomplished by the robots?
The studied robots are quite simple: they are anonymous, totally asynchronous,
they do not have any memory of past computations, they cannot explicitly
communicate among each other.
We show that this simple task cannot be in general accomplished
by the considered system of robots.
Nicola Santoro, Peter Widmayer:
" Majority and Unanimity In Synchronous Networks With Ubiquitous Dynamic Faults"
Abstract: In this paper we are interested in synchronous distributed systems
subject to transient and ubiquitous failures. This includes systems
where failures will occur on {\em any} communication link, systems
where {\em every} processor will fail at one time or another, etc.,
and, following a failure, normal functioning can resume after a finite
(although unpredictable) amount of time. Notice that these cases cannot be handled by the traditional {\em component failure} models.
The model we use is the {\em transmission failure} model, known also
as the {\em dynamic faults} model. Using this model, we study the
fundamental problem of {\em agreement} in synchronous systems of
arbitrary topology. We establish bounds on the number of dynamic
faults that make any non-trivial form of agreement (even strong majority) impossible; in turn, these bounds express connectivity requirements which must be met to achieve any meaningful form of agreement. We also provide, constructively, bounds on the number of dynamic faults in spite of which any non-trivial form of agreement
(even unanimity) is possible. These bounds are shown to be tight for a large class of networks, that includes hypercubes, toruses, rings, and complete graphs; incidentally, we close the existing gap between possibility and impossibility of non-trivial agreement in complete graphs in presence of dynamic Byzantine faults. None of these results is derivable in the component failure models; in particular, all our {\em possibility} results hold in situations for which those models indicate {\em impossibility}.
Mordechai Shalom and Shmuel Zaks:
"Minimizing the Number of ADMs in SONET Rings with Maximum Throughput"
Abstract: SONET ADMs are dominant cost factors in WDM/SONET rings. Whereas
most previous papers on the topic concentrated on the number of
wavelengths assigned to a given set of lightpaths, more recent
papers argue that the number of ADMs is a more realistic cost
measure. The minimization of this cost factor has been
investigated in recent years, where single-hop and multi-hop
communication models, with arbitrary traffic and uniform traffic
loads have been investigated. As a first attempt to understand the
trade-off between the number of wavelengths and the number of
ADMs, we concentrate on the all-to-all, uniform traffic instance
with multi-hop, splittable communication. We look for a solution
which makes a full use of the bandwidth and uses the minimum
possible number of ADMs under this constraint. We develop an
architecture based on successive nested polygons and present a
necessary and sufficient condition for a solution in this
architecture to be feasible. This architecture leads to a solution
using $O(W \log W + N)$ ADMs (compared to $N W$ ADMs for the basic
architecture in \cite{GLS99}) which is optimal for $W=O(N/\log
N)$. We further improve this result to $O(W \log \overline{W} +
N)$ ADMs, where $\overline{W}=o(W)$.
Rui Wang, Francis C. M. Lau :
"OptimalGossiping in Square Meshes in All-Port Mode and with Short Packets"
Abstract: N/A
Mirjam Wattenhofer, Roger Wattenhofer, Peter Widmayer:
"Geometric Routing without Geometry"
Abstract: In this paper we propose a new routing paradigm,
called pseudo-geometric routing. In pseudo-geometric
routing, each node u of a network of computing elements is
assigned a pseudo coordinate composed of the graph (hop)
distances from u to a set of designated nodes (the
anchors) in the network. On theses pseudo coordinates we
employ greedy geometric routing. Almost as a side effect,
pseudo-geometric routing is not restricted to planar unit disk
graph networks anymore, but succeeds on general networks.
Back