Graduation date: 2004

Biologists need tools to see the structural relationships encoded in biological sequences (strings). The Walking Tree heuristics calculate some of these relationships. I have designed and implemented graphic presentations which allow the biologist (user) to see these relations. This thesis contains background information on the biological sequences and some background on the Walking Tree heuristics. I demonstrate my methods by showing a visual matching of mitochondrial genomes. I also show matchings based on amino acids and on hydrophobicity. I also show how the parameters of the visualization can be varied to produce more useful pictures. I implemented a parallel version of the Walking Tree heuristic and used it to produce a phylogenetic tree for picornaviruses. I also implemented several user interfaces. These programs are available on my WWW page which allows a user to produce a picture of a matching by giving the sequences in Gen Bank format and by making a few mouse clicks. / Graduation date: 1998

Cognitive radio technology is a promising technology to solve the wireless spectrum scarcity problem by intelligently allowing secondary, or unlicensed, users access to the primary, licensed, users' frequency bands. Cognitive technology involves two main tasks: 1) sensing the wireless medium to assess the presence of the primary users and 2) designing secondary spectrum access techniques that maximize the secondary users' benefits while maintaining the primary users' privileged status. On the spectrum sensing side, we make two contributions. First, we maximize a utility function representing the secondary throughput while constraining the collision probability with the primary below a certain value. We optimize therein the channel sensing time, the sensing decision threshold, the channel probing time, together with the channel sensing order for wideband primary channels. Second, we design a cooperative spectrum sensing technique termed sensing with equal gain combining whereby cognitive radios simultaneously transmit their sensing results to the fusion center over multipath fading reporting channels. The proposed scheme is shown to outperform orthogonal reporting systems in terms of achievable secondary throughput and to be robust against phase and synchronization errors. On the spectrum access side, we make four contributions. First, we design a secondary scheduling scheme with the goal of minimizing the secondary queueing delay under constraints on the average secondary transmit power and the maximum tolerable primary outage probability. Second, we design another secondary scheduling scheme based on the spectrum sensing results and the primary automatic repeat request feedback. The optimal medium access probabilities are obtained via maximizing the secondary throughput subject to constraints that guarantee quality of service parameters for the primary. Third, we propose a three-message superposition coding scheme to maximize the secondary throughput without degrading the primary rate. Cognitive relaying is employed as an incentive for the primary network. The scheme is shown to outperform a number of reference schemes such as best relay selection. Finally, we consider a network of multiple primary and secondary users. We propose a three-stage distributed matching algorithm to pair the network users. The algorithm is shown to perform close to an optimal central controller, albeit at a reduced computational complexity.

Thesis (Ph. D.)--University of Delaware, 2005. / Principal faculty advisor: Chandra Kambhamettu, Dept. of Computer & Information Sciences. Includes bibliographical references.

It is the aim of this paper to review some of the work done on stable matching, and on stable marriage problems in particular. Variants of the stable marriage problem will be considered, and the similarities and differences from a mathematical point of view will be highlighted. The correlation between preference and stability is a main theme, and the way in which diluted or incomplete preferences affect stability is explored. Since these problems have a wide range of practical applications, it is of interest to develop useful algorithms for the derivation of solutions. Time-complexity is a key factor in designing computable algorithms, making work load a strong consideration for practical purposes. Average and worst-case complexity are discussed. The number of different solutions that are possible for a given problem instance is surprising, and counter-intuitive. This leads naturally to a study of the solution sets and the lattice structure of solutions that emerges for any stable marriage problem. Many theorems derive from the lattice structure of stable solutions and it is shown that this can lead to the design of more efficient algorithms. The research on this topic is well established, and many theorems have been proved and published, although some published proofs have omitted the detail. In this paper, the author selects some key theorems, providing detailed proofs or alternate proofs, showing the mathematical richness of this field of study. Various applications are discussed, particularly with relevance to the social sciences, although mention is made of applications in computer science, game theory, and economics. The current research that is evident in this subject area, by reference to technical papers in periodicals and on the internet, suggests that it will remain a key topic for some time to come. / MATHEMATICAL SCIENCES / MSC (MATHEMATICS)

