Standard

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-Verlag GmbH and Co. KG, 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 proceedingConference contributionResearchpeer-review

Harvard

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

APA

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

Vancouver

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

Author

Erzin, Adil ; Plotnikov, Roman. / 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. Springer-Verlag GmbH and Co. KG, 2019. pp. 131-140 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{c6aaac6c57e34c258575f935a3437905,
title = "The accuracy of one polynomial algorithm for the convergecast scheduling problem on a square grid with rectangular obstacles",
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.",
author = "Adil Erzin and Roman Plotnikov",
note = "Publisher Copyright: {\textcopyright} 2019, Springer Nature Switzerland AG.; 12th International Conference on Learning and Intelligent Optimization, LION 12 ; Conference date: 10-06-2018 Through 15-06-2018",
year = "2019",
month = jan,
day = "1",
doi = "10.1007/978-3-030-05348-2_11",
language = "English",
isbn = "9783030053475",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer-Verlag GmbH and Co. KG",
pages = "131--140",
booktitle = "Learning and Intelligent Optimization - 12th International Conference, LION 12, Revised Selected Papers",
address = "Germany",

}

RIS

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

ID: 18143019