Действия за год
Аннотация
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.
Язык оригинала | английский |
---|---|
Название основной публикации | Relational and Algebraic Methods in Computer Science |
Подзаголовок основной публикации | 16th International Conference, RAMiCS 2017, Lyon, France, May 15-18, 2017, Proceedings |
Редакторы | Peter Höfner, Damien Pous, Georg Struth |
Место публикации | Cham |
Издатель | Springer Nature |
Страницы | 226-241 |
ISBN (электронное издание) | 978-3-319-57418-9 |
ISBN (печатное издание) | 978-3-319-57417-2 |
DOI | |
Состояние | Опубликовано - 2017 |
Событие | The 16th International Conference on Relational and Algebraic Methods in Computer Science - Université de Lyon, Lyon, Франция Продолжительность: 15 мая 2017 → 18 мая 2017 Номер конференции: 16 http://www.ens-lyon.fr/LIP/PLUME/RAMiCS17/ |
Серия публикаций
Название | Lecture Notes in Computer Science |
---|---|
Издатель | Springer International Publishing |
Том | 10226 |
ISSN (печатное издание) | 0302-9743 |
ISSN (электронное издание) | 1611-3349 |
конференция
конференция | The 16th International Conference on Relational and Algebraic Methods in Computer Science |
---|---|
Сокращенный заголовок | RAMiCS 2017 |
Страна/Tерритория | Франция |
Город | Lyon |
Период | 15/05/17 → 18/05/17 |
Адрес в сети Интернет |
Предметные области Scopus
- Теория оптимизации
- Теория управления и исследование операций
- Алгебра и теория чисел
Fingerprint
Подробные сведения о темах исследования «Complete solution of an optimization problem in tropical semifield». Вместе они формируют уникальный семантический отпечаток (fingerprint).Виды деятельности
-
Complete solution of an optimization problem in tropical semifield
Николай Кимович Кривулин (Докладчик)
18 мая 2017Деятельность: выступление › выступление с устной презентацией
-
The 16th International Conference on Relational and Algebraic Methods in Computer Science
Николай Кимович Кривулин (Участник)
15 мая 2017 → 18 мая 2017Деятельность: Участие в мероприятиях или организация мероприятий (событий) › Участие в конференции, заседании рабочей группы, ...