Orientador: Claudio Leonardo Lucchesi / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-07T04:48:23Z (GMT). No. of bitstreams: 1 Miranda_AlbertoAlexandreAssis_M.pdf: 924668 bytes, checksum: 5707312a9e0513f890e4affc3858fbb6 (MD5) Previous issue date: 2006 / Resumo: Um grafo G que tem emparelhamento perfeito é o Pfaffiano se existe uma orientação D das arestas de G, tal que todo circuito conforme de G tem orientação ímpar em D. Um subgrafo H de G é conforme se G- V (H) tem emparelhamento perfeito. Uma orientação de um circuito par é ímpar se numa dada direção de percurso do circuito o número de arestas que concorda com a direção é ímpar. Calcular o número de emparelhamentos perfeitos de um grafo, no caso geral, _e NP-difícil [11, pág. 307]. No entanto, para grafos Pfaffiano, seu cálculo torna-se polinomial [11, pág. 319]. A caracterização de grafos bipartidos Pfaffiano, feita por Little, tem quase trinta anos [9]. No entanto, somente nos últimos anos apareceram algoritmos polinomiais para reconhecimento de tais grafos, por McCuaig [13] e independentemente por Robertson, Seymour e Thomas [14]. A solução para este problema resolve também uma série de problemas, muitos deles clássicos, em teoria dos grafos, economia e química, como descrito no artigo de McCuaig [13, págs. 16 a 35]. Nesta dissertação, apresentamos uma prova de corretude do algoritmo distinta das duas provas anteriormente conhecidas / Abstract: A graph G that contains a perfect matching is Pfaffiano if there is an orientation D of the edges of G, such that every conformal circuit of G is oddly oriented in D. A subgraph H of G is conformal if G - V (H) has a perfect matching. A circuit with an even number of edges is oddly oriented if the number of edges whose orientation in D agrees with any sense of traversal of the circuit is odd. Counting the number of perfect matchings of a graph is known to be NP-hard [11, page 307]. However, when restricted to Pfaffiano graphs, this problem is solvable in polynomial time [11, page 319]. The characterisation of Pfaffiano bipartite graphs, achieved by Charles Little, is almost thirty years old [9]. However, only recently, polynomial time algorithms for determining whether a bipartite graph is Pfaffiano were discovered, by McCuaig [13] and independently by Robertson, Seymour and Thomas [14]. This problem's solution solves a lot of problems, some of them are quite famous, in graph theory, economy and chemistry, as described in McCuaig's article [13, pages 16 to 35]. On this dissertation, we present a new proof of the correctness of this algorithm distinct from the two previously known proofs / Mestrado / Mestre em Ciência da Computação

Orientador: Claudio Leonardo Lucchesi / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-15T06:54:51Z (GMT). No. of bitstreams: 1 Miranda_AlbertoAlexandreAssis_D.pdf: 571362 bytes, checksum: bd3600cbf8fe0c2875d8e5c60b6abfd3 (MD5) Previous issue date: 2009 / Resumo: A área de grafos Pfaffianos apresenta muitos problemas em aberto. Nesta tese resolvemos dois problemas sobre grafos Pfaffianos. O primeiro problema resolvido é a obtenção de um algoritmo polinomial para reconhecimento de grafos quase-bipartidos Pfaffianos. Além disso, estendemos tanto o algoritmo como a caracterização de grafos quase-bipartidos Pfaffianos para a classe dos grafos meio-bipartidos. O segundo resultado é a obtencão de vários resultados estruturais básicos sobre grafos k-Pfaffianos. Utilizando esses resultados, obtivemos um contra-exemplo para a conjectura de Norine, que afirma que o número Pfaffiano de todo grafo é uma potência de quatro: apresentamos um grafo cujo numero Pfaffiano é 6 / Abstract: The area of Pfaffian graphs contains many open problems. In this thesis, we solve two problems related to Pfaffian graphs. The first result is a polynomial time algorithm to recognize near-bipartite Pfaffian graphs. Moreover, we extend this algorithm and the characterization of near-bipartite Pfaffian graphs to the class of half-bipartite graphs. The second result is obtaining several basic structural results concerning k-Pfaffian graphs. Using these results, we obtained a counter-example to Norine's conjecture, which states that the Pfaffian number of a graph is always a power of four: we present a graph whose Pfaffian number is 6 / Doutorado / Matematica Discreta e Combinatoria / Doutor em Ciência da Computação

La découverte de la photoluminescence du silicium sous sa forme nanométrique a ouvert la voie de l’utilisation du silicium dans les composants optoélectroniques. Cependant cette photoluminescence reste trop peu efficace et de nombreuses recherches portent aujourd’hui sur l’amélioration des propriétés optiques du silicium. Ce travail de thèse s’intéresse particulièrement à l’utilisation de plasmons de surface localisés afin d’améliorer les propriétés optiques de nanocristaux de silicium. Grâce au contrôle de tous les paramètres géométriques des nanocristaux de silicium et des nanoparticules métalliques lors de la fabrication des échantillons, il a été possible d’étudier les phénomènes physiques du couplage entre ces deux objets. Une modification de l’émission des nanocristaux de silicium en fonction de la distance, de la taille et de la nature des nanoparticules métalliques a été étudiée. Grâce au développement de différentes techniques de caractérisation optique, il a été possible de montrer que la photoluminescence des nanocristaux de silicium était modifiée à la fois spectralement et spatialement par les plasmons de surface localisés. Ce travail montre que grâce aux plasmons de surface localisés il est possible de grandement améliorer la photoluminescence des nanocristaux de silicium et ainsi il est possible d’imaginer de nouveaux composants optoélectroniques à base de silicium et de plasmons / The discovery of photoluminescence of nanometric silicon paves the way to use silicon in optoelectronic devices. However this photoluminescence remains low and a lot of works aim at improving silicon optical properties. In this dissertation we study localized surface plasmons to improve optical properties of silicon nanocrystals. Thanks to the control of all geometrical parameters of silicon nanocrystals and metallic nanoparticles during the fabrication process, the coupling process between these two objects has been studied. The modification of silicon nanocrystals emission as a function of the distance, the size and the nature of metallic nanoparticles has been investigated. Thanks to the development of experimental optical characterization techniques we showed that silicon nanocrystals photoluminescence is modified both spectrally and spatially by localized surface plasmons. This work shows that it’s possible to enhance silicon’s optical properties and thus to devise optoelectronic devices with silicon and plasmons

