Standard
Solving a tropical optimization problem via matrix sparsification. / Krivulin, Nikolai .
Relational and Algebraic Methods in Computer Science: 15th International Conference, RAMiCS 2015, Braga, Portugal, September 28 - October 1, 2015, Proceedings. ed. / Wolfram Kahl; Michael Winter; José N. Oliveira. Cham : Springer Nature, 2015. p. 326-343 (Lecture Notes in Computer Science; Vol. 9348).
Research output: Chapter in Book/Report/Conference proceeding › Chapter › Research › peer-review
Harvard
Krivulin, N 2015,
Solving a tropical optimization problem via matrix sparsification. in W Kahl, M Winter & JN Oliveira (eds),
Relational and Algebraic Methods in Computer Science: 15th International Conference, RAMiCS 2015, Braga, Portugal, September 28 - October 1, 2015, Proceedings. Lecture Notes in Computer Science, vol. 9348, Springer Nature, Cham, pp. 326-343, 15th International Conference on Relational and Algebraic Methods in Computer Science, Braga, Portugal,
28/09/15.
https://doi.org/10.1007/978-3-319-24704-5_20
APA
Krivulin, N. (2015).
Solving a tropical optimization problem via matrix sparsification. In W. Kahl, M. Winter, & J. N. Oliveira (Eds.),
Relational and Algebraic Methods in Computer Science: 15th International Conference, RAMiCS 2015, Braga, Portugal, September 28 - October 1, 2015, Proceedings (pp. 326-343). (Lecture Notes in Computer Science; Vol. 9348). Springer Nature.
https://doi.org/10.1007/978-3-319-24704-5_20
Vancouver
Krivulin N.
Solving a tropical optimization problem via matrix sparsification. In Kahl W, Winter M, Oliveira JN, editors, Relational and Algebraic Methods in Computer Science: 15th International Conference, RAMiCS 2015, Braga, Portugal, September 28 - October 1, 2015, Proceedings. Cham: Springer Nature. 2015. p. 326-343. (Lecture Notes in Computer Science).
https://doi.org/10.1007/978-3-319-24704-5_20
Author
BibTeX
@inbook{4e634435ddaf435eb32d312a5dfa7a81,
title = "Solving a tropical optimization problem via matrix sparsification",
abstract = "An optimization problem, which arises in various applications as that of minimizing the span seminorm, is considered in the framework of tropical mathematics. The problem is to minimize a nonlinear function defined on vectors over an idempotent semifield, and calculated by means of multiplicative conjugate transposition. We find the minimum of the function, and give a partial solution which explicitly represents a subset of solution vectors. We characterize all solutions by a system of simultaneous equation and inequality, and exploit this characterization to investigate properties of the solutions. A matrix sparsification technique is developed to extend the partial solution to a wider solution subset, and then to a complete solution described as a family of subsets. We offer a backtracking procedure that generates all members of the family, and derive an explicit representation for the complete solution. Numerical examples and graphical illustrations of the results are presented.",
keywords = "tropical algebra, idempotent semifield, optimization problem, span seminorm, sparse matrix, backtracking, complete solution",
author = "Nikolai Krivulin",
note = "Krivulin N. (2015) Solving a Tropical Optimization Problem via Matrix Sparsification. In: Kahl W., Winter M., Oliveira J. (eds) Relational and Algebraic Methods in Computer Science. RAMICS 2015. Lecture Notes in Computer Science, vol 9348. Springer, Cham. https://doi.org/10.1007/978-3-319-24704-5_20; 15th International Conference on Relational and Algebraic Methods in Computer Science, RAMiCS 2015 ; Conference date: 28-09-2015 Through 01-10-2015",
year = "2015",
doi = "10.1007/978-3-319-24704-5_20",
language = "English",
isbn = "978-3-319-24703-8",
series = "Lecture Notes in Computer Science",
publisher = "Springer Nature",
pages = "326--343",
editor = "Wolfram Kahl and Michael Winter and Oliveira, {Jos{\'e} N.}",
booktitle = "Relational and Algebraic Methods in Computer Science",
address = "Germany",
url = "http://ramics2015.di.uminho.pt/",
}
RIS
TY - CHAP
T1 - Solving a tropical optimization problem via matrix sparsification
AU - Krivulin, Nikolai
N1 - Conference code: 15
PY - 2015
Y1 - 2015
N2 - An optimization problem, which arises in various applications as that of minimizing the span seminorm, is considered in the framework of tropical mathematics. The problem is to minimize a nonlinear function defined on vectors over an idempotent semifield, and calculated by means of multiplicative conjugate transposition. We find the minimum of the function, and give a partial solution which explicitly represents a subset of solution vectors. We characterize all solutions by a system of simultaneous equation and inequality, and exploit this characterization to investigate properties of the solutions. A matrix sparsification technique is developed to extend the partial solution to a wider solution subset, and then to a complete solution described as a family of subsets. We offer a backtracking procedure that generates all members of the family, and derive an explicit representation for the complete solution. Numerical examples and graphical illustrations of the results are presented.
AB - An optimization problem, which arises in various applications as that of minimizing the span seminorm, is considered in the framework of tropical mathematics. The problem is to minimize a nonlinear function defined on vectors over an idempotent semifield, and calculated by means of multiplicative conjugate transposition. We find the minimum of the function, and give a partial solution which explicitly represents a subset of solution vectors. We characterize all solutions by a system of simultaneous equation and inequality, and exploit this characterization to investigate properties of the solutions. A matrix sparsification technique is developed to extend the partial solution to a wider solution subset, and then to a complete solution described as a family of subsets. We offer a backtracking procedure that generates all members of the family, and derive an explicit representation for the complete solution. Numerical examples and graphical illustrations of the results are presented.
KW - tropical algebra
KW - idempotent semifield
KW - optimization problem
KW - span seminorm
KW - sparse matrix
KW - backtracking
KW - complete solution
U2 - 10.1007/978-3-319-24704-5_20
DO - 10.1007/978-3-319-24704-5_20
M3 - Chapter
SN - 978-3-319-24703-8
T3 - Lecture Notes in Computer Science
SP - 326
EP - 343
BT - Relational and Algebraic Methods in Computer Science
A2 - Kahl, Wolfram
A2 - Winter, Michael
A2 - Oliveira, José N.
PB - Springer Nature
CY - Cham
T2 - 15th International Conference on Relational and Algebraic Methods in Computer Science
Y2 - 28 September 2015 through 1 October 2015
ER -
