Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
The accuracy of one polynomial algorithm for the convergecast scheduling problem on a square grid with rectangular obstacles. / Erzin, Adil; Plotnikov, Roman.
Learning and Intelligent Optimization - 12th International Conference, LION 12, Revised Selected Papers. Springer, 2019. p. 131-140 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11353 LNCS).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
}
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
N1 - Publisher Copyright: © 2019, Springer Nature Switzerland AG.
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
T2 - 12th International Conference on Learning and Intelligent Optimization, LION 12
Y2 - 10 June 2018 through 15 June 2018
ER -
ID: 18143019