In this work, we introduce the notion of time to some well-known combinatorial optimization problems. In particular, we study problems defined on temporal graphs. A temporal graph D=(V,A) may be ...viewed as a time-sequence G1,G2,…,Gl of static graphs over the same (static) set of nodes V. Each Gt=D(t)=(V,A(t)) is called the instance of D at time t and l is called the lifetime of D. Our main focus is on analogues of traveling salesman problems in temporal graphs. A sequence of time-labeled edges (e.g. a tour) is called temporal if its labels are strictly increasing. We begin by considering the problem of exploring the nodes of a temporal graph as soon as possible. In contrast to the positive results known for the static case, we prove that, it cannot be approximated within cn, for some constant c>0, in a special case of temporal graphs and within (2−ε), for every constant ε>0, in another special case in which D(t) is strongly connected for all 1≤t≤l, both unless P=NP. We then study the temporal analogue of TSP(1,2), abbreviated TTSP(1,2), where, for all 1≤t≤l, D(t) is a complete weighted graph with edge-costs from {1,2} and the cost of an edge may vary from instance to instance. The goal is to find a minimum cost temporal TSP tour. We give several polynomial-time approximation algorithms for TTSP(1,2). Our best approximation is (1.7+ε) for the generic TTSP(1,2) and (13/8+ε) for its interesting special case in which the lifetime of the temporal graph is restricted to n. In the way, we also introduce temporal versions of other fundamental combinatorial optimization problems, for which we obtain polynomial-time approximation algorithms and hardness results.
In this work we consider
temporal networks
, i.e. networks defined by a
labeling
λ
assigning to each edge of an
underlying graph
G
a set of
discrete
time-labels. The labels of an edge, which are ...natural numbers, indicate the discrete time moments at which the edge is available. We focus on
path problems
of temporal networks. In particular, we consider
time-respecting
paths, i.e. paths whose edges are assigned by
λ
a strictly increasing sequence of labels. We begin by giving two efficient algorithms for computing shortest time-respecting paths on a temporal network. We then prove that there is a
natural analogue of Menger’s theorem
holding for arbitrary temporal networks. Finally, we propose two
cost minimization parameters
for temporal network design. One is the
temporality
of
G
, in which the goal is to minimize the maximum number of labels of an edge, and the other is the
temporal cost
of
G
, in which the goal is to minimize the total number of labels used. Optimization of these parameters is performed subject to some
connectivity constraint
. We prove several lower and upper bounds for the temporality and the temporal cost of some very basic graph families such as rings, directed acyclic graphs, and trees.
In this work, we study protocols so that populations of distributed processes can
construct networks
. In order to highlight the basic principles of distributed network construction, we keep the ...model minimal in all respects. In particular, we assume
finite-state processes
that all begin from the same initial state and all execute the same protocol. Moreover, we assume
pairwise interactions
between the processes that are scheduled by a fair adversary. In order to allow processes to construct networks, we let them
activate
and
deactivate
their pairwise connections. When two processes interact, the protocol takes as input the states of the processes and the state of their connection and updates all of them. Initially all connections are inactive and the goal is for the processes, after interacting and activating/deactivating connections for a while, to end up with a desired
stable network
. We give protocols (optimal in some cases) and lower bounds for several basic network construction problems such as
spanning line
,
spanning ring
,
spanning star
, and
regular network
. The
expected time to convergence
of our protocols is analyzed under a
uniform random scheduler
. Finally, we prove several
universality
results by presenting generic protocols that are capable of simulating a Turing Machine (TM) and exploiting it in order to construct a large class of networks. We additionally show how to partition the population into
k
supernodes
, each being a line of
log
k
nodes, for the largest such
k
. This amount of local memory is sufficient for the supernodes to obtain unique names and exploit their names and their memory to realize nontrivial constructions.
We study theoretical models of programmable matter systems, consisting of n spherical modules kept together by magnetic or electrostatic forces and able to perform two minimal mechanical operations ...(movements): rotate and/or slide. The goal is for an initial shape A to transform to some target shape B by a sequence of movements. Most of the paper focuses on transformability (feasibility) questions. When only rotation is available, we prove that deciding whether two given shapes can transform to each other, is in P. Under the additional restriction of maintaining global connectivity, we prove inclusion in PSPACE and explore minimum seeds that can make otherwise infeasible transformations feasible. Allowing both rotations and slidings yields universality: any two connected shapes of the same order can be transformed to each other without breaking connectivity, in O(n2) sequential and O(n) parallel time (both optimal). We finally provide a type of distributed transformation.
We study the design of small cost temporally connected graphs, under various constraints. We mainly consider undirected graphs of
n
vertices, where each edge has an associated set of discrete ...availability instances (labels). A journey from vertex
u
to vertex
v
is a path from
u
to
v
where successive path edges have strictly increasing labels. A graph is temporally connected iff there is a (
u
,
v
)-journey for any pair of vertices
u
,
v
,
u
≠
v
. We first give a simple polynomial-time algorithm to check whether a given temporal graph is temporally connected. We then consider the case in which a designer of temporal graphs can
freely choose
availability instances for all edges and aims for temporal connectivity with very small
cost
; the cost is the total number of availability instances used. We achieve this via a simple polynomial-time procedure which derives designs of cost linear in
n
. We also show that the above procedure is (almost) optimal when the underlying graph is a tree, by proving a lower bound on the cost for any tree. However, there are pragmatic cases where one is not free to design a temporally connected graph anew, but is instead
given
a temporal graph design with the claim that it is temporally connected, and wishes to make it more cost-efficient by removing labels without destroying temporal connectivity (redundant labels). Our main technical result is that computing the maximum number of redundant labels is APX-hard, i.e., there is no PTAS unless
P
=
N
P
. On the positive side, we show that in dense graphs with random edge availabilities, there is asymptotically almost surely a very large number of redundant labels. A temporal design may, however, be
minimal
, i.e., no redundant labels exist. We show the existence of minimal temporal designs with at least
n
log
n
labels.
Resampling is a well-known statistical algorithm that is commonly applied in the context of Particle Filters (PFs) in order to perform state estimation for non-linear non-Gaussian dynamic models. As ...the models become more complex and accurate, the run-time of PF applications becomes increasingly slow. Parallel computing can help to address this. However, resampling (and, hence, PFs as well) necessarily involves a bottleneck, the redistribution step, which is notoriously challenging to parallelize if using textbook parallel computing techniques. A state-of-the-art redistribution takes O((log2N)2) computations on Distributed Memory (DM) architectures, which most supercomputers adopt, whereas redistribution can be performed in O(log2N) on Shared Memory (SM) architectures, such as GPU or mainstream CPUs. In this paper, we propose a novel parallel redistribution for DM that achieves an O(log2N) time complexity. We also present empirical results that indicate that our novel approach outperforms the O((log2N)2) approach.
We study here systems of distributed entities that can actively modify their communication network. This gives rise to distributed algorithms that apart from communication can also exploit network ...reconfiguration to carry out a given task. Also, the distributed task itself may now require a global reconfiguration from a given initial network
G
s
to a target network
G
f
from a desirable family of networks. To formally capture costs associated with creating and maintaining connections, we define three edge-complexity measures: the
total edge activations
, the
maximum activated edges per round
, and the
maximum activated degree of a node
. We give (poly)log(
n
) time algorithms for the task of transforming any
G
s
into a
G
f
of diameter (poly)log(
n
), while minimizing the edge-complexity. Our main lower bound shows that
Ω
(
n
)
total edge activations and
Ω
(
n
/
log
n
)
activations per round must be paid by any algorithm (even centralized) that achieves an optimum of
Θ
(
log
n
)
rounds. We give three distributed algorithms for our general task. The first runs in
O
(
log
n
)
time, with at most 2
n
active edges per round, a total of
O
(
n
log
n
)
edge activations, a maximum degree
n
-
1
, and a target network of diameter 2. The second achieves bounded degree by paying an additional logarithmic factor in time and in total edge activations. It gives a target network of diameter
O
(
log
n
)
and uses
O
(
n
) active edges per round. Our third algorithm shows that if we slightly increase the maximum degree to polylog(
n
) then we can achieve
o
(
log
2
n
)
running time.
We extend the population protocol model with a cover-time service that informs a walking state every time it covers the whole network. This represents a known upper bound on the cover time of a ...random walk. The cover-time service allows us to introduce termination into population protocols, a capability that is crucial for any distributed system. By reduction to an oracle-model we arrive at a very satisfactory lower bound on the computational power of the model: we prove that it is at least as strong as a Turing Machine of space logn with input commutativity, where n is the number of nodes in the network. We also give a logn-space, but nondeterministic this time, upper bound. Finally, we prove interesting similarities of this model to linear bounded automata.
•We introduce a variant of population protocols capable of termination.•The ability to terminate is modeled by an oracle detecting absence of states.•We prove that the new model simulates Turing Machines of space logn.•We demonstrate similarities to linear bounded automata.
Binary Search in Graphs Revisited Deligkas, Argyrios; Mertzios, George B.; Spirakis, Paul G.
Algorithmica,
15/5, Volume:
81, Issue:
5
Journal Article
Peer reviewed
Open access
In the classical binary search in a path the aim is to detect an unknown target by asking as few queries as possible, where each query reveals the direction to the target. This binary search ...algorithm has been recently extended by Emamjomeh-Zadeh et al. (in: Proceedings of the 48th annual ACM SIGACT symposium on theory of computing, STOC 2016, Cambridge, pp. 519–532,
2016
) to the problem of detecting a target in an arbitrary graph. Similarly to the classical case in the path, the algorithm of Emamjomeh-Zadeh et al. maintains a candidates’ set for the target, while each query asks an appropriately chosen vertex—the “median”—which minimises a potential
Φ
among the vertices of the candidates’ set. In this paper we address three open questions posed by Emamjomeh-Zadeh et al., namely (a) detecting a target when the query response is a direction to an
approximately shortest path
to the target, (b) detecting a target when querying a vertex that is an
approximate median
of the current candidates’ set (instead of an exact one), and (c) detecting
multiple targets
, for which to the best of our knowledge no progress has been made so far. We resolve questions (a) and (b) by providing appropriate upper and lower bounds, as well as a new potential
Γ
that guarantees efficient target detection even by querying an approximate median each time. With respect to (c), we initiate a systematic study for detecting two targets in graphs and we identify sufficient conditions on the queries that allow for strong (linear) lower bounds and strong (polylogarithmic) upper bounds for the number of queries. All of our positive results can be derived using our new potential
Γ
that allows querying approximate medians.
We study a security game over a network played between a
defender
and
k
attackers
. Every attacker chooses, probabilistically, a node of the network to damage. The defender chooses, probabilistically ...as well, a connected induced subgraph of the network of
λ
nodes to scan and clean. Each attacker wishes to maximize the probability of escaping her cleaning by the defender. On the other hand, the goal of the defender is to maximize the expected number of attackers that she catches. This game is a generalization of the model from the seminal paper of Mavronicolas et al. Mavronicolas et al. (in: International symposium on mathematical foundations of computer science, MFCS, pp 717–728, 2006). We are interested in Nash equilibria of this game, as well as in characterizing
defense-optimal
networks which allow for the best
equilibrium defense ratio
; this is the ratio of
k
over the expected number of attackers that the defender catches in equilibrium. We provide a characterization of the Nash equilibria of this game and defense-optimal networks. The equilibrium characterizations allow us to show that even if the attackers are centrally controlled the equilibria of the game remain the same. In addition, we give an algorithm for computing Nash equilibria. Our algorithm requires exponential time in the worst case, but it is polynomial-time for
λ
constantly close to 1 or
n
. For the special case of tree-networks, we further refine our characterization which allows us to derive a polynomial-time algorithm for deciding whether a tree is defense-optimal and if this is the case it computes a defense-optimal Nash equilibrium. On the other hand, we prove that it is
NP
-hard to find a best-defense strategy if the tree is not defense-optimal. We complement this negative result with a polynomial-time constant-approximation algorithm that computes solutions that are close to optimal ones for general graphs. Finally, we provide asymptotically (almost) tight bounds for the
Price of Defense
for any
λ
; this is the worst equilibrium defense ratio over all graphs.
PDF
