Akcay, Mehmet BerkehanAkcan, HüseyinEvrendilek, Cem2023-06-162023-06-1620181381-12311572-9397https://doi.org/10.1007/s10732-018-9370-4https://hdl.handle.net/20.500.14365/914Given an edge weighted tree T(V, E), rooted at a designated base vertex , and a color from a set of colors assigned to every vertex , All Colors Shortest Path problem on trees (ACSP-t) seeks the shortest, possibly non-simple, path starting from r in T such that at least one node from every distinct color in C is visited. We show that ACSP-t is NP-hard, and also prove that it does not have a constant factor approximation. We give an integer linear programming formulation of ACSP-t. Based on a linear programming relaxation of this formulation, an iterative rounding heuristic is proposed. The paper also explores genetic algorithm and tabu search to develop alternative heuristic solutions for ACSP-t. The performance of all the proposed heuristics are evaluated experimentally for a wide range of trees that are generated parametrically.eninfo:eu-repo/semantics/closedAccessNP-hardnessInapproximabilityInteger linear programmingLinear programming relaxationGenetic algorithmTabu searchTraveling-Salesman ProblemApproximation AlgorithmN-SetsNodesArticle10.1007/s10732-018-9370-42-s2.0-85044603535