TY - GEN

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

AU - Erzin, Adil

AU - Plotnikov, Roman

PY - 2019/1/1

Y1 - 2019/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85059950593&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-05348-2_11

DO - 10.1007/978-3-030-05348-2_11

M3 - Conference contribution

AN - SCOPUS:85059950593

SN - 9783030053475

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 131

EP - 140

BT - Learning and Intelligent Optimization - 12th International Conference, LION 12, Revised Selected Papers

PB - Springer-Verlag GmbH and Co. KG

T2 - 12th International Conference on Learning and Intelligent Optimization, LION 12

Y2 - 10 June 2018 through 15 June 2018

ER -