Made available in DSpace on 2014-06-12T18:28:59Z (GMT). No. of bitstreams: 2 arquivo648_1.pdf: 827994 bytes, checksum: 5bd18eefcbed6a0d647716cdc47627b9 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2011 / Conselho Nacional de Desenvolvimento Científico e Tecnológico / Bixby e Cunningham relacionaram graficidade de matroides binárias 3-conexas e cocircuitos não separadores, generalizando um critério de planaridade de grafos 3-conexos de Tutte. Lemos estudou o conjunto de cocircuitos não-separadores que evita um elemento de uma matroide binária 3-conexa e conseguiu outra caracterização: M é gráfica se e só se cada elemento de M evita exatamente r (M)¡1 cocircuitos não separadores. Aqui estudamos o conjunto Y (M), dessas obstruções para graficidade, formado pelos elementos de M que evitam no mínimo r (M) cocircuitos não-separadores. Mostramos que, numa matroide binária 3-conexa existem 3 circuitos contidos em Y (M), cada qual não contido na união dos outros dois. Isso implica numa generalização do resultado de Lemos. No caso em que M não possui menor M¤(K000 3,3) ou M não é regular, conseguimos resultado muito melhor: jE(M)¡Y (M)j · 1. A demonstração desses resultados se baseia numa extensão de alguns resultados de Whittle a respeito demenores de matroide 3-conexas, que também são desenvolvido aqui: Seja M uma matroide binária e 3-conexa com um menor 3-conexo N. Suponha que r (M) ¸ r (N)Å3. Então existe um 3-coindependente I ¤ de M tal que co(M\e) é 3-conexa com menor isomorfo a N para todo e 2 I ¤. No mesmo capítulo desse teorema mostramos ainda uma versão para grafos que, porém, não se extende para matroides binárias

Tesis para optar al grado de Magíster en Ciencias de la Ingeniería, Mención Matemáticas Aplicadas / Memoria para optar al título de Ingeniero Civil Matemático / Estudiamos el problema de bases de peso mínimo en matroides en un contexto donde los pesos en los elementos son inciertos. Inicialmente, para cada elemento $e$ de una matroide $(E,\I)$ se conocerá un conjunto no vacío $A_e \subseteq \mathbb R$, llamado área de incertidumbre, que contiene los posibles pesos del elemento $e$. El algoritmo puede escoger un conjunto de elementos $X\subseteq E$ a consultar, de manera que si un elemento $e$ es consultado se obtiene un peso $w_e \in A_e$ con un costo de consulta $c_e \in \mathbb R$ asociado. El objetivo es encontrar un conjunto $X \subseteq E$ que, al consultarlo, permita calcular una base de peso mínimo independiente del valor de las aristas no reveladas. A estos conjuntos se les llamará consultas factible; tenemos particular interés en encontrar una de costo mínimo. Esto es de especial interés en aplicaciones donde obtener datos exactos es díficil o costoso, pero datos vagos son de fácil acceso. El problema adaptativo bajo análisis competitivo fue estudiado anteriormente. En este trabajo consideramos el caso no adaptativo; es decir, cuando los elementos a consultar se eligen todos al mismo tiempo. Formalizamos el problema, definimos las bases de peso mínimo en el contexto incierto, caracterizamos su existencia y demostramos que son las bases de una matroide. Proveemos una caracterización de las consultas factibles de tamaño mínimo, probamos que los complementos de consultas factibles forman una matroide sencilla y esto nos permite idear un algoritmo que encuentra una consulta factible de costo mínimo con una cantidad polinomial tanto de recursos computacionales como de llamadas al oráculo de independencia de la matroide / FONDECYT Regular N° 1181180 y CMM - Conicyt PIA AFB170001

Magíster en Ciencias de la Ingeniería, Mención Matemáticas Aplicadas. Ingeniero Civil Matemático / Estudiamos una generalización del problema de la secretaria llamada el problema matroidal de la secretaria propuesta en 2007 por Babaioff et al. [1]. En este problema, los elementos de una matroide se revelan en orden aleatorio. Al observar un elemento, debemos decidir de forma irrevocable si incluirlo o no en nuestra solución. Los elementos aceptados deben formar un conjunto independiente y deseamos que sea cercano al independiente óptimo. En su trabajo, Babaioff et al. [1] conjeturaron la existencia de un algoritmo O(1)-competitivo para este problema en cualquier matroide. Dicha conjetura sigue abierta, y solo se ha podido probar en clases particulares de matroides. Por un lado esta tesis sirve como lectura introductoria al problema ya que incluye una introducción a lo que son las matroides y al problema de la secretaria. Por otro lado presentamos nuevos resultados sobre este problema. Desarrollamos una nueva técnica para diseñar y analizar algoritmos con la cual obtenemos nuevos algoritmos O(1)-competitivos para cuatro clases de matroides: transversales, gráficas, laminares y un tipo especial de matroides representables que llamaremos k-sparsas. En todos estos casos, nuestros algoritmos funcionan aún bajo hipótesis más restrictivas que las del problema original, y logran una mejor competitividad que la de los mejores algoritmos publicados para esos problemas. Además planteamos y estudiamos algunas variantes del problema. / Este trabajo ha sido parcialmente financiado por Fondecyt de Iniciación 11130266: APPROXIMATIONALGORITHMS FOR INCREMENTAL SELECTION PROBLEMS

