RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Зап. научн. сем. ПОМИ:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Зап. научн. сем. ПОМИ, 2016, том 450, страницы 43–61 (Mi znsl6336)  

Алгоритм поиска решения переопределенной тропической линейной системы с помощью анализа стабильных точек подсистем

А. Давыдов

С.-Петербургский национальный исследовательский Академический университет Российской академии наук (СПбАУ РАН)

Аннотация: В данной статье доказывается, что для любой переопределенной линейной тропической системы найдется квадратная подсистема, такая, что ее стабильное решение будет решением исходной системы. Это позволяет построить простой алгоритм, решающий переопределенные тропические линейные системы с конечными целочисленными коэфициентами за время $O((C_m^nn ^2+n^3)M(N))$, где $m$ – количество уравнений, $n$ – количество переменных, а $M(N)$ – время арифметических операций с числами, не превосходящими максимальное число в матрице по модулю. Для слабопереопределенных систем это время работы полиномиально. Библ. – 10 назв.

Ключевые слова: тропические линейные системы, слабопереопределенные тропические линейные системы.

Полный текст: PDF файл (221 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Journal of Mathematical Sciences (New York), 2018, 232:1, 25–35

Реферативные базы данных:

Тип публикации: Статья
УДК: 512.7
Поступило: 18.10.2016

Образец цитирования: А. Давыдов, “Алгоритм поиска решения переопределенной тропической линейной системы с помощью анализа стабильных точек подсистем”, Комбинаторика и теория графов. VIII, Зап. научн. сем. ПОМИ, 450, ПОМИ, СПб., 2016, 43–61; J. Math. Sci. (N. Y.), 232:1 (2018), 25–35

Цитирование в формате AMSBIB
\RBibitem{Dav16}
\by А.~Давыдов
\paper Алгоритм поиска решения переопределенной тропической линейной системы с~помощью анализа стабильных точек подсистем
\inbook Комбинаторика и теория графов.~VIII
\serial Зап. научн. сем. ПОМИ
\yr 2016
\vol 450
\pages 43--61
\publ ПОМИ
\publaddr СПб.
\mathnet{http://mi.mathnet.ru/znsl6336}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3582952}
\transl
\jour J. Math. Sci. (N. Y.)
\yr 2018
\vol 232
\issue 1
\pages 25--35
\crossref{https://doi.org/10.1007/s10958-018-3856-3}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85047334309}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/znsl6336
  • http://mi.mathnet.ru/rus/znsl/v450/p43

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Записки научных семинаров ПОМИ
    Просмотров:
    Эта страница:49
    Полный текст:10
    Литература:6
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019