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

Результат исследований: Вклад в журналСтатьяНаучно-исследовательскаярецензирование

Аннотация

В статье предлагаются полиномиальные приближенные алгоритмы с константным фактором аппроксимации для задачи пересечения заданного набора отрезков на плоскости наименьшим числом одинаковых кругов. Если число различных направлений отрезков, входящих в набор, не превосходит , для этой задачи известен простой -приближенный алгоритм с временной сложностью Также для случая задачи на множествах ребер произвольных плоских графов известен 100-приближенный алгоритм с временем работы . В настоящей работе для частных случаев задачи на множествах ребер графов Габриеля, графов относительных окрестностей и минимальных евклидовых остовных деревьев, число различных ориентаций ребер в которых, вообще говоря, не ограничено сверху, удается построить несложные алгоритмы с факторами аппроксимации, равными соответственно 14, 12 и 10, имеющие существенно меньшую трудоемкость по сравнению с вышеупомянутым алгоритмом для общего случая задачи на множествах ребер произвольных плоских графов.
Переведенное названиеApproximation algorithms with guaranteed performance for the intersection of edge sets of some metric graphs with equal disks
Язык оригиналаРусский
Страницы (с-по)62-77
Число страниц16
ЖурналТруды института математики и механики УрО РАН
Том25
Номер выпуска1
DOI
СостояниеОпубликовано - 2019

Отпечаток

Approximation algorithms
Polynomials

Ключевые слова

    Предметные области WoS

    • Математика, Прикладная

    ГРНТИ

    • 27.00.00 МАТЕМАТИКА

    Уровень публикации

    • Перечень ВАК

    Цитировать

    @article{6ad3181852fb4915b57c3f6512fb5020,
    title = "ПРИБЛИЖЕННЫЕ АЛГОРИТМЫ С ГАРАНТИРОВАННЫМИ ОЦЕНКАМИ ТОЧНОСТИ ДЛЯ ПЕРЕСЕЧЕНИЯ МНОЖЕСТВ РЕБЕР НЕКОТОРЫХ МЕТРИЧЕСКИХ ГРАФОВ РАВНЫМИ КРУГАМИ",
    abstract = "В статье предлагаются полиномиальные приближенные алгоритмы с константным фактором аппроксимации для задачи пересечения заданного набора отрезков на плоскости наименьшим числом одинаковых кругов. Если число различных направлений отрезков, входящих в набор, не превосходит , для этой задачи известен простой -приближенный алгоритм с временной сложностью Также для случая задачи на множествах ребер произвольных плоских графов известен 100-приближенный алгоритм с временем работы . В настоящей работе для частных случаев задачи на множествах ребер графов Габриеля, графов относительных окрестностей и минимальных евклидовых остовных деревьев, число различных ориентаций ребер в которых, вообще говоря, не ограничено сверху, удается построить несложные алгоритмы с факторами аппроксимации, равными соответственно 14, 12 и 10, имеющие существенно меньшую трудоемкость по сравнению с вышеупомянутым алгоритмом для общего случая задачи на множествах ребер произвольных плоских графов.",
    keywords = "combinatorial optimization, approximation algorithm, geometric Hitting Set problem on the plane, straight line segment, Gabriel graph, relative neighborhood graph, Euclidean minimum spanning tree",
    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, имеющие существенно меньшую трудоемкость по сравнению с вышеупомянутым алгоритмом для общего случая задачи на множествах ребер произвольных плоских графов.

    KW - combinatorial optimization

    KW - approximation algorithm

    KW - geometric Hitting Set problem on the plane

    KW - straight line segment

    KW - Gabriel graph

    KW - relative neighborhood graph

    KW - Euclidean minimum spanning tree

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

    UR - https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=tsmetrics&SrcApp=tsm_test&DestApp=WOS_CPL&DestLinkType=FullRecord&KeyUT=000470956900006

    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 -