Thesis advisor: Utku Unver / My doctoral research focuses on the matching theory and its market design application. Specifically, I work on matching with property rights, where property rights not only mean the ownership, but also refer to the ability to determine how the good is used. In the matching with property rights model, an agent who owns a resource can claim how her resource is offered, depending on what she gets from the system. For example, in a housing exchange for vacation, an agent who gets a house with a car will offer her house also with a car. However, if she is assigned only a house without a car, she might refuse to offer a car. This restriction can be thought as a matching with externality, as someone's consuming my resource in certain way affects my utility. With property rights present, it is not clear how we can achieve a desirable outcome while satisfying the rights. I am currently pursuing two main lines of research in this topic that constitute the two chapters dissertation. In Matching with Property Rights: an Application to a Parking Space Assignment Problem, I introduce parking in urban areas as a matching problem. First, I model the street-parking market as a strategic game and show that the set of Nash equilibrium outcomes is equivalent to the set of stable allocations. However, it is not reasonable to expect drivers to reach a Nash equilibrium in the decentralized system due to lack of information and coordination failure. Therefore, I suggest a centralized mechanism that would enable a parking authority to assign available spaces to drivers in a stable way. The model incorporates resident parking spaces, such that visitors could access vacant resident spaces. To use the resident parking spaces, the system needs to protect exclusive property rights over their parking spaces. I show that, however, there is no mechanism that is stable and protects residents' rights. To resolve this issue, I introduce a new concept, a claim contract, and suggest a mechanism that protects property rights, is strategy proof for the drivers, and approximates a stable matching. Besides its market-design focus, this paper handles both priority-based and property right-based assignment, which considered separately in the matching theory literature. In Housing Market with Contracts, I study matching with property rights problem in the housing market framework. To introduce property rights in housing market, I assume the house can be offered in two contractual terms. Property rights requires that when an agent gets a house in a certain term, her house should also be offered as the same term. Moreover, when every agent owns a house, property rights reduces to an equal-term matching. After defining efficiency and core in equal-term domain, I show that, in a housing market with contracts problem, core may be empty. However, there always exists an efficient, individually rational, and equal-term matching in every housing market with contracts problem. Then I present a mechanism that always produces an efficient, individually rational, and equal-term matching. This is the first attempt to model a matching with contract in a exchange economy. / Thesis (PhD) — Boston College, 2018. / Submitted to: Boston College. Graduate School of Arts and Sciences. / Discipline: Economics.

This thesis studies two discrete optimization problems: ordering problems in optimal stopping theory and popular matchings. The main goal of this thesis is to find the boundary between NP-hardness and tractability for these problems, and whenever possible, designs polynomial-time algorithms for the easy cases and approximation schemes or prophet inequalities for the hard cases. In the first part of the thesis, we study ordering problems in optimal stopping theory. In the optimal stopping problem, a player is presented with 𝓃 random variables 𝑋₁, . . . , 𝑋n, whose distributions are known to the player, but not their realizations. After observing the realization of 𝑋ᵢ, the player can choose to stop and earn reward 𝑋ᵢ, or reject 𝑋ᵢ and probe the next variable 𝑋ᵢ₊₁. If 𝑋ᵢ is rejected, it cannot be accepted in the future. The goal of the player is to maximize the expected reward at stopping time. If the order of observation is fixed, the player can find the optimal stopping criteria using a dynamic program. In this thesis, we investigate the variant in which the player is able to choose the order of observation. What is the best ordering and what benefits does ordering bring? Chapter 2 introduces the optimal ordering problem in optimal stopping theory. We prove that the problem of finding an optimal ordering is NP-hard even in very restricted cases where the support of each distribution has support on at most three points. Next, we prove an FPTAS for the hardness case and provide a tractable algorithm and a prophet inequality for two-point distributions. Chapter 3 studies the optimal ordering problem when the player can choose 𝑘 > 1 rewards before stopping. We show that finding an optimal static ordering is NP-hard even for very simple two-point distributions. Next, we prove an FPTAS for the hardness case and give prophet inequalities under static and dynamic policies for two-point distributions. In the second part of the thesis, we study popular matchings. Suppose we are given a bipartite graph with independent sets 𝑨 and 𝐵. Each vertex in 𝑨 has a ranked order of preferences on the vertices in 𝐵, and vice versa. A matching 𝑴 is popular if for any other matching 𝑴′, the number of vertices that prefer 𝑴 is at least as much as the number of vertices that prefer 𝑴′. Chapter 4 studies popular matchings. In the first part, we provide a general reduction which, through minor adjustments, proves NP-Hardness for a variety of different questions, including that of finding a max-weight popular matching. In the second part, we restrict our attention to graphs of bounded treewidth and provide a tractable algorithm for finding a max-weight popular matching.