Weighted online minimum latency problem with edge uncertainty

Basit Öğe Kaydı
dc.authoridShiri, Davood/0000-0003-2884-0047
dc.authorwosidShiri, Davood/AAZ-2210-2020
dc.contributor.authorAkbari, Vahid
dc.contributor.authorShiri, Davood
dc.date.accessioned2024-07-18T20:42:34Z
dc.date.available2024-07-18T20:42:34Z
dc.date.issued2021
dc.departmentİstanbul Bilgi Üniversitesien_US
dc.description.abstractIn the minimum latency problem, an undirected connected graph and a root node together with non negative edge distances are given to an agent. The agent looks for a tour starting at the root node and visiting all the nodes to minimise the sum of the latencies of the nodes, where the latency of a node is the distance from the root node to the node at its first visit on the tour by the agent. We study an online variant of the problem, where there are k blocked edges in the graph which are not known to the agent in advance. A blocked edge is learned online when the agent arrives at one of its end nodes. Furthermore, we investigate another online variant of the minimum latency problem involving k blocked edges where each node is associated with a weight to express its priority and the objective is to minimise the summation of the weighted latency of the nodes. In this paper, we prove that the lower bound of 2 k + 1 on the competitive ratio of deterministic online algorithms is tight for both weighted and non-weighted variations by introducing an optimal deterministic online algorithm which meets this lower bound. We also present a lower bound of k + 1 on the expected competitive ratio of randomized online algorithms for both problems. We then develop two polynomial time heuristic algorithms to solve these online problems. We test our algorithms on real life as well as randomly generated instances that are partially adopted from the literature. (c) 2021 Elsevier B.V. All rights reserved.en_US
dc.identifier.doi10.1016/j.ejor.2021.02.038
dc.identifier.endpage65en_US
dc.identifier.issn0377-2217
dc.identifier.issn1872-6860
dc.identifier.issue1en_US
dc.identifier.scopus2-s2.0-85102805952en_US
dc.identifier.scopusqualityQ1en_US
dc.identifier.startpage51en_US
dc.identifier.urihttps://doi.org/10.1016/j.ejor.2021.02.038
dc.identifier.urihttps://hdl.handle.net/11411/7342
dc.identifier.volume295en_US
dc.identifier.wosWOS:000661773000004en_US
dc.identifier.wosqualityQ1en_US
dc.indekslendigikaynakWeb of Scienceen_US
dc.indekslendigikaynakScopusen_US
dc.language.isoenen_US
dc.publisherElsevieren_US
dc.relation.ispartofEuropean Journal of Operational Researchen_US
dc.relation.publicationcategoryMakale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanıen_US
dc.rightsinfo:eu-repo/semantics/closedAccessen_US
dc.subjectRoutingen_US
dc.subjectOnline Optimisationen_US
dc.subjectMinimum Latency Problemen_US
dc.subjectCompetitive Ratioen_US
dc.subjectOnline Algorithmsen_US
dc.subjectTraveling Salesman Problemen_US
dc.subjectRouting-Problemsen_US
dc.subjectShortest Pathsen_US
dc.subjectConnectivityen_US
dc.subjectTimeen_US
dc.titleWeighted online minimum latency problem with edge uncertainty
dc.typeArticle

Dosyalar

Koleksiyon

Web of Science Indexed Publications
Scopus Indexed Publications