### ?

## The complexity of tropical matrix factorization

Advances in Mathematics. 2014. Vol. 254. P. 138-156.

Shitov Y.

The tropical arithmetic operations on R are defined by a⊕b=min{a, b} and a⊗b=a+b. Let A be a tropical matrix and k a positive integer, the problem of Tropical Matrix Factorization (TMF) asks whether there exist tropical matrices B∈R^{m×k} and C∈R^{k×n} satisfying B⊗C=A. We show that no algorithm for TMF is likely to work in polynomial time for every fixed k, thus resolving a problem proposed by Barvinok in 1993.

Shitov Y., Journal of Combinatorial Theory, Series A 2014 Vol. 126 P. 166-176

The smallest integer k for which the elements of a real matrix A can be expressed as A_ij = min B_it + C_tj with B an m-by-k matrix and C an k-by-n matrix is called the combinatorial rank of A. This notion was introduced by Barvinok in 1993, and he posed a problem on the ...

Added: May 24, 2014

Gribanov D., Malyshev D., Журнал Средневолжского математического общества 2016 Т. 18 № 3 С. 19-31

Мы рассматриваем естественные постановки задач о независимом множестве, о вершинном и о реберном доминирующем множестве как задач целочисленного линейного программирования и доказываем полиномиальную разрешимость этих задач для классов графов, имеющих ограниченные по абсолютному значению миноры (расширенных) матриц ограничений. ...

Added: October 20, 2016

Sirotkin D., Malyshev D., Lobachevskii Journal of Mathematics 2021 Vol. 42 No. 4 P. 760-766