This thesis is dedicated to the study of secret sharing schemes, which are cryptographic methods to share information in a secure way. The topics that are considered in the thesis are two of the main open problems in secret sharing: the characterization of the ideal access structures and the optimization of the length of the shares for general access structures. These open problems are studied for multipartite secret sharing schemes. In these schemes the set of participants is divided into parts and the participants in each part have the same rights to obtain the secret. The results of the thesis are based on a new combinatorial property of secret sharing schemes, which is a connection between ideal multipartite secret sharing schemes and integer polymatroids. It provides new sufficient conditions and necessary conditions for an access structure to be ideal. Moreover, this connection is also used in the construction ideal linear multipartite secret sharing schemes. These results are useful for the study of multipartite access structures in which the number of parts is small in relation to the number of participants, and multipartite access structures in which the parts are related in a special way. This is the case of the family of hierarchical access structures, which are the ones in which the participants can be hierarchically ordered, and the family of tripartite access structures. Applying these results, the ideal access structures in these families are completely characterized. All the ideal multipartite secret sharing schemes presented in the literature are related to a particular family of integer polymatroids, the boolean ones. The analysis of these polymatroids leds to the find of new ideal multipartite secret sharing schemes. The optimization of the length of the shares is also studied for multipartite secret sharing schemes, in particular for the bipartite ones. The main results are a new method to find bound on the length of the shares that combines linear / El tema d'aquesta tesi són els esquemes de compartició de secrets, uns mètodes criptogràfics que permeten fragmentar missatges de manera segura. En particular s'aborden dos dels principals problemes oberts en aquest camp: la caracterització de les estructures d'accés que admeten esquemes de compartició de secrets ideals i l'optimització de la llargada dels fragments en construccions per estructures d'accés generals. Aquests problemes oberts s'estudien per estructures d'accés multipartides, que són estructures en què el conjunt de participants està dividit en diferents parts i a cada part tots els participants tenen el mateix rol. Aquest plantejament resulta útil per estudiar famílies d'estructures d'accés en què el nombre de parts és petit i estructures en què hi ha alguna relació especial entre les parts, com les jeràrquiques i les compartmentades. L'eina principal d'aquest estudi és una nova propietat de les estructures ideals que es presenta en aquesta tesi, una connexió entre les estructures ideals multipartides i els polimatroides enters. A partir d'aquesta connexió s'obté una condició suficient i una de necessària perquè una estructura d'accés multipartida sigui ideal. Així, aquesta connexió permet discutir la idealitat de les estructures d'accés i també, en el cas que el polimatoride sigui representable, construir esquemes ideals a partir de les representacions. Aplicant aquests resultats s'obté un nou marc per descriure i analitzar mètodes per construir esquemes multipartits ideals. Com a resultat d'aquest estudi s'obté una caracterització completa de les estructures d'accés tripartides ideals i de les jeràrquiques ideals. Una estructura és jeràrquica si el conjunt de participants es pot ordenar de tal manera que si en un conjunt autoritzat es canvia un participant per un de jeràrquicament superior, el nou conjunt també és autoritzat. A partir d'aquest resultat s'obté una nova caracterització de les estructures de llindar amb pesos ideals. Després d'analitzar tots els esquemes de compartició de secrets ideals multipartits presentats fins l'actualitat, es mostra que tots ells estan relacionats amb una família molt senzilla de polimatroides enters, els booleans. A partir d'aquests polimatroides s'obté una nova família d'estructures ideals, les compartmentades, que inclouen diverses famílies estudiades prèviament. L'altre problema obert considerat a la tesi, l'estudi de l'optimització de la llargada dels fragments, es centra en les estructures bipartides. Combinant tècniques de programació lineal i polimatroides, es presenta un mètode per calcular fites en la llargada dels fragments per estructures d'accés no ideals que és vàlid per qualsevol estructura multipartida. A partir de tècniques algebraiques es presenten noves fites i una família d'esquemes bipartits òptims.