### ?

## Tropical semimodules of dimension two

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

Shitov Y.

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 a finite weak dimension not exceeding n. For a fixed k, we construct a polynomial time algorithm deciding whether S is contained in some tropical semimodule of weak dimension k or not. The latter result

provides a solution of a problem that has been open for eight years.

Shitov Y., St Petersburg Mathematical Journal 2015 Vol. 26 P. 341-350

In the paper, the concept of a semimodule is discussed, which is rather ill-behaved in tropical mathematics. The semimodules S in R^n having topological dimension two are studied, and it is shown that any such S has a finite weak dimension not exceeding n. For a fixed k, a polynomial time algorithm is constructed that ...

Added: August 12, 2015

Penskoi A., А. А. Гайфуллин, Смирнов С. В., М.: Московский центр непрерывного математического образования, 2014

Данное пособие содержит подробные решения типовых задач курса линейной алгебры и геометрии, читаемого на мехмате МГУ им. М. В. Ломоносова.
Для студентов естественнонаучных специальностей, в первую очередь физико-математических. ...

Added: March 21, 2017

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

Vorob'ev E. M., International Journal of Engineering Pedagogy 2012 Vol. 2 No. 3 P. 47-51

We discuss the online teaching of Linear algebra using the Wolfram Research software product called web- Mathematica. The teaching is based on interactive electronic tutorials developed by the author. The tutorials provide distant students with the instruments of remote calculation and visualization of the calculation results. All this increases the chances for students to deepen ...

Added: December 13, 2012

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

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

Added: November 30, 2012

Shitov Y., Advances in Mathematics 2014 Vol. 254 P. 138-156

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 ...

Added: January 10, 2014

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

Guterman A., Shitov Y., Linear Algebra and its Applications 2012 Vol. 437 No. 7 P. 1793-1811

We introduce the notion of the tropical matrix pattern, which provides a powerful tool to investigate tropical matrices. The above
approach is then illustrated by the application to the study of the properties of the Gondran–Minoux rank function. Our main result states that up to a multiplication of matrix rows by non-zero constants the Gondran–Minoux independence ...

Added: November 9, 2012

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

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

Added: November 30, 2012

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

Vyacheslav V. Chistyakov, Switzerland: Springer, 2015

Aimed toward researchers and graduate students familiar with elements of functional analysis, linear algebra, and general topology; this book contains a general study of modulars, modular spaces, and metric modular spaces. Modulars may be thought of as generalized velocity fields and serve two important purposes: generate metric spaces in a unified manner and provide a ...

Added: December 31, 2015

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

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

Shitov Y., International Journal of Algebra and Computation 2014 Vol. 24 No. 8 P. 1183-1189

We present a number of new results on the multiplicative structure of univariate polynomials over the Boolean and tropical semirings.We answer the question asked by Kim and Roush in 2005 by proving that almost all Boolean polynomials with nonzero constant term are irreducible.We also give a lower bound for the number of reducible polynomials, and ...

Added: January 8, 2015

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

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., Дискретный анализ и исследование операций 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

Shitov Y., A semigroup identity for tropical 3x3 matrices / Cornell University. Series math "arxiv.org". 2014. No. 1406.2601.

We construct a nontrivial identity which holds in the semigroup of tropical 3-by-3 matrices. ...

Added: March 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., 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., 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., Дискретная математика 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

Nicolas Gillis, 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