The vertex 3-colourability problem is to verify whether it is possible to split the vertex set of a given graph into three subsets of pairwise nonadjacent vertices or not. This problem is known to be NP-complete for planar graphs of the maximum face length at most 4 (and, even, additionally, of the maximum vertex degree ...

Added: June 5, 2021

Shitov Y., SIAM Journal on Optimization 2018 Vol. 28 No. 3 P. 2067-2072

Gouveia, Parrilo, and Thomas gave a description of certain rank functions of matrices in geometric terms, generalizing a celebrated result of Yannakakis on the nonnegative rank. We analyze the algorithmic complexity of their description using the results of Renegar on the first-order theory of the reals. This gives a proof that matrices whose positive semidefinite ...

Added: September 26, 2018

Shitov Y., 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. ...

Added: February 23, 2016

Shitov Y., Вестник Московского университета. Серия 1: Математика. Механика 2011 № 5 С. 58-61

We present an example of a 6x6 matrix A with tropical rank equal to 4 and Kapranov rank equal to 5. This disproves the conjecture formulated by M. Chan, A. Jensen, and E. Rubei. ...

Added: January 6, 2013

Shvydun S., Normative properties of multi-criteria choice procedures and their superpositions: II / Высшая школа экономики. Series WP7 "Математические методы анализа решений в экономике, бизнесе и политике". 2015. No. WP7/2015/07.

Two-stage superposition choice procedures, which sequentially apply two choice procedures so that the result of the first choice procedure is the input for the second choice procedure, are studied. We define which of them satisfy given normative conditions, showing how a final choice is changed due to the changes of preferences or a set of ...

Added: October 20, 2015

Shitov Y., Linear Algebra and its Applications 2012 Vol. 437 No. 11 P. 2727-2732

The notion of the factor rank of tropical matrices is considered. We construct a linear-time algorithm that either finds a full-rank 3 × 3 submatrix of a given matrix A or concludes that the factor rank of A is less than 3. We show that there exist matrices of factor rank 4 whose 4 × 4 submatrices are all rank ...

Added: January 6, 2013

Shitov Y., St Petersburg Mathematical Journal 2014 Vol. 26 No. 2 P. 216-228

The tropical arithmetic operations on R are defined as (a,b) -> min{a,b} and (a,b) -> a+b. We are interested in the concept of a semimodule, which is rather ill-behaved in tropical mathematics. In our paper we study the semimodules S in R^n having topological dimension two, and we show that any such S has always ...

Added: May 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 ...

Added: February 1, 2015

Malyshev D., Дискретная математика 2009 Т. 21 № 4 С. 129-134

The notion of a boundary class is a useful notion in the investigation of the complexity of extremal problems on graphs. One boundary class is known for the independent set problem and three boundary classes are known for the dominating set problem. In this paper it is proved that the set of boundary classes for ...

Added: November 25, 2012

Malyshev D., Дискретная математика 2012 Т. 24 № 2 С. 75-78

В данной работе исследуются семейства граничных классов для задач о вершинной k-раскраске и о хроматическом числе. Указано континуальное семейство классов графов, являющихся граничными одновременно для первой задачи при k=3 и для второй. Для любого k>3 выявлено континуальное семейство граничных классов для первой задачи, не являющихся граничными для второй. Для задачи о хроматическом числе найден граничный ...

Added: November 30, 2012

Korpelainen N., Lozin V. V., Malyshev D. et al., Theoretical Computer Science 2011 No. 412 P. 3545-3554

The notion of a boundary graph property was recently introduced as a relaxation of that of a minimal property and was applied to several problems of both algorithmic and combinatorial nature. In the present paper, we first survey recent results related to this notion and then apply it to two algorithmic graph problems: Hamiltonian cycle ...

Added: September 11, 2012

Gillis N., Shitov Y., Linear Algebra and its Applications 2019 Vol. 581 P. 367-382

The low-rank matrix approximation problem with respect to the entry-wise l∞-norm is the following: given a matrix M and a factorization rank r, find a matrix X whose rank is at most r and that minimizes max_i,j | M_ij − X_ij |. In this paper, we prove that the decision variant of this problem for ...

Added: November 11, 2020

Malyshev D., Дискретный анализ и исследование операций 2012 Т. 19 № 3 С. 58-64

An algorithm is implemented in the article for finding the independence number of a n-vertex graph from the class Free({P5,C5, Kp}) in time O(np+O(1)). ...

Added: June 6, 2012

Vassiliev V., Moscow Mathematical Journal 2017 Vol. 17 No. 4 P. 825-836

The local multiplicities of the caustics, the Maxwell sets, and the complex Stokes' sets in the spaces of versal deformations of Pham singularities (that is, of germs of holomorphic functions C^n --> C^1 which are expressed by the sums of degrees of the coordinate functions) are calculated ...

Added: December 27, 2017

Shitov Y., Linear Algebra and its Applications 2012 Vol. 436 No. 9 P. 3247-3253

We investigate the Kapranov rank functions of tropical matrices for different ground fields. For any infinite ground field we show that the rank-product inequality holds for Kapranov rank, and we prove that the Kapranov rank respects Green’s preorders on the semigroup of tropical n-by-n matrices. The rank-product inequality is shown to fail for Kapranov rank ...

Added: November 9, 2012

Goldengorin B. I., Malyshev D., Pardalos P. M., 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 ...

Added: June 23, 2013

Malyshev D., Journal of Applied and Industrial Mathematics 2013 Vol. 7 No. 2 P. 221-228

The notion of a boundary class of graphs is a helpful tool for the computational complexity analysis of graph theory problems in the family of hereditary classes. Some general and specific features for families of boundary classes of graphs for the vertex k-colorability problem and its “limit” variant, the chromatic index problem, were studied by ...

Added: June 23, 2013

Malyshev D., Дискретный анализ и исследование операций 2012 Т. 19 № 6 С. 37-48

Понятие граничного класса графов является полезным инструментом для анализа вычислительной сложности задач на графах в семействе наследственных классов. В предыдущих работах автора исследовались общие черты и особенности семейств граничных классов графов для задачи о вершинной k-раскраске и ее «предельного варианта» - задачи о хроматическом числе. В данной работе эта проблематика рассматривается применительно к реберному варианту ...

Added: November 30, 2012

Shitov Y., Linear and Multilinear Algebra 2015

We give a tropical proof of a recent result of Mohindru on the CP-rank conjecture over min-max semiring. ...

Added: April 14, 2015

Malyshev D., Discrete Mathematics and Applications 2010 Vol. 19 No. 6 P. 625-630

The notion of a boundary class is a useful notion in the investigation of the complexity of extremal problems on graphs. One boundary class is known for the independent set problem and three boundary classes are known for the dominating set problem. In this paper it is proved that the set of boundary classes for ...

Added: November 25, 2012

Shitov Y., 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. ...

Added: October 5, 2013

Shitov Y., Information Processing Letters 2018 Vol. 135 P. 92-94

Let G = (V , E) be a finite simple graph. Recall that a proper coloring of G is a mapping φ : V → {1, . . . , k} such that every color class induces an independent set. Such a φ is called a semi-matching coloring if the union of any two consecutive ...

Added: September 26, 2018