УДК 519.16 + 519.85
MSC: 68W25
https://doi.org/10.21538/0134-4889-2026-32-2-112-129
Задача стохастического ориентирования — базовый вариант одной из наиболее известных комбинаторных задач — задачи ориентирования. Как и в исходной детерминированной постановке цель задачи состоит в построении маршрута в заданной транспортной сети, обеспечивающего наибольшую награду, достижимую в пределах фиксированного бюджета. Основное отличие рассматриваемой постановки состоит в случайности временных затрат, связанных с посещением вершин сети. В связи с этим, подход к решению задачи связан с построением адаптивных или неадаптивных стратегий обхода сети, обеспечивающих максимально большую ожидаемую награду. Аппроксимационная способность более эффективных в построении неадаптивных стратегий оценивается в терминах разрыва адаптивности — максимального по рассматриваемому семейству постановок отношения математических ожиданий награды для оптимальных для заданной постановки адаптивной и неадаптивной стратегий. Известно, что в общем случае разрыв адаптивности обладает теоретической нижней оценкой $\Omega\bigl(\sqrt{\log\log B}\bigr)$ для заданной величины бюджета $B$, в то время как для некоторых частных случаев исследуемой задачи, например, стохастической задачи о рюкзаке, он не превосходит константы. В данной статье показывается, что для произвольной константы $\beta\in(0,1)$ аналогичным свойством обладает подкласс $\mathcal{I}_\beta$ задачи, в каждой постановке которого расстояние $d(u,v)$ между произвольными вершинами сети не превосходит $\beta$-й доли заданного бюджета. Доказательство данного утверждения конструктивно и опирается на обоснованный в работе алгоритм, сопоставляющий произвольной постановке $I\in\mathcal{I}_\beta$ за полиномиальное время от размера ее записи неадаптивную стратегию с ожидаемой наградой $\Omega\bigl((1 - \beta)$OPT$(I)\bigr)$.
Ключевые слова: стохастическая задача ориентирования, адаптивная и неадаптивная политика, полиномиальный приближенный алгоритм, константный фактор аппроксимации, константный разрыв адаптивности
СПИСОК ЛИТЕРАТУРЫ
1. Osipov Yu.S., Kryazhimskii A.V. Inverse Problems for Ordinary Differential Equations: Dynamical Solutions. Gordon and Breach, 1995. Basel: Gordon and Breach, 1995, 625 p.
2. Осипов Ю.С. Пакеты программ: подход к решению задач позиционного управления с неполной информацией. // Успехи мат. наук. 2006. Т. 61, № 4 (370). C. 25–76.
3. Osipov Yu.S., Maksimov V.I. Application of locally regularized extremal shift to the problem of realization of a prescribed motion // J. Inverse Ill-Posed Probl. 2024. Vol. 32, no. 5. P. 1033–1049.
https://doi.org/10.1515/jiip-2024-0018
4. Gupta A., Krishnaswamy R., Nagarajan V., Ravi R. Approximation algorithms for stochastic orienteering // Proc. Twenty-Third Annual ACM-SIAM Symp. on Discrete Algorithms (SODA 2012). San Francisco, 2012 (SIAM). P. 1522–1538. https://doi.org/10.1137/1.9781611973099.121
5. Gupta A., Krishnaswamy R., Nagarajan V., Ravi R. Running errands in time: Approximation algorithms for stochastic orienteering // Math. Operat. Res. 2015. Vol. 40, no. 1. P. 56–79. https://doi.org/10.1287/moor.2014.0656
6. Gunawan A., Lau H.C., Vansteenwegen P. Orienteering problem: A survey of recent variants, solution approaches and applications // Eur. J. Operat. Res. 2016. Vol. 255, no. 2. P. 315–332. https://doi.org/10.1016/j.ejor.2016.04.059
7. Vansteenwegen P., Gunnawan A. Orienteering problems: Models and algorithms for vehicle routing problems with profits. Cham: Springer, 2019. 112 p. https://doi.org/10.1007/978-3-030-29746-6
8. Bansal N., Nagarajan V. On the adaptivity gap of stochastic orienteering // Math. Program. 2015. Vol. 154, no. 1. P. 145–172. https://doi.org/10.1007/s10107-015-0927-9
9. Dean B.C., Goemans M.X., Vondrák J. Approximating the stochastic knapsack problem: The benefit of adaptivity // Math. Operat. Res. 2008. Vol. 33, no. 4. P. 945–964. https://doi.org/10.1287/moor.1080.0330
10. Golden B.L., Levy L., Vohra R. The orienteering problem // Nav. Res. Logist. 1987. Vol. 34, no. 3.
P. 307–318. https://doi.org/10.1002/1520-6750(198706)34:3
11. Trevisan L. When Hamming meets Euclid: The approximability of Geometric TSP and Steiner tree // SIAM J. Comput. 2000. Vol. 30, no. 2. P. 475–485. https://doi.org/10.1137/S0097539799352735
12. Blum A., Chawla S., Karger D.R., Lane T., Meyerson A., Minkoff M. Approximation algorithms for Orienteering and Discounted-Reward TSP // SIAM J. Comput. 2007. Vol. 37, no. 2. P. 653–670. https://doi.org/10.1137/050645464
13. Chekuri C., Korula N., Pál M. Improved algorithms for orienteering and related problems // ACM Trans. Algorithms. 2012. Vol. 8, no. 3. P. 661–670. https://doi.org/10.1145/2229163.222916
14. Chen K., Har-Peled S. The euclidean orienteering problem revisited // SIAM J. Comput. 2008. Vol. 38, no. 1. P. 385–397. https://doi.org/10.1137/060667839
15. Gottlieb L.-A., Krauthgamer R., Rika H. Faster algorithms for orienteering and k-TSP // Theor. Comput. Sci. 2022. Vol. 914. P. 73–83. https://doi.org/10.1016/j.tcs.2022.02.013
16. Gavalas D., Konstantopoulos C., Mastakas K., Pantziou G., Vathis N. Approximation algorithms for the arc orienteering problem // Inf. Proc. Letters. 2015. Vol. 115, no. 2. P. 313–315. https://doi.org/10.1016/j.ipl.2014.10.003
17. D’Angelo G., D’Emidio M., Delfaraz E., Di Stefano G. Improved algorithms for the capacitated team orienteering problem // Proc. 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024) / eds. P. C. Bouman, S. C. Kontogianni. Ser.: Open access series in informatics (OASIcs). 2024. Vol. 123. P. 7:1–7:17. https://doi.org/10.4230/OASIcs.ATMOS.2024.7
18. Xu W., Xu Z, Peng J., Liang W., Liu T., Jia X., Das S.K. Approximation algorithms for the team orienteering problem // IEEE INFOCOM 2020 — IEEE Conf. Comp. Commun. Toronto: IEEE Press, 2020. P. 1389–1398. https://doi.org/10.1109/INFOCOM41043.2020.9155343
19. Khachay M.Yu., Neznakhina E.D., Ryzhenko K.V. Constant-factor approximation algorithms for a series of combinatorial routing problems based on the reduction to the asymmetric traveling Salesman problem // Proc. Steklov Inst. Math. 2022. Vol. 319, iss. 1. P. S140–S155. https://doi.org/10.1134/S0081543822060128
20. Rizhenko K., Neznakhina K., Khachay M. Fixed ratio polynomial time approximation algorithm for the Prize-Collecting Asymmetric Traveling Salesman Problem // Ural Math. J. 2023. Vol. 9, no. 1. P. 135–146. http://dx.doi.org/10.15826/umj.2023.1.012
21. Blauth J., Klein N., Nägele M. A better-than-1.6-approximation for prizecollecting TSP // Math. Program. 2025. 20 p. https://doi.org/10.1007/s10107-025-02221-4
22. Bhalgat A., Goel A., Khanna S. Improved approximation results for stochastic knapsack problems // Proc. Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’11). San Francisco, California, 2011. P. 1647–1665.
23. Гимади Э.Х., Хачай М.Ю. Экстремальные задачи на множествах перестановок. Екатеринбург: УМЦ УПИ, 2016. 220 c.
24. Khachai M.Yu., Dubinin R.D. Approximability of the vehicle routing problem in finite-dimensional Euclidean spaces // Proc. Steklov Inst. Math. 2017. Vol. 297, iss. 1. P. S117–S128. https://doi.org/10.1134/S0081543817050133
25. Espinosa D.A., Swamy C. Approximation algorithms for correlated Knapsack orienteering // Proc. the 27th Inter. Conf. “Approximation algorithms for combinatorial optimization problems” (APPROX) / eds. A. Kumar, N. Ron-Zewi; Proc. the 28th Inter. Conf. “Randomization and computation” (RANDOM). Ser. Leibniz Inter. Proc. Informatics (LIPIcs). London: London School of Economics, 2024. P. 29:1–29:24.
Поступила 6.04.2026
После доработки 15.04.2026
Принята к публикации 20.04.2026
Кулемин Кирилл Олегович
аспирант, математик
Инcтитут математики и механики им. Н.Н. Красовского УрО РАН
e-mail: kulemin@imm.uran.ru
Хачай Михаил Юрьевич
д-р физ.-мат. наук, чл-корр. РАН, зав. отделом
Инcтитут математики и механики им. Н.Н. Красовского УрО РАН
e-mail: mkhachay@imm.uran.ru
Ссылка на статью: К.О. Кулемин, М.Ю. Хачай. Аппроксимируемость задачи стохастического ориентирования в классе неадаптивных стратегий // Тр. Ин-та математики и механики УрО РАН. 2026.
Т. 32, № 2. С. 112–129.
English
K.O. Kulemin, M.Yu. Khachai. Approximation of Stochastic Orienteering Problem within nonadaptive strategies
The Stochastic Orienteering Problem is a basic variant of a well-known combinatorial Orienteering Problem. Similarly to the initial deterministic setting, the objective is to find, in a given transportation network, a route providing the maximum reward subject to budget consumption constraint. The main difference of the setting in question is in randomness of time delays related to visiting the nodes in the network. Therefore, any approach to solve this problem relates to construction not a single path but node-visiting policies, adaptive or nonadaptive, that provide the possibly largest expected reward. Among these two types, nonadaptive policies are more efficient to construct. Their approximation ability is assessed in terms of adaptivity gap, which is equal, for a considered family of instances, to the maximum ratio between expected rewards collected by optimal adaptive and nonadaptive polices, respectively. For the general stochastic orienteering problem, adaptivity gap is $\Omega\bigl(\sqrt{\log\log B}\bigr)$, for a given budget $B$, while, for some its special cases, e.g. for the stochastic knapsack problem, the adaptivity gap is constant. In this paper, we show that adaptivity gap remains constant for any subclass $\mathcal{I}_\beta$ of the stochastic orienteering problem specified by an arbitrary constant $\beta\in(0,1)$, for which the distance $d(u,v)$ between any nodes does not exceed $\beta$-fraction of the given budget. The proof is constructive and follows from the proposed polynomial time algorithm that, for any instance $I\in\mathcal{I}_\beta$, provides a nonadaptive policy with expected reward $\Omega\bigl((1 - \beta)$OPT$(I)\bigr)$.
Keywords: stochastic orienteering problem, adaptive and nonadaptive policies, polynomial time approximation algorithm, constant approximation factor, constant adaptivity gap
Received April 6, 2026
Revised April 15, 2026
Accepted April 20, 2026
Kirill Olegovich Kulemin, PhD-student, Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620077 Russia, e-mail: kulemin@imm.uran.ru
Mikhail Yur’evich Khachai, Dr. Phys.-Math. Sci, RAS Corresponding Member, Prof., Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620077 Russia, e-mail: mkhachay@imm.uran.ru
Cite this article as: K.O. Kulemin, M.Yu. Khachai. Approximation of Stochastic Orienteering Problem within nonadaptive strategies. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2026, vol. 32, no. 2, pp. 112–129.
[References -> on the "English" button bottom right]
