Standard

Complete solution of an optimization problem in tropical semifield. / Krivulin, Nikolai.

Relational and Algebraic Methods in Computer Science: 16th International Conference, RAMiCS 2017, Lyon, France, May 15-18, 2017, Proceedings. ed. / Peter Höfner; Damien Pous; Georg Struth. Cham : Springer Nature, 2017. p. 226-241 (Lecture Notes in Computer Science; Vol. 10226).

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Research › peer-review

Harvard

Krivulin, N 2017, Complete solution of an optimization problem in tropical semifield. in P Höfner, D Pous & G Struth (eds), Relational and Algebraic Methods in Computer Science: 16th International Conference, RAMiCS 2017, Lyon, France, May 15-18, 2017, Proceedings. Lecture Notes in Computer Science, vol. 10226, Springer Nature, Cham, pp. 226-241, The 16th International Conference on Relational and Algebraic Methods in Computer Science, Lyon, France, 15/05/17. https://doi.org/10.1007/978-3-319-57418-9_14

APA

Krivulin, N. (2017). Complete solution of an optimization problem in tropical semifield. In P. Höfner, D. Pous, & G. Struth (Eds.), Relational and Algebraic Methods in Computer Science: 16th International Conference, RAMiCS 2017, Lyon, France, May 15-18, 2017, Proceedings (pp. 226-241). (Lecture Notes in Computer Science; Vol. 10226). Springer Nature. https://doi.org/10.1007/978-3-319-57418-9_14

Vancouver

Krivulin N. Complete solution of an optimization problem in tropical semifield. In Höfner P, Pous D, Struth G, editors, Relational and Algebraic Methods in Computer Science: 16th International Conference, RAMiCS 2017, Lyon, France, May 15-18, 2017, Proceedings. Cham: Springer Nature. 2017. p. 226-241. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-319-57418-9_14

Author

Krivulin, Nikolai. / Complete solution of an optimization problem in tropical semifield. Relational and Algebraic Methods in Computer Science: 16th International Conference, RAMiCS 2017, Lyon, France, May 15-18, 2017, Proceedings. editor / Peter Höfner ; Damien Pous ; Georg Struth. Cham : Springer Nature, 2017. pp. 226-241 (Lecture Notes in Computer Science).

BibTeX

@inbook{83329121b88645f48fb9ae3a29842532,
title = "Complete solution of an optimization problem in tropical semifield",
abstract = "We consider a multidimensional optimization problem that is formulated in the framework of tropical mathematics to minimize a function defined on vectors over a tropical semifield (a semiring with idempotent addition and invertible multiplication). The function, given by a matrix and calculated through a multiplicative conjugate transposition, is nonlinear in the tropical mathematics sense. We show that all solutions of the problem satisfy a vector inequality, and then use this inequality to establish characteristic properties of the solution set. We examine the problem when the matrix is irreducible. We derive the minimum value in the problem, and find a set of solutions. The results are then extended to the case of arbitrary matrices. Furthermore, we represent all solutions of the problem as a family of subsets, each defined by a matrix that is obtained by using a matrix sparsification technique. We describe a backtracking procedure that offers an economical way to obtain all subsets in the family. Finally, the characteristic properties of the solution set are used to provide a complete solution in a closed form.",
keywords = "tropical semifield, tropical optimization, matrix sparsification, complete solution, backtracking",
author = "Nikolai Krivulin",
note = "Krivulin N. (2017) Complete Solution of an Optimization Problem in Tropical Semifield. In: H{\"o}fner P., Pous D., Struth G. (eds) Relational and Algebraic Methods in Computer Science. RAMICS 2017. Lecture Notes in Computer Science, vol 10226. Springer, Cham. https://doi.org/10.1007/978-3-319-57418-9_14; The 16th International Conference on Relational and Algebraic Methods in Computer Science, RAMiCS 2017 ; Conference date: 15-05-2017 Through 18-05-2017",
year = "2017",
doi = "10.1007/978-3-319-57418-9_14",
language = "English",
isbn = "978-3-319-57417-2",
series = "Lecture Notes in Computer Science",
publisher = "Springer Nature",
pages = "226--241",
editor = "Peter H{\"o}fner and Damien Pous and Georg Struth",
booktitle = "Relational and Algebraic Methods in Computer Science",
address = "Germany",
url = "http://www.ens-lyon.fr/LIP/PLUME/RAMiCS17/",

}

RIS

TY - CHAP

T1 - Complete solution of an optimization problem in tropical semifield

AU - Krivulin, Nikolai

N1 - Conference code: 16

PY - 2017

Y1 - 2017

N2 - We consider a multidimensional optimization problem that is formulated in the framework of tropical mathematics to minimize a function defined on vectors over a tropical semifield (a semiring with idempotent addition and invertible multiplication). The function, given by a matrix and calculated through a multiplicative conjugate transposition, is nonlinear in the tropical mathematics sense. We show that all solutions of the problem satisfy a vector inequality, and then use this inequality to establish characteristic properties of the solution set. We examine the problem when the matrix is irreducible. We derive the minimum value in the problem, and find a set of solutions. The results are then extended to the case of arbitrary matrices. Furthermore, we represent all solutions of the problem as a family of subsets, each defined by a matrix that is obtained by using a matrix sparsification technique. We describe a backtracking procedure that offers an economical way to obtain all subsets in the family. Finally, the characteristic properties of the solution set are used to provide a complete solution in a closed form.

AB - We consider a multidimensional optimization problem that is formulated in the framework of tropical mathematics to minimize a function defined on vectors over a tropical semifield (a semiring with idempotent addition and invertible multiplication). The function, given by a matrix and calculated through a multiplicative conjugate transposition, is nonlinear in the tropical mathematics sense. We show that all solutions of the problem satisfy a vector inequality, and then use this inequality to establish characteristic properties of the solution set. We examine the problem when the matrix is irreducible. We derive the minimum value in the problem, and find a set of solutions. The results are then extended to the case of arbitrary matrices. Furthermore, we represent all solutions of the problem as a family of subsets, each defined by a matrix that is obtained by using a matrix sparsification technique. We describe a backtracking procedure that offers an economical way to obtain all subsets in the family. Finally, the characteristic properties of the solution set are used to provide a complete solution in a closed form.

KW - tropical semifield

KW - tropical optimization

KW - matrix sparsification

KW - complete solution

KW - backtracking

U2 - 10.1007/978-3-319-57418-9_14

DO - 10.1007/978-3-319-57418-9_14

M3 - Chapter

SN - 978-3-319-57417-2

T3 - Lecture Notes in Computer Science

SP - 226

EP - 241

BT - Relational and Algebraic Methods in Computer Science

A2 - Höfner, Peter

A2 - Pous, Damien

A2 - Struth, Georg

PB - Springer Nature

CY - Cham

T2 - The 16th International Conference on Relational and Algebraic Methods in Computer Science

Y2 - 15 May 2017 through 18 May 2017

ER -

ID: 7746734