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

Adil Erzin, Roman Plotnikov

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

Abstract

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.

Original languageEnglish
Title of host publicationLearning and Intelligent Optimization - 12th International Conference, LION 12, Revised Selected Papers
PublisherSpringer-Verlag GmbH and Co. KG
Pages131-140
Number of pages10
ISBN (Print)9783030053475
DOIs
Publication statusPublished - 1 Jan 2019
Event12th International Conference on Learning and Intelligent Optimization, LION 12 - Kalamata, Greece
Duration: 10 Jun 201815 Jun 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11353 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference12th International Conference on Learning and Intelligent Optimization, LION 12
CountryGreece
CityKalamata
Period10.06.201815.06.2018

Fingerprint Dive into the research topics of 'The accuracy of one polynomial algorithm for the convergecast scheduling problem on a square grid with rectangular obstacles'. Together they form a unique fingerprint.

Cite this