In this work, we introduce the notion of time to some well-known combinatorial optimization problems. In particular, we study problems defined on \emph{temporal graphs}. A temporal graph $D=(V,A)$ may be viewed as a time-sequence $G_1,G_2,\ldots,G_l$ of static graphs over the same (static) set of nodes $V$. Each $G_t=D(t)=(V,A(t))$ is called the \emph{instance of $D$ at time $t$} and $l$ is called the \emph{lifetime of $D$}. Our main focus is on analogues of \emph{traveling salesman problems} in temporal graphs. A sequence of time-labeled edges (e.g. a tour) is called \emph{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-\varepsilon)$, for every constant $\varepsilon>0$, in another special case in which $D(t)$ is strongly connected for all $1\leq t\leq l$, both unless $\rem{P}=\rem{NP}$. We then study the temporal analogue of TSP(1,2), abbreviated TTSP(1,2), where, for all $1\leq t\leq 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 \emph{polynomial-time approximation algorithms} for TTSP(1,2). Our best approximation is $(1.7+\varepsilon)$ for the generic TTSP(1,2) and $(13/8+\varepsilon)$ 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.
@article{MS16b,
author = {Michail, Othon and Spirakis, Paul G.},
title = {Traveling Salesman Problems in Temporal Graphs},
journal = {Theoretical Computer Science},
volume = {634},
pages = {1--23},
year = {2016},
issn = {0304-3975},
doi = {http://dx.doi.org/10.1016/j.tcs.2016.04.006},
url = {http://www.sciencedirect.com/science/article/pii/S0304397516300342},
publisher = {Elsevier}
}