К.С. Кобылкин. Приближенные алгоритмы с гарантированными оценками точности для пересечения множеств ребер некоторых метрических графов равными кругами ... C. 62-77

Том 25, номер 1, 2019

УДК 519.856

MSC: 90C15

DOI: 10.21538/0134-4889-2019-25-1-62-77

Исследования поддержаны Российским научным фондом, грант № 14-11-00109.

В статье предлагаются полиномиальные приближенные алгоритмы с константным фактором аппроксимации для задачи пересечения заданного набора $n$ отрезков на плоскости наименьшим числом одинаковых кругов. Если число различных направлений отрезков, входящих в набор, не превосходит $k,$ для этой задачи известен простой $4k$-приближенный алгоритм с временной сложностью $O(n\log n).$ Также для случая задачи на множествах ребер произвольных плоских графов известен $100$-приближенный алгоритм с временем работы $O(n^4\log n).$ В настоящей работе для частных случаев задачи на множествах ребер графов Габриеля, графов относительных окрестностей и минимальных евклидовых остовных деревьев, число различных ориентаций ребер в которых, вообще говоря, не ограничено сверху, удается построить несложные алгоритмы с факторами аппроксимации, равными соответственно 14, 12 и 10, имеющие существенно меньшую трудоемкость $O(n^2)$ по сравнению с вышеупомянутым алгоритмом для общего случая задачи на множествах ребер произвольных плоских графов.

Ключевые слова: комбинаторная оптимизация, приближенный алгоритм, геометрическая задача Hitting Set на плоскости, прямолинейный отрезок, граф Габриеля, граф относительных окрестностей, минимальное евклидово остовное дерево

СПИСОК ЛИТЕРАТУРЫ

1.   Agarwal P., Pan J. Near-linear algorithms for geometric hitting sets and set covers // Proc. of 30th Ann. Symp. on Comput. Geom. 2014. P. 271–279.

2.   Alon N. A Non-linear lower bound for planar epsilon-nets // Discr. Comput. Geom. 2012. Vol. 47, no. 2. P. 235–244. doi: 10.1007/s00454-010-9323-7 

3.   Antunes D., Mathieu C., Mustafa N. Combinatorics of local search: An optimal 4-local Hall’s theorem for planar graphs // Proc. of 25th Ann. Eur. Symp. on Alg. (ESA). 2017. No. 87. P. 8:1–8:13. doi: 10.4230/LIPIcs.ESA.2017.8 

4.    Biniaz A., Liu P., Maheshwari A., Smid M. Approximation algorithms for the unit disk cover problem in 2D and 3D // Comput. Geom. 2017. Vol. 60. P. 8–18. doi: 10.1016/j.comgeo.2016.04.002 

5.   Bus N., Garg S., Mustafa N., Ray S. Limits of local search: Quality and efficiency // Discr. Comput. Geom. 2017. Vol. 57, no. 3. P. 607–624. doi: 10.1007/s00454-016-9819-x 

6.   Dash D., Bishnu A., Gupta A., Nandy S. C. Approximation algorithms for deployment of sensors for line segment coverage in wireless sensor networks // Wireless Networks. 2013. Vol. 19, no. 5. P. 857–870. doi: 10.1007/s11276-012-0506-4 

7.   Efrat A., Katz M. J., Nielsen F., Sharir M. Dynamic data structures for fat objects and their applications // Comput. Geom. 2000. Vol. 15. P. 215–227. doi: 10.1016/S0925-7721(99)00059-0 

8.   Jaromczyk J. W., Toussaint G. T. Relative neighborhood graphs and their relatives // Proc. IEEE. 1992. Vol. 80, no. 9. P. 1502–1517. doi: 10.1109/5.163414 

9.   Kobylkin K. S. Stabbing line segments with disks: Complexity and approximation algorithms // Lect. Notes Comp. Sci. 2017. Vol. 10716. P. 356–367. doi: 10.1007/978-3-319-73013-4_33 

10.   Kobylkin K. S. Constant factor approximation for intersecting line segments with disks // Lect. Notes Comp. Sci. 2019. Vol. 11353. P. 447–454. doi: 10.1007/978-3-030-05348-2_39 

11.   Matula D. W., Sokal R. R. Properties of Gabriel graphs relevant to geographic variation research and clustering of points in the plane // Geogr. Anal. 1980. Vol. 12, no. 3. P. 205–222. doi: 10.1111/j.1538-4632.1980.tb00031.x 

12.   Madireddy R. R., Mudgal A. Stabbing line segments with disks and related problems // Proc. of 28th Canadian Conf. on Comput. Geom. 2016. P. 201–207.

13.   Mustafa N., Ray S. Improved results on geometric hitting set problems // Discr. Comput. Geom. 2010. Vol. 44, no. 4. P. 883–895.

14.   Pyrga E., Ray S. New existence proofs for $\varepsilon$-nets // Proc. of 24th Ann. Symp. on Comput. Geom. 2008. P. 199–207. doi: 10.1145/1377676.1377708 

Поступила 19.11.2018

После доработки 23.01.2019

Принята к публикации 4.02.2019

Кобылкин Константин Сергеевич
канд. физ.-мат. наук, старший науч. сотрудник
Институт математики и механики им. Н.Н.Красовского УрО РАН;
Уральский федеральный университет
г. Екатеринбург
e-mail: kobylkinks@gmail.com

Ссылка на статью:   Кобылкин К.С.  Приближенные алгоритмы с гарантированными оценками точности для  пересечения множеств ребер некоторых метрических графов равными кругами  // Тр. Ин-та математики и механики УрО РАН. 2019. Т. 25, № 1. С. 62-77.

Cite this article as:   Approximation algorithms with guaranteed performance for the intersection of edge sets of some metric graphs with equal disks, Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2019, vol. 25, no. 1, pp. 62–77. 

English

K.S. Kobylkin. Approximation algorithms with guaranteed performance for the intersection of edge sets of some metric graphs with equal disks

Polynomial-time approximation algorithms with constant approximation ratio are proposed for the problem of intersection of a given set of $n$ planar straight line segments with the least number of equal disks. In the case where the segments have at most $k$ different orientations, a simple 4$k$-approximate algorithm with time complexity $O(n\log n)$ is known. In addition, a 100-approximate algorithm with time complexity $O(n^4\log n)$ is known for the case of the problem on the edge sets of plane graphs. In this paper, for instances of the problem on the edge sets of Gabriel graphs, relative neighbourhood graphs, and Euclidean minimum spanning trees, in which the number of different edge orientations is, in general, unbounded, we construct simple $O(n^2)$-time approximation algorithms with approximation ratios 14, 12, and 10, respectively. These algorithms outperform the aforementioned approximation algorithm for the general setting of the problem for edge sets of plane graphs.

Keywords: combinatorial optimization, approximation algorithm, geometric Hitting Set problem on the plane, straight line segment, Gabriel graph, relative neighborhood graph, Euclidean minimum spanning tree

Received November 19, 2018

Revised January 23, 2019

Accepted February 4, 2019

Funding Agency: This work was supported by the Russian Science Foundation (project no. 14-11-00109).

Konstantin Sergeevich Kobylkin, Cand. Sci. (Phys.-Math.), Krasovsky Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Ekaterinburg, 620108 Russia; Ural Federal University, Yekaterinburg, 620002 Russia, e-mail: kobylkinks@gmail.com

[References -> on the "English" button bottom right]