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

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

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.

Number Sequences in an Integral Form with a Generalized Convolution Property and Somos-4 Hankel Determinants

MSC 2010: 11B83, 05A19, 33C45

Estudo teórico das propriedades eletrônicas e termodinâmicas de nanofitas quasiperiódicas BCN

Nanoscale materials composed of boron, nitrogen, and carbon have unique properties and may be useful in new technologies. In this thesis, we investigate some properties of BCN nanoribbons constructed according to the Fibonacci quasiperiodic sequence. We analyze properties such as structural stability, electronic density of states, electronic specific heat, band structure, and energy band gap. We have performed first-principles calculations based on density functional theory implemented in the SIESTA code. The results showed that nanoribbons present a fixed value of the formation energy. The electronic density of states was used to calculate the specific heat. We found an oscillatory behavior of the electronic specific heat, in the low temperature regime. We analyze the electronic band structure to determine the energy band gap. The energy band gap oscillates as a function of the Fibonacci generation index n. Our work suggest that appropriate choice of the building block materials of the quasiperiodic sequence, may lead to a tuneable band gap of the quasiperiodic nanoribbons.

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

Échantillonnage basé sur les Tuiles de Penrose et applications en infographie

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Échantillonnage basé sur les Tuiles de Penrose et applications en infographie

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

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

Mathematical Programming Models for Influence Maximization on Social Networks

In this dissertation, we apply mathematical programming techniques (i.e., integer programming and polyhedral combinatorics) to develop exact approaches for influence maximization on social networks. We study four combinatorial optimization problems that deal with maximizing influence at minimum cost over a social network. To our knowl- edge, all previous work to date involving influence maximization problems has focused on heuristics and approximation. We start with the following viral marketing problem that has attracted a significant amount of interest from the computer science literature. Given a social network, find a target set of customers to seed with a product. Then, a cascade will be caused by these initial adopters and other people start to adopt this product due to the influence they re- ceive from earlier adopters. The idea is to find the minimum cost that results in the entire network adopting the product. We first study a problem called the Weighted Target Set Selection (WTSS) Prob- lem. In the WTSS problem, the diffusion can take place over as many time periods as needed and a free product is given out to the individuals in the target set. Restricting the number of time periods that the diffusion takes place over to be one, we obtain a problem called the Positive Influence Dominating Set (PIDS) problem. Next, incorporating partial incentives, we consider a problem called the Least Cost Influence Problem (LCIP). The fourth problem studied is the One Time Period Least Cost Influence Problem (1TPLCIP) which is identical to the LCIP except that we restrict the number of time periods that the diffusion takes place over to be one. We apply a common research paradigm to each of these four problems. First, we work on special graphs: trees and cycles. Based on the insights we obtain from special graphs, we develop efficient methods for general graphs. On trees, first, we propose a polynomial time algorithm. More importantly, we present a tight and compact extended formulation. We also project the extended formulation onto the space of the natural vari- ables that gives the polytope on trees. Next, building upon the result for trees---we derive the polytope on cycles for the WTSS problem; as well as a polynomial time algorithm on cycles. This leads to our contribution on general graphs. For the WTSS problem and the LCIP, using the observation that the influence propagation network must be a directed acyclic graph (DAG), the strong formulation for trees can be embedded into a formulation on general graphs. We use this to design and implement a branch-and-cut approach for the WTSS problem and the LCIP. In our computational study, we are able to obtain high quality solutions for random graph instances with up to 10,000 nodes and 20,000 edges (40,000 arcs) within a reasonable amount of time.

L'armonia della natura. Ruolo della musica e degli ultrasuoni nella viticoltura.

Questo elaborato ha come obiettivo quello di illustrare l'utilizzo della musica e degli ultrasuoni nella viticoltura come tecnica innovativa di prevenzione delle avversità della vite, quali patogeni, insetti, malattie, e altri fattori ambientali sfavorevoli come la siccità. In particolare, viene sviluppato il loro impiego contro il vettore della flavescenza dorata, lo Scaphoideus titanus, e nei confronti della specie Homalodisca vitripennis, vettore del batterio Xylella fastidiosa, il quale è responsabile della malattia di Pierce. Viene anche esposto l'uso della Protéodie all'interno dei vigneti e delle cantine francesi, dove queste “melodie delle proteine” agiscono sulla biosintesi proteica delle piante, amplificando la resistenza delle viti nei confronti del mal dell’esca.

Applicazioni tecnologiche e nuovi metodi di valutazione della performance negli sport acquatici

Nello sport di alto livello l’uso della tecnologia ha raggiunto un ruolo di notevole importanza per l’analisi e la valutazione della prestazione. Negli ultimi anni sono emerse nuove tecnologie e sono migliorate quelle pre-esistenti (i.e. accelerometri, giroscopi e software per l’analisi video) in termini di campionamento, acquisizione dati, dimensione dei sensori che ha permesso la loro “indossabilità” e l’inserimento degli stessi all’interno degli attrezzi sportivi. La tecnologia è sempre stata al servizio degli atleti come strumento di supporto per raggiungere l’apice dei risultati sportivi. Per questo motivo la valutazione funzionale dell’atleta associata all’uso di tecnologie si pone lo scopo di valutare i miglioramenti degli atleti misurando la condizione fisica e/o la competenza tecnica di una determinata disciplina sportiva. L’obiettivo di questa tesi è studiare l’utilizzo delle applicazioni tecnologiche e individuare nuovi metodi di valutazione della performance in alcuni sport acquatici. La prima parte (capitoli 1-5), si concentra sulla tecnologia prototipale chiamata E-kayak e le varie applicazioni nel kayak di velocità. In questi lavori è stata verificata l’attendibilità dei dati forniti dal sistema E-kayak con i sistemi presenti in letteratura. Inoltre, sono stati indagati nuovi parametri utili a comprendere il modello di prestazione del paddler. La seconda parte (capitolo 6), si riferisce all’analisi cinematica della spinta verticale del pallanuotista, attraverso l’utilizzo della video analisi 2D, per l’individuazione delle relazioni Forza-velocità e Potenza-velocità direttamente in acqua. Questo studio pilota, potrà fornire indicazioni utili al monitoraggio e condizionamento di forza e potenza da svolgere direttamente in acqua. Infine la terza parte (capitoli 7-8), si focalizza sull’individuazione della sequenza di Fibonacci (sequenza divina) nel nuoto a stile libero e a farfalla. I risultati di questi studi suggeriscono che il ritmo di nuotata tenuto durante le medie/lunghe distanze gioca un ruolo chiave. Inoltre, il livello di autosomiglianza (self-similarity) aumenta con la tecnica del nuoto.

Poset associahedra as sections of graph associahedra

Poset associahedra are a family of convex polytopes recently introduced by Pavel Galashin in 2021. The associahedron An is an (n-2)-dimensional convex polytope whose facial structure encodes the ways of parenthesizing an n-letter word (among several equivalent combinatorial objects). Associahedra are deeply studied polytopes that appear naturally in many areas of mathematics: algebra, combinatorics, geometry, topology... They have many presentations and generalizations. One of their incarnations is as a compactification of the configuration space of n points on a line. Similarly, the P-associahedron of a poset P is a compactification of the configuration space of order preserving maps from P to R. Galashin presents poset associahedra as combinatorial objects and shows that they can be realized as convex polytopes. However, his proof is not constructive, in the sense that no explicit coordinates are provided. The main goal of this thesis is to provide an explicit construction of poset associahedra as sections of graph associahedra, thus solving the open problem stated in Remark 1.5 of Galashin's paper.