?
The complexity of tropical matrix factorization
Advances in Mathematics. 2014. Vol. 254. P. 138-156.
Шитов Я. Н.
Шитов Я. Н., Journal of Combinatorial Theory, Series A 2014 Vol. 126 P. 166-176
Добавлено: 24 мая 2014 г.
Грибанов Д. В., Малышев Д. С., Журнал Средневолжского математического общества 2016 Т. 18 № 3 С. 19-31
Мы рассматриваем естественные постановки задач о независимом множестве, о вершинном и о реберном доминирующем множестве как задач целочисленного линейного программирования и доказываем полиномиальную разрешимость этих задач для классов графов, имеющих ограниченные по абсолютному значению миноры (расширенных) матриц ограничений. ...
Добавлено: 20 октября 2016 г.
Сироткин Д. В., Малышев Д. С., Lobachevskii Journal of Mathematics 2021 Vol. 42 No. 4 P. 760-766
Добавлено: 5 июня 2021 г.
Шитов Я. Н., SIAM Journal on Optimization 2018 Vol. 28 No. 3 P. 2067-2072
Добавлено: 26 сентября 2018 г.
Шитов Я. Н., American Mathematical Monthly 2016 Vol. 123 No. 1 P. 71-77
We present an infinite sequence of pairs (An, Bn) of chess positions on an n × n board such that (1) there is a legal sequence of chess moves leading from An to Bn and (2) any legal sequence leading from An to Bn contains at least exp(n + o(n)) moves. ...
Добавлено: 23 февраля 2016 г.
Шитов Я. Н., Вестник Московского университета. Серия 1: Математика. Механика 2011 № 5 С. 58-61
Мы приводим пример 6х6-матрицы с тропическим рангом 4 и рангом Капранова 5, опровергая гипотезу, предложенную М. Чан, А. Йенсеном и Е. Рубеи. ...
Добавлено: 6 января 2013 г.
Швыдун С. В., / Высшая школа экономики. Series WP7 "Математические методы анализа решений в экономике, бизнесе и политике". 2015. No. WP7/2015/07.
Исследуются двухступенчатые процедурывыбора, которые представляют собой суперпозицию двух процедур выбора. Показано, какие из рассматриваемых процедур выбора удовлетворяют существующим нормативным условиям, описывающим, каким образом изменяется конечный выбор при изменении предъявляемого множества альтернатив и оценок альтернатив по критериям. Особое внимание уделяется двухступенчатым процедурам, в основе которых лежат позиционные правила, а также правила, использующие мажоритарное отношение, вспомогательную числовую ...
Добавлено: 20 октября 2015 г.
Шитов Я. Н., Linear Algebra and its Applications 2012 Vol. 437 No. 11 P. 2727-2732
Рассматривается понятие факторизационного ранга тропической матрицы. Построен линейный по времени алгоритм, который либо находит подматрицу размера 3х3 полного факторизационного ранга, либо заключает, что факторизационный ранг заданной матрицы меньше двух. Приведен пример матрицы факторизационного ранга 4, никак ая 4х4 подматрица которой не имеет полного ранга. ...
Добавлено: 6 января 2013 г.
Шитов Я. Н., St Petersburg Mathematical Journal 2014 Vol. 26 No. 2 P. 216-228
Добавлено: 24 мая 2014 г.
Providence : American Mathematical Society, 2014
This volume contains the proceedings of the International Workshop on Tropical and Idempotent Mathematics, held at the Independent University of Moscow, Russia, from August 26-31, 2012. The main purpose of the conference was to bring together and unite researchers and specialists in various areas of tropical and idempotent mathematics and applications. This volume contains articles ...
Добавлено: 1 февраля 2015 г.
Малышев Д. С., Дискретная математика 2009 Т. 21 № 4 С. 129-134
Понятие граничного класса — полезный инструмент изучения сложности экстремальных задач на графах. В настоящее время известны один граничный класс для задачи о независимом множестве и три граничных класса для задачи о доминирующем множестве. В настоящей работе доказывается бесконечность множества граничных классов для задачи о 3-раскраске. ...
Добавлено: 25 ноября 2012 г.
Малышев Д. С., Дискретная математика 2012 Т. 24 № 2 С. 75-78
В данной работе исследуются семейства граничных классов для задач о вершинной k-раскраске и о хроматическом числе. Указано континуальное семейство классов графов, являющихся граничными одновременно для первой задачи при k=3 и для второй. Для любого k>3 выявлено континуальное семейство граничных классов для первой задачи, не являющихся граничными для второй. Для задачи о хроматическом числе найден граничный ...
Добавлено: 30 ноября 2012 г.
Корпелайнен Н., Лозин В. В., Малышев Д. С. и др., Theoretical Computer Science 2011 No. 412 P. 3545-3554
Понятие граничного свойства графов было недавно введено в качестве релаксации минимального по включению свойства и было применено к нескольким задачам алгоритмической и комбинаторной природы. В настоящей работе мы в начале делаем обзор недавних результатов, связанных с этими понятием, а затем применяем их к двум алгоритмическим задачам: задаче о гамильтоновом цикле и задаче о вершинной k-раскраске. ...
Добавлено: 11 сентября 2012 г.
Gillis N., Шитов Я. Н., Linear Algebra and its Applications 2019 Vol. 581 P. 367-382
Добавлено: 11 ноября 2020 г.
Малышев Д. С., Дискретный анализ и исследование операций 2012 Т. 19 № 3 С. 58-64
В работе предлагается алгоритм, который определяет число независимости n-вершинного графа из класса Free({P5,C5, Kp}) за время O(np+O(1)). ...
Добавлено: 6 июня 2012 г.
Васильев В. А., Moscow Mathematical Journal 2017 Vol. 17 No. 4 P. 825-836
Добавлено: 27 декабря 2017 г.
Шитов Я. Н., Linear Algebra and its Applications 2012 Vol. 436 No. 9 P. 3247-3253
Изучаются функции ранга Капранова тропических матриц для различных базовых полей. Для любого бесконечного базового поля мы показываем, что неравенство для ранга произведения матриц выполняется для ранга Капранова, и доказываем монотонность ранга Капранова относительно предпорядков Грина на полугруппе тропических матриц. Неравенство на ранг произведения, вообще говоря, не выполняется ни над каким конечным базовым полем, как показывает ...
Добавлено: 9 ноября 2012 г.
Гольденгорин Б. И., Малышев Д. С., Пардалос П. О., Doklady Mathematics 2013 Vol. 87 No. 3 P. 368-371
The notion of a tolerance of an element of a combinatorial optimization problem is often used for stability analysis of an optimal solution and it is a base for design branch-and-bound algorithms solving such problems. In this paper we show that for the weighted independent set problem on trees with n vertices all upper and ...
Добавлено: 23 июня 2013 г.
Малышев Д. С., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2013 Vol. 7 No. 2 P. 221-228
Добавлено: 23 июня 2013 г.
Малышев Д. С., Дискретный анализ и исследование операций 2012 Т. 19 № 6 С. 37-48
Понятие граничного класса графов является полезным инструментом для анализа вычислительной сложности задач на графах в семействе наследственных классов. В предыдущих работах автора исследовались общие черты и особенности семейств граничных классов графов для задачи о вершинной k-раскраске и ее «предельного варианта» - задачи о хроматическом числе. В данной работе эта проблематика рассматривается применительно к реберному варианту ...
Добавлено: 30 ноября 2012 г.
Шитов Я. Н., Linear and Multilinear Algebra 2015
Добавлено: 14 апреля 2015 г.
Малышев Д. С., Discrete Mathematics and Applications 2010 Vol. 19 No. 6 P. 625-630
Понятие граничного класса — полезный инструмент изучения сложности экстремальных задач на графах. В настоящее время известны один граничный класс для задачи о независимом множестве и три граничных класса для задачи о доминирующем множестве. В настоящей работе доказывается бесконечность множества граничных классов для задачи о 3-раскраске. ...
Добавлено: 25 ноября 2012 г.
Шитов Я. Н., Proceedings of the American Mathematical Society 2014 Vol. 142 P. 15-19
We show that neither the Barvinok rank nor the Kapranov rank of a tropical matrix M can be defined in terms of the regular mixed subdivision produced by M. This answers a question asked by Develin, Santos and Sturmfels. ...
Добавлено: 5 октября 2013 г.
Шитов Я. Н., Information Processing Letters 2018 Vol. 135 P. 92-94
Добавлено: 26 сентября 2018 г.