Solving a tropical optimization problem via matrix sparsification

Результат исследований: Публикации в книгах, отчётах, сборниках, трудах конференцийглава/разделнаучнаярецензирование

4 Цитирования (Scopus)

Аннотация

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.
Язык оригиналаанглийский
Название основной публикации Relational and Algebraic Methods in Computer Science
Подзаголовок основной публикации15th International Conference, RAMiCS 2015, Braga, Portugal, September 28 - October 1, 2015, Proceedings
РедакторыWolfram Kahl, Michael Winter, José N. Oliveira
Место публикацииCham
ИздательSpringer Nature
Страницы326-343
ISBN (электронное издание)978-3-319-24704-5
ISBN (печатное издание)978-3-319-24703-8
DOI
СостояниеОпубликовано - 2015
Событие15th International Conference on Relational and Algebraic Methods in Computer Science - Braga, Португалия
Продолжительность: 28 сен 20151 окт 2015
Номер конференции: 15
http://ramics2015.di.uminho.pt/

Серия публикаций

НазваниеLecture Notes in Computer Science
ИздательSpringer
Том9348
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

конференция

конференция15th International Conference on Relational and Algebraic Methods in Computer Science
Сокращенный заголовокRAMiCS 2015
СтранаПортугалия
ГородBraga
Период28/09/151/10/15
Адрес в сети Интернет

Предметные области Scopus

  • Теория оптимизации
  • Алгебра и теория чисел

Fingerprint Подробные сведения о темах исследования «Solving a tropical optimization problem via matrix sparsification». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать