Abstract: There are two well-known problems with covering points using identical disks. The points in both problems are arbitrarily spread over the plane. In the rst problem, it is necessary to cover all points with a minimum number of identical disks. In the second problem, it is required to cover the maximum number of points with a known number of identical disks. Both problems are NP hard. This paper considers a problem di erent from those mentioned above. The set of points is split into two subsets of mandatory and optional points. The set of mandatory points is divided into disjoint subsets (clusters). It is required to cover each cluster of mandatory points with one unit disk in such a way as to maximize the number of covered optional points. The complexity status of the problem is unknown. This paper considers a special case of the problem in which all points are on a strip. Su cient conditions are found for the existence of an optimal orderpreserving cover, which is constructed in polynomial time using a dynamic programming.

Cite: Erzin A. , Voronchikhina E.
Covering mandatory and optional points on a strip with identical disks
In compilation Advances in Optimization and Applications. 2025.

Identifiers: No identifiers

Citing: Пока нет цитирований