The aim is to approximately solve minimum Steiner tree and minimum tour problems where prescribed quotas must be reached for the total weight of visited vertices. The project involves the study of both fast heuristic algorithms and algorithms with constant worst-case approximation ratio.
Hivatkozások
Pedrosa, L.L.C., Rosado, H.K.K. A 2-Approximation for the k-Prize-Collecting Steiner Tree Problem. Algorithmica 84, 3522–3558 (2022). https://doi.org/10.1007/s00453-021-00919-3