Cover Image

NP-hardness of collective pursuiting optimization problems

The differential pursuitevasion games on a plane are considered. A group of pursuers is created for every evader in a game. The optimization problem of group composition has been formulated. The theorems about NP-completeness and NP-hardness of pursuit optimization problems are proved. Numerical met...

Full description

Saved in:

Bibliographic Details
Date:	2025
Main Author:	Pashko, S.V.
Format:	Article
Language:	Russian
Published:	PROBLEMS IN PROGRAMMING 2025
Subjects:	UDC 518.9
Online Access:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/692
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Problems in programming
Download file:

Institution

Problems in programming

Similar Items

Maximal time of pursuit for the strategy of parallel approach
by: Pashko, S.V., et al.
Published: (2019)

Numerical Methods for Solving the Pursuit Optimization Problems
by: Pashko, C.V., et al.
Published: (2025)

Construction of pursuit strategies with using Lyapunov functions
by: Pashko, S.V.
Published: (2018)

Simulation of optimal pursuit strategies with simple motion
by: Pashko, S.V.
Published: (2023)

Modification of the family three-point iterative method for refinement of simple roots of monotonic nonsmooth function
by: Шелудько, Г. А., et al.
Published: (2015)

Modification of the family three-point iterative method for refinement of simple roots of monotonic nonsmooth function
by: Шелудько, Г. А., et al.
Published: (2015)

To the problem of pursuit on the plane
by: Yalovets, A.L.
Published: (2025)

The magnitudes of acceleration in the optimal pursuit strategies
by: S. V. Pashko, et al.
Published: (2023)

The operating model of communicative informations systems
by: Zubenko, V.V.
Published: (2025)

Guaranteed time of pursuit for the strategy of parallel approach
by: S. V. Pashko
Published: (2014)

Construction of pursuit strategies with using Lyapunov functions
by: S. V. Pashko
Published: (2017)

Effective pursuit strategies based on the use of the Lyapunov function
by: S. V. Pashko
Published: (2016)

Modernization adaptive piecewise linear approximation of difficult-to-compute functions
by: Sheludko, G. A., et al.
Published: (2018)

Modernization adaptive piecewise linear approximation of difficult-to-compute functions
by: Sheludko, G. A., et al.
Published: (2018)

Solvability of NP-complete problems
by: O. A. Vahis, et al.
Published: (2022)

About an optimal control for a "predator-prey" system
by: Pashko, S.V.
Published: (2020)

Special attention is given to the project of the Informational System "Planned for Science in the NAPN of Ukraine"
by: Zadorozhna, N.T., et al.
Published: (2015)

Optimal placement of a multi-sensor system
by: Pashko, S.V.
Published: (2018)

About the method of the nearest point as a method of management of strategies of pursuit/evasion of agents
by: Yalovets, A.L.
Published: (2025)

Spline-interlineation in building of optimal by exactness cubature formula for the exact evaluating of 3D Fourier’s coefficients on one differential class
by: Литвин, О. М., et al.
Published: (2016)

Spline-interlineation in building of optimal by exactness cubature formula for the exact evaluating of 3D Fourier’s coefficients on one differential class
by: Литвин, О. М., et al.
Published: (2016)

On a criterion of $NP$-completeness
by: Bulitko, V. V., et al.
Published: (1998)

Improving the quality of educational process management through the integration of a module based on ERP ODOO in the context of cloud technologies
by: Bida, P.I., et al.
Published: (2025)

Individual and collective parts in experience of victims of Nazi pursuits: source studies aspect
by: M. Dubyk
Published: (2010)

Pursuit problem for fractional differential systems with pure delay
by: L. V. Baranovska
Published: (2022)

To the decision of pursuit problem under integral constrains on controls
by: I. S. Rappoport
Published: (2018)

On a descriptor pursuit game
by: L. A. Vlasenko, et al.
Published: (2021)

NP-трудность задач оптимизации коллективного преследования
by: Пашко, С.В.
Published: (2014)

Optimization problems solution for queuing systems with failure under uncertainty
by: Kopytchuk, M.B., et al.
Published: (2025)

On substantiation of method of proportional navi-gationin simple pursuit problem
by: A. P. Ignatenko, et al.
Published: (2004)

Superfluidity of a condensate with np pairing correlations in asymmetric nuclear matter
by: Akhiezer, A.I., et al.
Published: (2001)

Time optimal control problem for the Lotka–Volterra system
by: S. V. Pashko
Published: (2021)

Cloud service for authentication of a person based on their electrocardiogram
by: Luhovskyi, Yu.O.
Published: (2023)

Numerical method of solving a problem of optical pursuit by maximum of time
by: Beiko, I. V., et al.
Published: (1966)

Restorative thermal treatment of shell parts of turbines during complex turbine reconstruction after continuous service
by: Любимов, А. А.
Published: (2016)

Restorative thermal treatment of shell parts of turbines during complex turbine reconstruction after continuous service
by: Любимов, А. А.
Published: (2016)

A Pursuit Problem in an Infinite System of Second-Order Differential Equations
by: Ibragimov, G., et al.
Published: (2013)

A Pursuit Problem in an Infinite System of Second-Order Differential Equations
by: G. Ibragimov, et al.
Published: (2013)

A Pursuit Problem in an Infinite System of Second-Order Differential Equations
by: Allahabi, F., et al.
Published: (2013)

Оцінювання можливості подальшого використання колекторів первинного пароперегрівача котла з експлуатаційними пошкодженнями
by: Astashkin, V. I.; Асташкін В. І.; Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України, Львів, et al.
Published: (2018)