Reoptimization of minimum latency problem revisited: don’t panic when asked to revisit the route after local modifications

Wenkai Dai () and Yongjie Yang ()
Additional contact information
Wenkai Dai: Saarland University
Yongjie Yang: Saarland University

Journal of Combinatorial Optimization, 2019, vol. 37, issue 2, No 12, 619 pages

Abstract: Abstract We study the reoptimization of the Minimum Latency problem (MLP) in metric space with respect to the modifications of adding (resp. removing) a vertex and increasing (resp. decreasing) the cost of an edge $$e^*$$ e ∗ . We provide 7 / 3-approximation and 3-approximation algorithms for the modifications of adding and removing a vertex, respectively. For the modification of increasing the cost of an edge $$e^*$$ e ∗ , we obtain $$\alpha $$ α -approximation algorithms where $$\alpha $$ α changes from 2.1286 to 4 / 3 as $$e^*$$ e ∗ moves from the first edge to the last edge in the given optimal tour of the initial instance. Concerning the case of decreasing the cost of an edge $$e^*$$ e ∗ , if $$e^*$$ e ∗ is an edge of the given optimal tour, we get a 2-approximation algorithm. Moreover, if $$e^*$$ e ∗ is the i-th edge of the given optimal tour and i is a constant, we derive a , but prove that an does not exist unless . We also show that the special case where $$i\in \{1,2\}$$ i ∈ { 1 , 2 } is polynomial-time solvable. If $$e^*$$ e ∗ is not in the given optimal tour, we derive a 2.1286-approximation algorithm, where n is the number of vertices. Finally, we show that if an approximation solution instead of an optimal one is given for the initial instance, the reoptimization of MLP with the vertex deletion operation admits no $$\alpha $$ α -approximation algorithm unless MLP itself admits such an algorithm.

Keywords: Reoptimization; Minimum latency; Traveling salesman; Complexity; Approximation algorithm; PTAS; Metrics (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-018-0317-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:37:y:2019:i:2:d:10.1007_s10878-018-0317-3

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-018-0317-3

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().