On (1+ε) -approximate data reduction for the rural postman problem

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

1 Цитирования (Scopus)

Аннотация

Given a graph G=(V,E) with edge weights and a subset (formula presented) of required edges, the NP-hard Rural Postman Problem (RPP) is to find a closed walk of minimum total weight containing all edges of R. The number b of vertices incident to an odd number of edges of R and the number b of connected components formed by the edges in R are both bounded from above by the number of edges that has to be traversed additionally to the required ones. We show how to reduce any RPP instance I to an RPP instance I' with (formula presented) vertices in O(n)3 time so that any α -approximate solution for I' gives an (formula presented). -approximate solution for I, for any (formula presented). That is, we provide a polynomial-size approximate kernelization scheme (PSAKS). We make first steps towards a PSAKS with respect to the parameter c.

Язык оригиналаанглийский
Название основной публикацииMathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Proceedings
РедакторыMichael Khachay, Panos Pardalos, Yury Kochetov
ИздательSpringer-Verlag GmbH and Co. KG
Страницы279-294
Число страниц16
ISBN (печатное издание)9783030226282
DOI
СостояниеОпубликовано - 1 янв 2019
Событие18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019 - Ekaterinburg, Российская Федерация
Продолжительность: 8 июл 201912 июл 2019

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том11548 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

Конференция

Конференция18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019
СтранаРоссийская Федерация
ГородEkaterinburg
Период08.07.201912.07.2019

Fingerprint Подробные сведения о темах исследования «On (1+ε) -approximate data reduction for the rural postman problem». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать