The accuracy of one polynomial algorithm for the convergecast scheduling problem on a square grid with rectangular obstacles

Adil Erzin, Roman Plotnikov

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

Аннотация

In the Convergecast Scheduling Problem, it is required to find in the communication graph an oriented spanning aggregation tree with a root in a base station and the arcs oriented to the root and to build a conflict-free min-length schedule for aggregating data along the arcs of the aggregation tree. This problem is NP-hard in general, however, if the communication graph is a unit square grid in each node of which there is a sensor and in which a data packet is transmitted along any edge during a one-time slot, the problem is polynomially solvable. In this paper, we consider a communication graph in the form of a square grid with rectangular obstacles impenetrable by the messages. In our previous paper, we proposed a polynomial algorithm for constructing a feasible schedule and intensive numerical experiment allowed us to make a hypothesis that the algorithm constructs an optimal solution. In this paper, we present a counterexample and prove that the proposed algorithm constructs a schedule of length at most one time round longer than the optimal schedule.

Язык оригиналаанглийский
Название основной публикацииLearning and Intelligent Optimization - 12th International Conference, LION 12, Revised Selected Papers
ИздательSpringer-Verlag GmbH and Co. KG
Страницы131-140
Число страниц10
ISBN (печатное издание)9783030053475
DOI
СостояниеОпубликовано - 1 янв 2019
Событие12th International Conference on Learning and Intelligent Optimization, LION 12 - Kalamata, Греция
Продолжительность: 10 июн 201815 июн 2018

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

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

Конференция

Конференция12th International Conference on Learning and Intelligent Optimization, LION 12
СтранаГреция
ГородKalamata
Период10.06.201815.06.2018

Fingerprint Подробные сведения о темах исследования «The accuracy of one polynomial algorithm for the convergecast scheduling problem on a square grid with rectangular obstacles». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать

    Erzin, A., & Plotnikov, R. (2019). The accuracy of one polynomial algorithm for the convergecast scheduling problem on a square grid with rectangular obstacles. В Learning and Intelligent Optimization - 12th International Conference, LION 12, Revised Selected Papers (стр. 131-140). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 11353 LNCS). Springer-Verlag GmbH and Co. KG. https://doi.org/10.1007/978-3-030-05348-2_11