Traveling salesman problems in temporal graphs

详细信息    查看全文

• 作者：Othon Michail^a ; ^{michailo@cti.gr" class="auth_mail" title="E-mail the corresponding author} ; Paul G. Spirakis^a ; ^b ; ^{P.Spirakis@liverpool.ac.uk" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Dynamic network ; Exploration ; TSP with costs one and two ; Temporal matching ; Approximation algorithm ; Hardness result
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：27 June 2016
• 年：2016
• 卷：634
• 期：Complete
• 页码：1-23
• 全文大小：783 K

文摘

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)$D=(V,A)$ may be viewed as a time-sequence G₁,G₂,…,G_l$G_1,G_2,\dots ,G_l$ of static graphs over the same (static) set of nodes V  . Each G_t=D(t)=(V,A(t))$G_t=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$c>0$, in a special case of temporal graphs and within (2−ε)$(2-\epsilon )$, for every constant ε>0$\epsilon >0$, in another special case in which D(t)$D(t)$ is strongly connected for all 1≤t≤l$1\le t\le l$, both unless P=NP$\mathbf{P}=\mathbf{NP}$. We then study the temporal analogue of TSP(1,2)$\text{TSP}(1,2)$, abbreviated TTSP(1,2)$\text{TTSP}(1,2)$, where, for all 1≤t≤l$1\le t\le l$, D(t)$D(t)$ is a complete weighted graph with edge-costs from {1,2}$\{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)$\text{TTSP}(1,2)$. Our best approximation is (1.7+ε)$(1.7+\epsilon )$ for the generic TTSP(1,2)$\text{TTSP}(1,2)$ and (13/8+ε)$(13/8+\epsilon )$ 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.