Description Reduction for Restricted Sets of (0,1) Matrices

* The research is supported partly by INTAS: 04-77-7173 project, http://www.intas.be

Алгоритмы Решения Систем Линейных Диофантовых Уравнений в Дискретных Областях

Abstract.The algorithms for computation of minimal supported set of solutions for systems of linear Diophantine homogeneous equations over set of natural numbers and basis of systems of linear Diophantine homogeneous and inhomogeneous equations in ring and field of remainders on modulo of a number.

Многокритериальные Задачи на Комбинаторном Множестве Полиразмещений: Структурные Свойства Решений

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

Векторные Задачи на Комбинаторном Множестве Полиразмещений: Условия Оптимальности и Подход к Решению

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

Generating More Boundary Elements of Subset Projections

Composition problem is considered for partition constrained vertex subsets of n dimensional unit cube E^n . Generating numerical characteristics of E^n subsets partitions is considered by means of the same characteristics in 1 − n dimensional unit cube, and construction of corresponding subsets is given for a special particular case. Using pairs of lower layer characteristic vectors for E^(1-n) more characteristic vectors for E^n are composed which are boundary from one side, and which take part in practical recognition of validness of a given candidate vector of partitions.

As representações externas - na resolução de problemas matemáticos no 2º e 3º anos do ensino básico

Relatório de estágio para obtenção de grau de mestre em Educação pré-escolar e Ensino do 1º ciclo do ensino básico

On f-vectors of polytopes and matroids

Thesis (Ph.D.)--University of Washington, 2016-08

Extended formulations, nonnegative factorizations, and randomized communication protocols

An extended formulation of a polyhedron P is a linear description of a polyhedron Q together with a linear map π such that π(Q)=P. These objects are of fundamental importance in polyhedral combinatorics and optimization theory, and the subject of a number of studies. Yannakakis’ factorization theorem (Yannakakis in J Comput Syst Sci 43(3):441–466, 1991) provides a surprising connection between extended formulations and communication complexity, showing that the smallest size of an extended formulation of $$P$$P equals the nonnegative rank of its slack matrix S. Moreover, Yannakakis also shows that the nonnegative rank of S is at most 2^c, where c is the complexity of any deterministic protocol computing S. In this paper, we show that the latter result can be strengthened when we allow protocols to be randomized. In particular, we prove that the base-2 logarithm of the nonnegative rank of any nonnegative matrix equals the minimum complexity of a randomized communication protocol computing the matrix in expectation. Using Yannakakis’ factorization theorem, this implies that the base-2 logarithm of the smallest size of an extended formulation of a polytope P equals the minimum complexity of a randomized communication protocol computing the slack matrix of P in expectation. We show that allowing randomization in the protocol can be crucial for obtaining small extended formulations. Specifically, we prove that for the spanning tree and perfect matching polytopes, small variance in the protocol forces large size in the extended formulation.

As representações externas - na resolução de problemas matemáticos no 2º e 3º anos do ensino básico

Relatório de estágio para obtenção de grau de mestre em Educação pré-escolar e Ensino do 1º ciclo do ensino básico

Privileged Words and Sturmian Words

This dissertation has two almost unrelated themes: privileged words and Sturmian words. Privileged words are a new class of words introduced recently. A word is privileged if it is a complete first return to a shorter privileged word, the shortest privileged words being letters and the empty word. Here we give and prove almost all results on privileged words known to date. On the other hand, the study of Sturmian words is a well-established topic in combinatorics on words. In this dissertation, we focus on questions concerning repetitions in Sturmian words, reproving old results and giving new ones, and on establishing completely new research directions. The study of privileged words presented in this dissertation aims to derive their basic properties and to answer basic questions regarding them. We explore a connection between privileged words and palindromes and seek out answers to questions on context-freeness, computability, and enumeration. It turns out that the language of privileged words is not context-free, but privileged words are recognizable by a linear-time algorithm. A lower bound on the number of binary privileged words of given length is proven. The main interest, however, lies in the privileged complexity functions of the Thue-Morse word and Sturmian words. We derive recurrences for computing the privileged complexity function of the Thue-Morse word, and we prove that Sturmian words are characterized by their privileged complexity function. As a slightly separate topic, we give an overview of a certain method of automated theorem-proving and show how it can be applied to study privileged factors of automatic words. The second part of this dissertation is devoted to Sturmian words. We extensively exploit the interpretation of Sturmian words as irrational rotation words. The essential tools are continued fractions and elementary, but powerful, results of Diophantine approximation theory. With these tools at our disposal, we reprove old results on powers occurring in Sturmian words with emphasis on the fractional index of a Sturmian word. Further, we consider abelian powers and abelian repetitions and characterize the maximum exponents of abelian powers with given period occurring in a Sturmian word in terms of the continued fraction expansion of its slope. We define the notion of abelian critical exponent for Sturmian words and explore its connection to the Lagrange spectrum of irrational numbers. The results obtained are often specialized for the Fibonacci word; for instance, we show that the minimum abelian period of a factor of the Fibonacci word is a Fibonacci number. In addition, we propose a completely new research topic: the square root map. We prove that the square root map preserves the language of any Sturmian word. Moreover, we construct a family of non-Sturmian optimal squareful words whose language the square root map also preserves.This construction yields examples of aperiodic infinite words whose square roots are periodic.