Розробка алгоритму групового пошуку для задачі секретаря

Автор(и)

  • Сергій Іванович Доценко Київський національний університет імені Тараса Шевченка, Україна https://orcid.org/0000-0003-2913-3790
  • Анастасія Сергіївна Вєчерковська Київський національний університет імені Тараса Шевченка, Україна https://orcid.org/0000-0003-2054-2715

DOI:

https://doi.org/10.15587/1729-4061.2026.353251

Ключові слова:

оптимальна зупинка, умовна ймовірність, оптимальний вибір, теорема про шанси, моделювання методом Монте-Карло

Анотація

Об’єктом дослідження є узагальнена задача секретаря, у якій кандидати поділяються на групи різного розміру та спостерігаються одночасно в межах кожної групи. Вирішувалася проблема визначення оптимального порядку перегляду таких груп з метою максимізації ймовірності вибору найкращого кандидата.

Отримані результати полягають у побудові ефективного алгоритму впорядкування груп, який поєднує теоретичні результати, засновані на теоремі шансів Брусса, з чисельним моделюванням методом Монте-Карло.

Завдяки своїм особливостям та характерним відмінностям отримані результати підвищити ймовірність вибору найкращого кандидата на 8–15% порівняно з випадковим порядком вибору. Це досягається за рахунок двох доведених лем, які обмежують розгляд лише тими перестановками, де групи, що розглядаються як кандидати для зупинки, впорядковані за незростанням розміру, а пошук починається з найбільшої групи. Такий алгоритм  розв’язання робить задачу обчислювально здійсненною навіть для помірно великої кількості груп.

Отримані результати пояснюються тим, що нерівномірність розмірів груп створює додаткову структурну інформацію, яку ефективно використовує запропонована стратегія впорядкування.

Практичне використання побудованого алгоритму можливе в умовах задач розподілу ресурсів, адаптивних алгоритмів з оновленням у реальному часі, а також у системах підтримки прийняття рішень і рекрутингових платформах. Запропонований алгоритм є релевантним як для теоретичних досліджень задач оптимальної зупинки, так і для прикладних застосувань в операційних дослідженнях, економіці та штучному інтелекті

Біографії авторів

Сергій Іванович Доценко, Київський національний університет імені Тараса Шевченка

Доцент

Кафедра програмних систем та технологій

Анастасія Сергіївна Вєчерковська, Київський національний університет імені Тараса Шевченка

Доцент

Кафедра програмних систем та технологій

