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

Research output: Contribution to journalArticleResearchpeer-review

Abstract

Polynomial-time approximation algorithms with constant approximation ratio are proposed for the problem of intersection of a given set of planar straight line segments with the least number of equal disks. In the case where the segments have at most different orientations, a simple 4-approximate algorithm with time complexity is known. In addition, a 100-approximate algorithm with time complexity 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 -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.
Translated title of the contributionApproximation algorithms with guaranteed performance for the intersection of edge sets of some metric graphs with equal disks
Original languageRussian
Pages (from-to)62-77
Number of pages16
JournalТруды института математики и механики УрО РАН
Volume25
Issue number1
DOIs
Publication statusPublished - 2019

Fingerprint

Approximation algorithms
Polynomials

GRNTI

  • 27.00.00 MATHEMATICS

Level of Research Output

  • VAK List

Cite this

@article{6ad3181852fb4915b57c3f6512fb5020,
title = "ПРИБЛИЖЕННЫЕ АЛГОРИТМЫ С ГАРАНТИРОВАННЫМИ ОЦЕНКАМИ ТОЧНОСТИ ДЛЯ ПЕРЕСЕЧЕНИЯ МНОЖЕСТВ РЕБЕР НЕКОТОРЫХ МЕТРИЧЕСКИХ ГРАФОВ РАВНЫМИ КРУГАМИ",
abstract = "В статье предлагаются полиномиальные приближенные алгоритмы с константным фактором аппроксимации для задачи пересечения заданного набора отрезков на плоскости наименьшим числом одинаковых кругов. Если число различных направлений отрезков, входящих в набор, не превосходит , для этой задачи известен простой -приближенный алгоритм с временной сложностью Также для случая задачи на множествах ребер произвольных плоских графов известен 100-приближенный алгоритм с временем работы . В настоящей работе для частных случаев задачи на множествах ребер графов Габриеля, графов относительных окрестностей и минимальных евклидовых остовных деревьев, число различных ориентаций ребер в которых, вообще говоря, не ограничено сверху, удается построить несложные алгоритмы с факторами аппроксимации, равными соответственно 14, 12 и 10, имеющие существенно меньшую трудоемкость по сравнению с вышеупомянутым алгоритмом для общего случая задачи на множествах ребер произвольных плоских графов.",
author = "Кобылкин, {Константин Сергеевич}",
year = "2019",
doi = "10.21538/0134-4889-2019-25-1-62-77",
language = "Русский",
volume = "25",
pages = "62--77",
journal = "Труды института математики и механики УрО РАН",
issn = "0134-4889",
publisher = "Институт математики и механики им. Н.Н. Красовского УрО РАН",
number = "1",

}

TY - JOUR

T1 - ПРИБЛИЖЕННЫЕ АЛГОРИТМЫ С ГАРАНТИРОВАННЫМИ ОЦЕНКАМИ ТОЧНОСТИ ДЛЯ ПЕРЕСЕЧЕНИЯ МНОЖЕСТВ РЕБЕР НЕКОТОРЫХ МЕТРИЧЕСКИХ ГРАФОВ РАВНЫМИ КРУГАМИ

AU - Кобылкин, Константин Сергеевич

PY - 2019

Y1 - 2019

N2 - В статье предлагаются полиномиальные приближенные алгоритмы с константным фактором аппроксимации для задачи пересечения заданного набора отрезков на плоскости наименьшим числом одинаковых кругов. Если число различных направлений отрезков, входящих в набор, не превосходит , для этой задачи известен простой -приближенный алгоритм с временной сложностью Также для случая задачи на множествах ребер произвольных плоских графов известен 100-приближенный алгоритм с временем работы . В настоящей работе для частных случаев задачи на множествах ребер графов Габриеля, графов относительных окрестностей и минимальных евклидовых остовных деревьев, число различных ориентаций ребер в которых, вообще говоря, не ограничено сверху, удается построить несложные алгоритмы с факторами аппроксимации, равными соответственно 14, 12 и 10, имеющие существенно меньшую трудоемкость по сравнению с вышеупомянутым алгоритмом для общего случая задачи на множествах ребер произвольных плоских графов.

AB - В статье предлагаются полиномиальные приближенные алгоритмы с константным фактором аппроксимации для задачи пересечения заданного набора отрезков на плоскости наименьшим числом одинаковых кругов. Если число различных направлений отрезков, входящих в набор, не превосходит , для этой задачи известен простой -приближенный алгоритм с временной сложностью Также для случая задачи на множествах ребер произвольных плоских графов известен 100-приближенный алгоритм с временем работы . В настоящей работе для частных случаев задачи на множествах ребер графов Габриеля, графов относительных окрестностей и минимальных евклидовых остовных деревьев, число различных ориентаций ребер в которых, вообще говоря, не ограничено сверху, удается построить несложные алгоритмы с факторами аппроксимации, равными соответственно 14, 12 и 10, имеющие существенно меньшую трудоемкость по сравнению с вышеупомянутым алгоритмом для общего случая задачи на множествах ребер произвольных плоских графов.

UR - https://elibrary.ru/item.asp?id=37051094

U2 - 10.21538/0134-4889-2019-25-1-62-77

DO - 10.21538/0134-4889-2019-25-1-62-77

M3 - Статья

VL - 25

SP - 62

EP - 77

JO - Труды института математики и механики УрО РАН

JF - Труды института математики и механики УрО РАН

SN - 0134-4889

IS - 1

ER -