Résumé | We introduce a variant of the deterministic rendezvous problem for a pair of
heterogeneous agents operating in an undirected graph, which differ in the time
they require to traverse particular edges of the graph. Each agent knows the
complete topology of the graph and the initial positions of both agents. The
agent also knows its own traversal times for all of the edges of the graph, but is
unaware of the corresponding traversal times for the other agent. The goal of the
agents is to meet on an edge or a node of the graph. In this scenario, we study the
time required by the agents to meet, compared to the meeting time T_OPT in the
offline scenario in which the agents have complete knowledge about each others
speed characteristics. When no additional assumptions are made, we show that
rendezvous in our model can be achieved after time O(n T_OPT) in a n-node graph,
and that such time is essentially in some cases the best possible. However, we
prove that the rendezvous time can be reduced to ?(T_OPT) when the agents
are allowed to exchange ?(n) bits of information at the start of the rendezvous
process. We then show that under some natural assumption about the traversal
times of edges, the hardness of the heterogeneous rendezvous problem can be
substantially decreased, both in terms of time required for rendezvous without
communication, and the communication complexity of achieving rendezvous in
time ?(T_OPT). |