Посилання

  1. Ferguson, T. S. (1989). Who Solved the Secretary Problem? Statistical Science, 4 (3). https://doi.org/10.1214/ss/1177012493
  2. Dubynetska, P., Sodoma, R. (2023). Osoblyvosti metodiv pidboru kadriv na pidpryiemstvo. Abstracts of the І International Scientific-Practical Conference «Problems and Prospects of Business Structures in the Conditions Unstable Processes of Economic Development». Kyiv, 36–38. Available at: https://sci.ldubgd.edu.ua/bitstream/123456789/13000/1/%D0%97%D0%B1%D1%96%D1%80%D0%BA%D0%B0_%D0%9A%D0%BE%D0%BD%D1%84_%D0%9A%D0%95%D0%91%D0%A2_06.04.23.pdf
  3. Correa, J., Cristi, A., Epstein, B., Soto, J. A. (2024). Sample-Driven Optimal Stopping: From the Secretary Problem to the i.i.d. Prophet Inequality. Mathematics of Operations Research, 49 (1), 441–475. https://doi.org/10.1287/moor.2023.1363
  4. Semsar-Kazerooni, E., Khorasani, K. (2009). Multi-agent team cooperation: A game theory approach. Automatica, 45 (10), 2205–2213. https://doi.org/10.1016/j.automatica.2009.06.006
  5. Hsiau, S.-R., Yang, J.-R. (2000). A natural variation of the standard secretary problem. Statistica Sinica, 10 (2), 639–646. Available at: https://www.jstor.org/stable/24306737
  6. Bruss, F. T. (2000). Sum the odds to one and stop. The Annals of Probability, 28 (3). https://doi.org/10.1214/aop/1019160340
  7. Tamaki, M. (2009). Optimal Choice of the Best Available Applicant in Full-Information Models. Journal of Applied Probability, 46 (4), 1086–1099. https://doi.org/10.1239/jap/1261670690
  8. Ano, K., Kakinuma, H., Miyoshi, N. (2010). Odds Theorem with Multiple Selection Chances. Journal of Applied Probability, 47 (4), 1093–1104. https://doi.org/10.1239/jap/1294170522
  9. Feldman, M., Izsak, R. (2017). Building a Good Team: Secretary Problems and the Supermodular Degree. Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1651–1670. https://doi.org/10.1137/1.9781611974782.109
  10. Blanc, P., Borthagaray, J. P., Kohen, D., Mereb, M. (2017). Secretary problem with quality-based payoff. arXiv. https://doi.org/10.48550/arXiv.1605.06478
  11. Goldstein, D. G., McAfee, R. P., Suri, S., Wright, J. R. (2017). Learning in the Repeated Secretary Problem. Proceedings of the 2017 ACM Conference on Economics and Computation, 541–541. https://doi.org/10.1145/3033274.3085112
  12. Correa, J., Cristi, A., Feuilloley, L., Oosterwijk, T., Tsigonias-Dimitriadis, A. (2025). The Secretary Problem with Independent Sampling. Management Science, 71 (4), 2778–2801. https://doi.org/10.1287/mnsc.2021.01580
  13. Dotsenko, S., Shevchenko, G. (2020). Secretary problem with vanishing objects. Mathematical Game Theory and Applications, 12 (2), 63–81. https://doi.org/10.17076/mgta_2020_2_16
  14. Nuti, P., Vondrák, J. (2023). Secretary Problems: The Power of a Single Sample. Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2015–2029. https://doi.org/10.1137/1.9781611977554.ch77
  15. Fujii, K., Yoshida, Y. (2024). The Secretary Problem with Predictions. Mathematics of Operations Research, 49 (2), 1241–1262. https://doi.org/10.1287/moor.2022.0031
  16. Braun, A., Sarkar, S. (2024). The Secretary Problem with Predicted Additive Gap. Advances in Neural Information Processing Systems 37, 16321–16341. https://doi.org/10.52202/079017-0521
  17. Antoniadis, A., Gouleakis, T., Kleer, P., Kolev, P. (2023). Secretary and online matching problems with machine learned advice. Discrete Optimization, 48, 100778. https://doi.org/10.1016/j.disopt.2023.100778
  18. Albers, S., Ladewig, L. (2021). New results for the k-secretary problem. Theoretical Computer Science, 863, 102–119. https://doi.org/10.1016/j.tcs.2021.02.022
  19. Brera, R., Fu, F. (2023). The satisficing secretary problem: when closed-form solutions meet simulated annealing. arXiv. https://doi.org/10.48550/arXiv.2302.03220
  20. Hahn, N., Hoefer, M., Smorodinsky, R. (2020). The Secretary Recommendation Problem. Proceedings of the 21st ACM Conference on Economics and Computation, 189–189. https://doi.org/10.1145/3391403.3399478
  21. Chun, Y. H., Moskowitz, H., Plante, R. D. (1993). Optimal Selection Strategy for the Group Interview Problem. Decision Sciences, 24 (2), 295–314. https://doi.org/10.1111/j.1540-5915.1993.tb00476.x
  22. Pinsky, R. G. (2023). The secretary problem with non-uniform arrivals via a left-to-right minimum exponentially tilted distribution. Latin American Journal of Probability and Mathematical Statistics, 20 (2), 1631. https://doi.org/10.30757/alea.v20-62
Розробка алгоритму групового пошуку для задачі секретаря

##submission.downloads##

Опубліковано

2026-02-27

Як цитувати

Доценко, С. І., & Вєчерковська, А. С. (2026). Розробка алгоритму групового пошуку для задачі секретаря. Eastern-European Journal of Enterprise Technologies, 1(4 (139), 56–64. https://doi.org/10.15587/1729-4061.2026.353251

Номер

Том 1 № 4 (139) (2026): Математика та кібернетика - прикладні аспекти

Розділ

Математика та кібернетика - прикладні аспекти

Ліцензія

Авторське право (c) 2026 Serhii Dotsenko, Anastasia Vecherkovskaya

Creative Commons License

Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.

Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.

Ліцензійний договір – це документ, в якому автор гарантує, що володіє усіма авторськими правами на твір (рукопис, статтю, тощо).
Автори, підписуючи Ліцензійний договір з ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР», мають усі права на подальше використання свого твору за умови посилання на наше видання, в якому твір опублікований. Відповідно до умов Ліцензійного договору, Видавець ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР» не забирає ваші авторські права та отримує від авторів дозвіл на використання та розповсюдження публікації через світові наукові ресурси (власні електронні ресурси, наукометричні бази даних, репозитарії, бібліотеки тощо).
За відсутності підписаного Ліцензійного договору або за відсутністю вказаних в цьому договорі ідентифікаторів, що дають змогу ідентифікувати особу автора, редакція не має права працювати з рукописом.
Важливо пам’ятати, що існує і інший тип угоди між авторами та видавцями – коли авторські права передаються від авторів до видавця. В такому разі автори втрачають права власності на свій твір та не можуть його використовувати в будь-який спосіб.