To see the other types of publications on this topic, follow the link: Combinatorial algorithms on string.
Dissertations / Theses on the topic 'Combinatorial algorithms on string'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Combinatorial algorithms on string.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
BERNARDINI, GIULIA. "COMBINATORIAL METHODS FOR BIOLOGICAL DATA." Doctoral thesis, Università degli Studi di Milano-Bicocca, 2021. http://hdl.handle.net/10281/305220.
Full textAbstract:
Lo scopo di questa tesi è di elaborare e analizzare metodi rigorosi dal punto di vista matematico per l’analisi di due tipi di dati biologici: dati relativi a pan-genomi e filogenesi.
Con il termine “pan-genoma” si indica, in generale, un insieme di sequenze genomiche strettamente correlate (tipicamente appartenenti a individui della stessa specie) che si vogliano utilizzare congiuntamente come sequenze di riferimento per un’intera popolazione. Una filogenesi, invece, rappresenta le relazioni evolutive in un gruppo di entità, che siano esseri viventi, geni, lingue naturali, manoscritti antichi o cellule tumorali.
Con l’eccezione di uno dei risultati presentati in questa tesi, relativo all’analisi di filogenesi tumorali, il taglio della dissertazione è prevalentemente teorico: lo scopo è studiare gli aspetti combinatori dei problemi affrontati, più che fornire soluzioni efficaci in pratica.
Una conoscenza approfondita degli aspetti teorici di un problema, del resto, permette un'analisi matematicamente rigorosa delle soluzioni già esistenti, individuandone i punti deboli e quelli di forza, fornendo preziosi dettagli sul loro funzionamento e aiutando a decidere quali problemi vadano ulteriormente investigati. Oltretutto, è spesso il caso che nuovi risultati teorici (algoritmi, strutture dati o riduzioni ad altri problemi più noti) si possano direttamente applicare o adattare come soluzione ad un problema pratico, o come minimo servano ad ispirare lo sviluppo di nuovi metodi efficaci in pratica.
La prima parte della tesi è dedicata a nuovi metodi per eseguire delle operazioni fondamentali su un testo elastico-degenerato, un oggetto computazionale che codifica in maniera compatta un insieme di testi simili tra loro, come, ad esempio, un pan-genoma. Nello specifico, si affrontano il problema di cercare una sequenza di lettere in un testo elastico-degenerato, sia in maniera esatta che tollerando un numero prefissato di errori, e quello di confrontare due testi degenerati.
Nella seconda parte si considerano sia filogenesi tumorali, che ricostruiscono per l'appunto l'evoluzione di un tumore, sia filogenesi "classiche", che rappresentano, ad esempio, la storia evolutiva delle specie viventi.
In particolare, si presentano nuove tecniche per confrontare due o più filogenesi tumorali, necessarie per valutare i risultati di diversi metodi che ricostruiscono le filogenesi stesse, e una nuova e più efficiente soluzione a un problema di lunga data relativo a filogenesi "classiche", consistente nel determinare se sia possibile sistemare, in presenza di dati mancanti, un insieme di specie in un albero filogenetico che abbia determinate proprietà.The main goal of this thesis is to develop new algorithmic frameworks to deal with (i) a convenient representation of a set of similar genomes and (ii) phylogenetic data, with particular attention to the increasingly accurate tumor phylogenies. A “pan-genome” is, in general, any collection of genomic sequences to be analyzed jointly or to be used as a reference for a population. A phylogeny, in turn, is meant to describe the evolutionary relationships among a group of items, be they species of living beings, genes, natural languages, ancient manuscripts or cancer cells. With the exception of one of the results included in this thesis, related to the analysis of tumor phylogenies, the focus of the whole work is mainly theoretical, the intent being to lay firm algorithmic foundations for the problems by investigating their combinatorial aspects, rather than to provide practical tools for attacking them. Deep theoretical insights on the problems allow a rigorous analysis of existing methods, identifying their strong and weak points, providing details on how they perform and helping to decide which problems need to be further addressed. In addition, it is often the case where new theoretical results (algorithms, data structures and reductions to other well-studied problems) can either be directly applied or adapted to fit the model of a practical problem, or at least they serve as inspiration for developing new practical tools. The first part of this thesis is devoted to methods for handling an elastic-degenerate text, a computational object that compactly encodes a collection of similar texts, like a pan-genome. Specifically, we attack the problem of matching a sequence in an elastic-degenerate text, both exactly and allowing a certain amount of errors, and the problem of comparing two degenerate texts. In the second part we consider both tumor phylogenies, describing the evolution of a tumor, and “classical” phylogenies, representing, for instance, the evolutionary history of the living beings. In particular, we present new techniques to compare two or more tumor phylogenies, needed to evaluate the results of different inference methods, and we give a new, efficient solution to a longstanding problem on “classical” phylogenies: to decide whether, in the presence of missing data, it is possible to arrange a set of species in a phylogenetic tree that enjoys specific properties.
2
Toopsuwan, Chalita. "Algorithms and combinatorics of repetitions in strings." Thesis, King's College London (University of London), 2017. https://kclpure.kcl.ac.uk/portal/en/theses/algorithms-and-combinatorics-of-repetitions-in-strings(a20776fa-6a15-4c37-bf87-505211309fd7).html.
Full textAbstract:
Repetitions in strings constitute one of the most fundamental areas of string combinatorics with exactly essential applications to text algorithms, data compression, and also analysis of biological sequences. It is relevant to periodicities, regularities, and compression. The higher compression rate can be obtained from the repetitive behavior of strings, and reversely some compression techniques are at the core of fast algorithms for detecting repetitions. Repetitions are highly periodic factors (or substrings) in strings, there are various type of repetitions such as repeat, repetition, squares, cubes, palindrome, maximal periodicitiie which is also called runs. The aim of this thesis is concentrated on the repetitions in strings in algorithmic and combinatorics approaches as they are very intricate and plenty of interesting works remain as open problems. The critical study of this thesis firstly approach to the maximal periodicities or runs. It presents in Algorithmics of repetitions, local periods and critical factorization. An algorithm is designed in order to compute all runs for a string drawn from an infinite alphabet. On a string of length n, the algorithm runs optimally in time O(n log n) while there is a linear number of runs. The key model of computation is the comparison of letters which is done with the equality operator only. Under the same proposition, another time-optimal algorithm is created. This gives the same running time to compute local periods and all critical factorisations. The prefix table of input strings is applied as the main tool of those algorithms. In this study, we also design a simple algorithm based on the Dictionary of Basic Factors of the input string. The notion of Gapped Palindrome and its Anti-exponent goes toward this research. A palindrome is a string x = a1 · · · an which is equal to its reversal ex = an · · · a1. The definition of a gapped palindromes is given by a string of the form uveu, where u, v are strings, |v| 2, and eu is the reversal of u. Replicating the standard notion of string exponent, we together define the anti-exponent of a gapped palindrome uveu as the quotient of |uveu| by |uv|. In this work, an algorithm is described to compute the maximal anti-exponent of gapped palindromes occurring in an ordinary palindrome-free string. To get an efficient computation of maximal anti-exponent of factors in a palindrome-free string, we apply techniques based on the suffix automaton and the reversed Lempel-Ziv factorisation. The complexity analyse shows that algorithm runs in linear-time on a fixed-size alphabet. Repeats are also of main concern in the domains of text compression and of pattern matching so lastly the study of repeat and its exponents are discussed in this thesis. Here we create linear-time algorithm to compute maximal exponent of repeats occurring in an overlapping-free string. Two main tools for the algorithm are a factorisation of the string and the Suffix Automaton of some factors. Eventually, we obtain the graceful result as the direct consequence from this research. There is the linearity of the number of occurrences of repeats whose exponent is maximal in an overlap-free string. Among all of the previous researches and our further viewpoints in this thesis, acquiring knowledge on repetitions in string remains interesting open questions to continue.
3
Wright, Colin Douglas. "Combinatorial algorithms." Thesis, University of Cambridge, 1990. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.357944.
Full text
4
Pinzon, Yoan Jose. "String algorithms on sequence comparison." Thesis, King's College London (University of London), 2001. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.395648.
Full text
5
Aslidis, Anastasios Haralampos. "Combinatorial algorithms for stacking problems." Thesis, Massachusetts Institute of Technology, 1989. http://hdl.handle.net/1721.1/33478.
Full text
6
Naji, Azimi Zahra <1982>. "Algorithms for Combinatorial Optimization Problems." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2010. http://amsdottorato.unibo.it/2695/1/Naji_Azimi_Zahra_Tesi.pdf.
Full text
7
Naji, Azimi Zahra <1982>. "Algorithms for Combinatorial Optimization Problems." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2010. http://amsdottorato.unibo.it/2695/.
Full text
8
Fischer, Johannes. "Data Structures for Efficient String Algorithms." Diss., lmu, 2007. http://nbn-resolving.de/urn:nbn:de:bvb:19-75053.
Full text
9
Newman, Alantha. "Algorithms for string and graph layout." Thesis, Massachusetts Institute of Technology, 2004. http://hdl.handle.net/1721.1/28745.
Full textAbstract:
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2004.Includes bibliographical references (p. 121-125).
Many graph optimization problems can be viewed as graph layout problems. A layout of a graph is a geometric arrangement of the vertices subject to given constraints. For example, the vertices of a graph can be arranged on a line or a circle, on a two- or three-dimensional lattice, etc. The goal is usually to place all the vertices so as to optimize some specified objective function. We develop combinatorial methods as well as models based on linear and semidefinite programming for graph layout problems. We apply these techniques to some well-known optimization problems. In particular, we give improved approximation algorithms for the string folding problem on the two- and three-dimensional square lattices. This combinatorial graph problem is motivated by the protein folding problem, which is central in computational biology. We then present a new semidefinite programming formulation for the linear ordering problem (also known as the maximum acyclic subgraph problem) and show that it provides an improved bound on the value of an optimal solution for random graphs. This is the first relaxation that improves on the trivial "all edges" bound for random graphs.
by Alantha Newman.
Ph.D.
10
Cruz, Mencía Francisco. "Enhancing performance on combinatorial optimization algorithms." Doctoral thesis, Universitat Autònoma de Barcelona, 2018. http://hdl.handle.net/10803/665199.
Full textAbstract:
L’optimització combinatòria és un tipus específic d’optimització matemàtica on el domini de les variables és discret. Aquest tipus de problemes d’optimització tenen una gran aplicabilitat degut a la seva capacitat d’optimització sobre objectes unitaris i no divisibles. Més enllà dels algoritmes genèrics, la comunitat investigadora és molt activa proposant algorismes capaços d’abordar problemes d’optimització combinatòria per a problemes específics. L’objectiu d’aquesta tesi és investigar com ampliar l’aplicabilitat d’algorismes d’optimització combinatoria que exploten l’estructura dels problemes a resoldre. Ho fem des de la perspectiva del maquinari d’una computadora, perseguint l’explotació total dels recursos computacionals que ofereix el maquinari actual. Per assolir generalitat treballem amb tres problemes diferents. Primer abordem el problema de generació d’estructures de la coalició (CSGP). Trobem que l’algorisme d’última generació és IDP. Proposem un algoritme optimitzat i paral·lel capaç de resoldre el CSGP. Aconseguim això definint un nou mètode per dur a terme l’operació més crítica -Splitting-, així com definint un nou mètode per dividir l’operació de l’algoritme en els diferent subprocessos. A continuació, estudiem el problema de determinació del guanyador (WDP) per a les subhastes combinades (CA). Trobem que l’escalabilitat dels solucionadors d’avantguarda és limitada. Més concretament, mostrem com millorar la resolució de resultats de relaxació LP per al WDP en subhastes combinables de gran escala mitjançant l’aplicació de l’algoritme AD³. A continuació, contribuïm amb una versió optimitzada d’AD³ que també es pot executar en un escenari paral·lel de memòria compartida. Finalment, estudiem l’aplicació de AD³ per resoldre les relaxacions LP d’un problema més exigent de la computacionalment: El problema de la predició de cadenes laterals (SCP). Presentem una manera optimitzada de resoldre l’operació més crítica, la resol·lució d’un problema quadràtic per a un factor arbitrari. En tots els casos proposem algoritmes optimitzats que es poden escalar de forma paral·lela i que milloren notablement l’estat de la tècnica. Tres ordres de magnitud a IDP, i un ordre de magnitud a AD³. L’objectiu final d’aquest treball és demostrar com un disseny algorisme conscient de maquinari pot conduir a millores de rendiment significatives. Mostrem estratègies exportables a algorismes d’optimització combinatòria similars. Aquestes estratègies ajudaran al dissenyador d’algorismes a assolir més eficiència en les CPU modernes.La optimización combinatoria es un tipo específico de optimización donde el dominio de las variables es discreto. Este tipo de problemas de optimización tienen una gran aplicabilidad debido a su capacidad de optimización sobre objetos unitarios y no divisibles. Más allá de los algoritmos genéricos, la comunidad investigadora es muy activa proponiendo algoritmos capaces de abordar problemas de optimización combinatoria para problemas específicos. El objetivo de esta tesis es investigar cómo ampliar la aplicabilidad de algoritmos de optimización combinatoria que explotan la estructura de los problemas a resolver. Lo hacemos desde la perspectiva del hardware de una computadora, persiguiendo la explotación total de los recursos computacionales que ofrece el hardware actual. Para alcanzar generalidad trabajamos con tres problemas diferentes. Primero abordamos el problema de generación de estructuras de la coalición (CSGP). Encontramos que el algoritmo de última generación es IDP. Proponemos un algoritmo optimizado y paralelo capaz de resolver el CSGP. Conseguimos esto deniendo un nuevo metodo para llevar a cabo la operacion mas crtica -Splitting-, así como deniendo un nuevo método para dividir la operación del algoritmo en los diferente subprocesos. A continuación, estudiamos el problema de determinación del ganador (WDP) para las subastas combinatorias (CA). Encontramos que la escalabilidad de los solucionadores de vanguardia es limitada. Más concretamente, mostramos cómo mejorar la resolución de resultados de relajación LP para el WDP en subastas combinatorias de gran escala mediante la aplicación del algoritmo AD³. A continuación, contribuimos con una versión optimizada de AD³ que también se puede ejecutar en un escenario paralelo de memoria compartida. Finalmente, estudiamos la aplicación de AD³ para resolver las relajaciones LP de un problema más exigente de la computacionalmente: El problema de la predición de cadenas laterales (SCP). Presentamos una manera optimizada de resolver la operación más crítica, la resolución de un problema cuadrático para un factor arbitrario. En todos los casos proponemos algoritmos optimizados que se pueden escalar de forma paralela y que mejoran notablemente el estado de la técnica. Tres órdenes de magnitud en IDP, y un orden de magnitud en AD³. El objetivo nal de este trabajo es demostrar como un diseño algoritmo consciente de hardware puede conducir a mejoras de rendimiento signicativas. Mostramos estrategias exportables a algoritmos de optimización combinatoria similares. Estas estrategias ayudarán al diseñador de algoritmos lograr más eficiencia en las CPU modernas.
Combinatorial Optimization is a specific type of mathematical optimization where variables' domain is discrete. This kind of optimization problems have an enormous applicability due to its ability to optimize over unitary and non-divisible objects. Beyond generic algorithms, the research community is very active proposing algorithms able to tackle specific combinatorial optimization problems. The goal of this thesis is to investigate how to widen the applicability of Combinatorial Optimization algorithms that exploit the structure of the problems to solve. We do so from a computer's hardware perspective, pursuing the full exploitation of computational resources offered by today's hardware. For the sake of generality we work on three different problems. First we tackle the Coalition Structure Generation Problem (CSGP). We find that the state-of-the-art algorithm is IDP. We propose an optimized and parallel algorithm able to solve the CSGP. We reach this by defining a novel method to perform the most critical operation --Splitting-- as well as by defining a novel method to divide the the algorithm's operation in threads. Then, we study the Winner Determination Problem (WDP) for Combinatorial Auctions (CA), which is very related to the CSGP. We find that state-of-the-art solvers' scalability is limited. More specifically we show how to improve results solving LP relaxations for the WDP in Large Scale Combinatorial Auctions by applying the AD³ algorithm. Then we contribute with an optimized version of AD³ which is also able to run in a shared-memory parallel scenario. Finally we study the application of AD³ to solve the LP relaxations of a more CPU demanding problem: The Side-Chain Prediction (SCP). We present an optimized way to solve the most critical operation which is solving a Quadratic Problem for an Arbitrary Factor. In all the cases we propose optimized algorithms that are scalable in parallel and that improve significantly the state-of-the-art. Three orders of magnitude speedup on IDP, one order of magnitude speedup in AD³. The ultimate purpose of this work is to demonstrate how a hardware-aware algorithmic design can lead to significant speedups. We show strategies that are exportable to similar Combinatorial Optimization algorithms. Such strategies will help the algorithm designer to achieve more efficiency in modern CPUs.
11
Violich, Stephen Scott. "Fusing Loopless Algorithms for Combinatorial Generation." Thesis, University of Canterbury. Computer Science and Software Engineering, 2006. http://hdl.handle.net/10092/1075.
Full textAbstract:
Loopless algorithms are an interesting challenge in the field of combinatorial generation. These algorithms must generate each combinatorial object from its predecessor in no more than a constant number of instructions, thus achieving theoretically minimal time complexity. This constraint rules out powerful programming techniques such as iteration and recursion, which makes loopless algorithms harder to develop and less intuitive than other algorithms. This thesis discusses a divide-and-conquer approach by which loopless algorithms can be developed more easily and intuitively: fusing loopless algorithms. If a combinatorial generation problem can be divided into subproblems, it may be possible to conquer it looplessly by fusing loopless algorithms for its subproblems. A key advantage of this approach is that is allows existing loopless algorithms to be reused. This approach is not novel, but it has not been generalised before. This thesis presents a general framework for fusing loopless algorithms, and discusses its implications. It then applies this approach to two combinatorial generation problems and presents two new loopless algorithms. The first new algorithm, MIXPAR, looplessly generates well-formed parenthesis strings comprising two types of parentheses. It is the first loopless algorithm for generating these objects. The second new algorithm, MULTPERM, generates multiset permutations in linear space using only arrays, a benchmark recently set by Korsh and LaFollette (2004). Algorithm MULTPERM is evaluated against Korsh and LaFollette's algorithm, and shown to be simpler and more efficient in both space and time.
12
Chen, Qin, and 陈琴. "Algorithms for some combinatorial optimization problems." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2011. http://hub.hku.hk/bib/B46589302.
Full text
13
Jartoux, Bruno. "On combinatorial approximation algorithms in geometry." Thesis, Paris Est, 2018. http://www.theses.fr/2018PESC1078/document.
Full textAbstract:
L'analyse des techniques d'approximation est centrale en géométrie algorithmique, pour des raisons pratiques comme théoriques. Dans cette thèse nous traitons de l'échantillonnage des structures géométriques et des algorithmes d'approximation géométriques en optimisation combinatoire. La première partie est consacrée à la combinatoire des hypergraphes. Nous débutons par les problèmes de packing, dont des extensions d'un lemme de Haussler, particulièrement le lemme dit de Shallow packing, pour lequel nous donnons aussi un minorant optimal, conjecturé mais pas établi dans les travaux antérieurs. Puis nous appliquons ledit lemme, avec la méthode de partition polynomiale récemment introduite, à l'étude d'un analogue combinatoire des régions de Macbeath de la géométrie convexe : les M-réseaux, pour lesquels nous unifions les résultats d'existence et majorations existants, et donnons aussi quelques minorants. Nous illustrons leur relation aux epsilon-réseaux, structures incontournables en géométrie combinatoire et algorithmique, notamment en observant que les majorants de Chan et al. (SODA 2012) ou Varadarajan (STOC 2010) pour les epsilon-réseaux (uniformes) découlent directement de nos résultats sur les M-réseaux. La deuxième partie traite des techniques de recherche locale appliquées aux restrictions géométriques de problèmes classiques d'optimisation combinatoire. En dix ans, ces techniques ont produit les premiers schémas d'approximation en temps polynomial pour divers problèmes tels que celui de calculer un plus petit ensemble intersectant pour un ensemble de disques donnés en entrée parmi un ensemble de points donnés en entrée. En fait, il a été montré que pour de nombreux tels problèmes, la recherche locale de rayon Θ (1/epsilon²) donne une (1 + epsilon)-approximation en temps n^{O(1/epsilon²)}. Savoir si l'exposant de n pouvait être ramené à o (1/epsilon²) demeurait une question ouverte. Nous répondons par la négative : la garantie d'approximation de la recherche locale n'est améliorable pour aucun desdits problèmesThe analysis of approximation techniques is a key topic in computational geometry, both for practical and theoretical reasons. In this thesis we discuss sampling tools for geometric structures and geometric approximation algorithms in combinatorial optimization. Part I focuses on the combinatorics of geometric set systems. We start by discussing packing problems in set systems, including extensions of a lemma of Haussler, mainly the so-called shallow packing lemma. For said lemma we also give an optimal lower bound that had been conjectured but not established in previous work on the topic. Then we use this lemma, together with the recently introduced polynomial partitioning technique, to study a combinatorial analogue of the Macbeath regions from convex geometry: Mnets, for which we unify previous existence results and upper bounds, and also give some lower bounds. We highlight their connection with epsilon-nets, staples of computational and combinatorial geometry, for example by observing that the unweighted epsilon-net bound of Chan et al. (SODA 2012) or Varadarajan (STOC 2010) follows directly from our results on Mnets. Part II deals with local-search techniques applied to geometric restrictions of classical combinatorial optimization problems. Over the last ten years such techniques have produced the first polynomial-time approximation schemes for various problems, such as that of computing a minimum-sized hitting set for a collection of input disks from a set of input points. In fact, it was shown that for many of these problems, local search with radius Θ(1/epsilon²) gives a (1 + epsilon)-approximation with running time n^{O(1/epsilon²)}. However the question of whether the exponent of n could be decreased to o(1/epsilon²) was left open. We answer it in the negative: the approximation guarantee of local search cannot be improved for any of these problems. The key ingredient is a new lower bound on locally expanding planar graphs, which is then used to show the impossibility results
14
Goldberg, Leslie Ann. "Efficient algorithms for listing combinatorial structures." Thesis, University of Edinburgh, 1991. http://hdl.handle.net/1842/10917.
Full textAbstract:
This thesis studies the problem of designing efficient algorithms for listing combinatorial structures. The main notion of efficiency that we use is due to Johnson, Yannakakis, and Papadimitriou. It is called polynomial delay. A listing algorithm is said to have delay d if and only if it satisfies the following conditions whenever it is run with any input p: 1. It executes at most d(p) machine instructions before either producing the first output or halting. 2. After any output it executes at most d(p) machine instructions before either producing the next output or halting. An algorithm is said to have polynomial delay if its delay is bounded from above by a polynomial in the length of the input. In the thesis we also define a weaker notion of efficiency which we call cumulative polynomial delay. There are some families of combinatorial structures for which it is easy to design a polynomial delay listing algorithm. For example, it is easy to design a polynomial delay algorithm that takes as input a unary integer n and lists all n-vertex graphs. In this thesis we focus on more difficult problems such as the following. Problem 1 - Listing unlabeled graphs - Design a polynomial delay algorithm that takes as input a unary integer n and lists exactly one representative from each isomorphism class in the set of n-vertex graphs. Problem 2 - Listing Hamiltonian graphs - Design a polynomial delay algorithm that takes as input a unary integer n and lists all Hamiltonian n-vertex graphs. We start the thesis by developing general methods for solving listing problems such as 1 and 2. Then we apply the methods to specific combinatorial families obtaining various listing algorithms including the following. 1. A polynomial space polynomial delay listing algorithm for unlabeled graphs 2. A polynomial space polynomial delay listing algorithm for any first order one property* 3. A polynomial delay listing algorithm for Hamiltonian graphs 4. A polynomial space polynomial delay listing algorithm for graphs with cliques of specified sizes 5. A polynomial space cumulative polynomial delay listing algorithm for k-colorable graphs. * A first order graph property is called a one property if and only if it is the case that almost every graph has the property.
15
Strappaveccia, Francesco <1982>. "Many-core Algorithms for Combinatorial Optimization." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2015. http://amsdottorato.unibo.it/6949/1/Strappaveccia_Francesco_tesi.pdf.
Full textAbstract:
Combinatorial Optimization is becoming ever more crucial, in these days. From natural sciences to economics, passing through urban centers administration and personnel management, methodologies and algorithms with a strong theoretical background and a consolidated real-word effectiveness is more and more requested, in order to find, quickly, good solutions to complex strategical problems. Resource optimization is, nowadays, a fundamental ground for building the basements of successful projects. From the theoretical point of view, Combinatorial Optimization rests on stable and strong foundations, that allow researchers to face ever more challenging problems.
However, from the application point of view, it seems that the rate of theoretical developments cannot cope with that enjoyed by modern hardware technologies,
especially with reference to the one of processors industry. In this work we propose new parallel algorithms, designed for exploiting the new parallel architectures available on the market. We found that, exposing the inherent parallelism of some resolution techniques (like Dynamic Programming), the computational benefits are remarkable, lowering the execution times by more than an order of magnitude, and allowing to address instances with dimensions not possible before. We approached four Combinatorial Optimization’s notable problems: Packing Problem, Vehicle Routing Problem, Single Source Shortest Path Problem and a Network Design problem. For each of these problems we propose a collection of effective parallel solution algorithms, either for solving the full problem (Guillotine Cuts and SSSPP) or for enhancing a fundamental part of the solution method (VRP and ND).
We endorse our claim by presenting computational results for all problems, either on standard benchmarks from the literature or, when possible, on data from real-world applications, where speed-ups of one order of magnitude are usually attained, not uncommonly scaling up to 40 X factors.
16
Strappaveccia, Francesco <1982>. "Many-core Algorithms for Combinatorial Optimization." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2015. http://amsdottorato.unibo.it/6949/.
Full textAbstract:
Combinatorial Optimization is becoming ever more crucial, in these days. From natural sciences to economics, passing through urban centers administration and personnel management, methodologies and algorithms with a strong theoretical background and a consolidated real-word effectiveness is more and more requested, in order to find, quickly, good solutions to complex strategical problems. Resource optimization is, nowadays, a fundamental ground for building the basements of successful projects. From the theoretical point of view, Combinatorial Optimization rests on stable and strong foundations, that allow researchers to face ever more challenging problems.
However, from the application point of view, it seems that the rate of theoretical developments cannot cope with that enjoyed by modern hardware technologies,
especially with reference to the one of processors industry. In this work we propose new parallel algorithms, designed for exploiting the new parallel architectures available on the market. We found that, exposing the inherent parallelism of some resolution techniques (like Dynamic Programming), the computational benefits are remarkable, lowering the execution times by more than an order of magnitude, and allowing to address instances with dimensions not possible before. We approached four Combinatorial Optimization’s notable problems: Packing Problem, Vehicle Routing Problem, Single Source Shortest Path Problem and a Network Design problem. For each of these problems we propose a collection of effective parallel solution algorithms, either for solving the full problem (Guillotine Cuts and SSSPP) or for enhancing a fundamental part of the solution method (VRP and ND).
We endorse our claim by presenting computational results for all problems, either on standard benchmarks from the literature or, when possible, on data from real-world applications, where speed-ups of one order of magnitude are usually attained, not uncommonly scaling up to 40 X factors.
17
Lipták, Zsuzsanna. "Strings in proteomics and transcriptomics algorithmic and combinatorial questions in mass spectrometry and EST clustering /." [S.l.] : [s.n.], 2005. http://deposit.ddb.de/cgi-bin/dokserv?idn=979746566.
Full text
18
Luccio, Flaminia L. Carleton University Dissertation Computer Science. "Distributed algorithms for routing and string recognition." Ottawa, 1995.
Find full text
19
Ozsayin, Burcu. "Multi-objective Combinatorial Optimization Using Evolutionary Algorithms." Master's thesis, METU, 2009. http://etd.lib.metu.edu.tr/upload/2/12610866/index.pdf.
Full textAbstract:
Due to the complexity of multi-objective combinatorial optimization problems (MOCO), metaheuristics like multi-objective evolutionary algorithms (MOEA) are gaining importance to obtain a well-converged and well-dispersed Pareto-optimal frontier approximation. In this study, of the well-known MOCO problems, single-dimensional multi-objective knapsack problem and multi-objective assignment problem are taken into consideration. We develop a steady-state and elitist MOEA in order to approximate the Pareto-optimal frontiers. We utilize a territory concept in order to provide diversity over the Pareto-optimal frontiers of various problem instances. The motivation behind the territory definition is to attach the algorithm the advantage of fast execution by eliminating the need for an explicit diversity preserving operator. We also develop an interactive preference incorporation mechanism to converge to the regions that are of special interest for the decision maker by interacting with him/her during the optimization process.
20
Paulden, Timothy John. "Combinatorial spanning tree representations for evolutionary algorithms." Thesis, University of Exeter, 2007. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.486767.
Full textAbstract:
The research presented in this thesis lies at the interface between two distinct' fields: combinatorial mathematics and evolutionary algorithm design. We examine a number of combinatorial spanning tree representations, and develop theoretical and empirical results to quantify the intrinsic properties of each representation, focusing on properties that encapsulate the representation's suitability for evolutionary search. In Part I of the thesis, we focus on a selectIon of Cayley codes - namely, the Priifer Code, the Blob Code, and the family of Dandelion-like codes (which includes the Dandelion Code, Happy Code, MHappy Code, and Theta Code). Each of these representations is bijective, and so the efficacy of evolutionary search primarily depends on the representation's locality. We develop a number of results which demonstrate that Dandelion-like codes possess highly desirable locality properties (including bounded locality), while those of the Blob Code and Priifer. Code are inferior. We also present linear-time decoding and'encoding algorithms for the various codes, many of which have not previously appeared in the evolutionary algorithms literature. In Part II, the Theta Code is adapted to give bijective spanning tree representations on graph topologies other than the complete graph. These extended representations retain the desirable properties of the Thet'a Code, including its high locality. We then formulate general principles for developing extended representations of this kind. Finally, in Part III, we study the Edge-Window-Decoder (EWD) representation. We find that the EWD representation has several desirable properties for evolutionary search (includi.ng bounded locality), but possesses an intrinsic bi~ towards path-like trees. We also present a number of theoretical advances, including the first method for generating EWD strings uniformly at random, and a new technique for characterising representational bias using the Wiener index.
21
Li, Ying. "Efficient Combinatorial Algorithms for DNA Microarray Design." Thesis, University of Liverpool, 2008. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.490907.
Full textAbstract:
The advent of efficient genome sequencing tools and high-throughput experimental biotechnology has led to enonnous progress in the life science. DNA microarray is among the most important innovations. It allows to measure the expression for thousands of genes simultaneously by analysing the hybridisation data. Such measurements have been proved to be invaluable in understanding the development of diseases such as cancer. However, the analysis of data is non-trivial since the hybridisation data relies on the quality of DNA microarray. High quality DNA microarray will lead to more efficient hybridisation and stronger signal.and reliability. The reliability of data is essential. Thus, the development of novel algorithms and techniques for DNA microarray design is crucial. This thesis considers a number of combinatorial issues in selecting, placing, and synthesising probes during the DNA microarray design process. A probe is a specific sequence of single-stranded DNA or RNA, typically labelled with a radioactive or fluorescent tag, which is designed to bind to, and thereby identify, a particular segment of DNA (or RNA). The probe selection problem we studied is to find for each gene sequence a unique probe such that every gene in the given dataset can be identified. However, due to homology, sometimes a gene does not have a unique probe, then we use a small number of non-unique probes to identify a gene. The challenge of the problem is that there are many candidate probes in a gene sequence and we have to find the right one (or a small subset) efficiently. A randomised probe selection algorithm for DNA microarray design is proposed. The algorithm overcomes some existing algorithms demanding optimal probes by exhaustive search. \Ve implement the randomised probe selection algorithm and develop a probe selection software RANDPS. Investigations using several real-life microarray datasets show that algorithm is able to find high quality probes. Nevertheless, the number of the probes selected might be too large for placing in a single microarray, thus minimising the number of probes is an important objective, since it is proportional to the cost of the microarray experiment. Therefore, we investigate the string barcoding problem in which a set of non-unique probes is given and the probes have to be chosen from the given set of probes. The objective is to use an appropriate combination of probes with minimum cardinality such that all genes in the dataset can be distinguished. An almost optimal O(nlSllog3 n)-time approximation algorithm for the considered problem is presented. The approximation procedure is a modification of the algorithm due to Berman et a1. [l0] which obtains the best possible approximation ratio (1 + In n). The improved time complexity is a direct consequence of more careful management of processed sets, use of several specialised graph and string data structures, as well as tighter time complexity analysis based on an amortised argument. After probes are selected, they are then synthesised on the microarrays by using a light-directed chemical process in which unintended illumination may contaminate the quality of the microarray experiments. Border length is a measure of the amount of unwanted illumination and the objective of this problem is to minimise the total border length during probe synthesis process. This problem is believed to be NP-hard and approximation of the BMP problem in asynchronous synthesis is studied. As far as we know, this is the first result with proved performance guarantee. The main result is an O(vnlog2 n)-approximation, where n is the number of probes to be synthesised. In the case where the placement is given in advance, we show that the problem is O(10g2 n)-approximable. A related problem called agreement maximisation problem (MAP) is also considered in this chapter. In contrast to BMp, we show that MAP admits a constant approximation even when placement is not given in advance. Supplied by The British Library - 'The world's knowledge'
22
Mestre, Julián Diego. "Primal-Dual algorithms for combinatorial optimization problems." College Park, Md. : University of Maryland, 2007. http://hdl.handle.net/1903/7387.
Full textAbstract:
Thesis (Ph. D.) -- University of Maryland, College Park, 2007.Thesis research directed by: Computer Science. Title from t.p. of PDF. Includes bibliographical references. Published by UMI Dissertation Services, Ann Arbor, Mich. Also available in paper.
23
Ortmann, Mark [Verfasser]. "Combinatorial Algorithms for Graph Sparsification / Mark Ortmann." Konstanz : Bibliothek der Universität Konstanz, 2017. http://d-nb.info/1173616438/34.
Full text
24
Lee, Lai Soon. "Multicrossover genetic algorithms for combinatorial optimisation problems." Thesis, University of Southampton, 2006. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.431202.
Full text
25
Lee, Yin Tat. "Faster algorithms for convex and combinatorial optimization." Thesis, Massachusetts Institute of Technology, 2016. http://hdl.handle.net/1721.1/104467.
Full textAbstract:
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Mathematics, 2016.This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.
Cataloged from student-submitted PDF version of thesis.
Includes bibliographical references (pages 443-458).
In this thesis, we revisit three algorithmic techniques: sparsification, cutting and collapsing. We use them to obtain the following results on convex and combinatorial optimization: --Linear Programming: We obtain the first improvement to the running time for linear programming in 25 years. The convergence rate of this randomized algorithm nearly matches the universal barrier for interior point methods. As a corollary, we obtain the first ... time randomized algorithm for solving the maximum flow problem on directed graphs with m edges and n vertices. This improves upon the previous fastest running time of achieved over 15 years ago by Goldberg and Rao. --Maximum Flow Problem: We obtain one of the first almost-linear time randomized algorithms for approximating the maximum flow in undirected graphs. As a corollary, we improve the running time of a wide range of algorithms that use the computation of maximum flows as a subroutine. --Non-Smooth Convex Optimization: We obtain the first nearly-cubic time randomized algorithm for convex problems under the black box model. As a corollary, this implies a polynomially faster algorithm for three fundamental problems in computer science: submodular function minimization, matroid intersection, and semidefinite programming. --Graph Sparsification: We obtain the first almost-linear time randomized algorithm for spectrally approximating any graph by one with just a linear number of edges. This sparse graph approximately preserves all cut values of the original graph and is useful for solving a wide range of combinatorial problems. This algorithm improves all previous linear-sized constructions, which required at least quadratic time. --Numerical Linear Algebra: Multigrid is an efficient method for solving large-scale linear systems which arise from graphs in low dimensions. It has been used extensively for 30 years in scientific computing. Unlike the previous approaches that make assumptions on the graphs, we give the first generalization of the multigrid that provably solves Laplacian systems of any graphs in nearly-linear expected time.
by Yin Tat Lee.
Ph. D.
26
Minkoff, Maria 1976. "Approximation algorithms for combinatorial optimization under uncertainty." Thesis, Massachusetts Institute of Technology, 2003. http://hdl.handle.net/1721.1/87452.
Full textAbstract:
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2003.Includes bibliographical references (p. 87-90).
Combinatorial optimization problems arise in many fields of industry and technology, where they are frequently used in production planning, transportation, and communication network design. Whereas in the context of classical discrete optimization it is usually assumed that the problem inputs are known, in many real-world applications some of the data may be subject to an uncertainty, often because it represents information about the future. In the field of stochastic optimization uncertain parameters are usually represented as random variables that have known probability distributions. In this thesis we study a number of different scenarios of planning under uncertainty motivated by applications from robotics, communication network design and other areas. We develop approximation algorithms for several NP-hard stochastic combinatorial optimization problems in which the input is uncertain - modeled by probability distribution - and the goal is to design a solution in advance so as to minimize expected future costs or maximize expected future profits. We develop techniques for dealing with certain probabilistic cost functions making it possible to derive combinatorial properties of an optimum solution. This enables us to make connections with already well-studied combinatorial optimization problems and apply some of the tools developed for them. The first problem we consider is motivated by an application from AI, in which a mobile robot delivers packages to various locations. The goal is to design a route for robot to follow so as to maximize the value of packages successfully delivered subject to an uncertainty in the robot's lifetime.
(cont.) We model this problem as an extension of the well-studied Prize-Collecting Traveling Salesman problem, and develop a constant factor approximation algorithm for it, solving an open question along the way. Next we examine several classical combinatorial optimization problems such as bin-packing, vertex cover, and shortest path in the context of a "preplanning" framework, in which one can "plan ahead" based on limited information about the problem input, or "wait and see" until the entire input becomes known, albeit incurring additional expense. We study this time-information tradeoff, and show how to approximately optimize the choice of what to purchase in advance and what to defer. The last problem studied, called maybecast is concerned with designing a routing network under a probabilistic distribution of clients using locally available information. This problem can be modeled as a stochastic version of the Steiner tree problem. However probabilistic objective function turns it into an instance of a challenging optimization problem with concave costs.
by Maria Minkoff.
Ph.D.
27
Fernandes, Muritiba Albert Einstein <1983>. "Algorithms and Models For Combinatorial Optimization Problems." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2010. http://amsdottorato.unibo.it/2897/1/FernandesMuritiba_AlbertEinstein_tesi.pdf.
Full textAbstract:
In this thesis we present some combinatorial optimization problems, suggest models and algorithms for their effective solution. For each problem,we give its description, followed by a short literature review, provide methods to solve it and, finally, present computational results and comparisons with previous works to show the effectiveness of the proposed approaches. The considered problems are: the Generalized Traveling Salesman Problem (GTSP), the Bin Packing Problem with Conflicts(BPPC) and the Fair Layout Problem (FLOP).
28
Fernandes, Muritiba Albert Einstein <1983>. "Algorithms and Models For Combinatorial Optimization Problems." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2010. http://amsdottorato.unibo.it/2897/.
Full textAbstract:
In this thesis we present some combinatorial optimization problems, suggest models and algorithms for their effective solution. For each problem,we give its description, followed by a short literature review, provide methods to solve it and, finally, present computational results and comparisons with previous works to show the effectiveness of the proposed approaches. The considered problems are: the Generalized Traveling Salesman Problem (GTSP), the Bin Packing Problem with Conflicts(BPPC) and the Fair Layout Problem (FLOP).
29
Kanade, Gaurav Nandkumar. "Combinatorial optimization problems in geometric settings." Diss., University of Iowa, 2011. https://ir.uiowa.edu/etd/1152.
Full textAbstract:
We consider several combinatorial optimization problems in a geometric set- ting. The first problem we consider is the problem of clustering to minimize the sum of radii. Given a positive integer k and a set of points with interpoint distances that satisfy the definition of being a "metric", we define a ball centered at some input point and having some radius as the set of all input points that are at a distance smaller than the radius of the ball from its center. We want to cover all input points using at most k balls so that the sum of the radii of the balls chosen is minimized. We show that when the points lie in some Euclidean space and the distance measure is the standard Euclidean metric, we can find an exact solution in polynomial time under standard assumptions about the model of computation.
The second problem we consider is the Network Spanner Topology Design problem. In this problem, given a set of nodes in the network, represented by points in some geometric setting - either a plane or a 1.5-D terrain, we want to compute a height assignment function h that assigns a height to a tower at every node such that the set of pairs of nodes that can form a direct link with each other under this height function forms a connected spanner. A pair of nodes can form a direct link if they are within a bounded distance B of each other and the heights of towers at the two nodes are sufficient to achieve Line-of-Sight connectivity - i.e. the straight line connecting the top of the towers lies above any obstacles. In the planar setting where the obstacles are modeled as having a certain maximum height and minimum clearance distance, we give a constant factor approximation algorithm. In the case where the points lie on a 1.5-D terrain we illustrate that it might be hard to use Computational Geometry to achieve efficient approximations.
The final problem we consider is the Multiway Barrier Cut problem. Here, given a set of points in the plane and a set of unit disk sensors also in the plane such that any path in the plane between any pair of input points hits at least one of the given sensor disks we consider the problem of finding the minimum size subset of these disks that still achieves this separation. We give a constant factor approximation algorithm for this problem.
30
Aljamea, Mudhi Mohammed. "Advances in string algorithms for information security applications." Thesis, King's College London (University of London), 2016. https://kclpure.kcl.ac.uk/portal/en/theses/advances-in-string-algorithms-for-information-security-applications(93f6c82c-8b7a-4fb1-a0bd-29f14549d57c).html.
Full textAbstract:
This thesis focuses on introducing novel algorithms in information security through studying successful algorithms in bioinformatics and adapting them to solve some open problems in information security. Although, the problems in both bioinformatics and information security are different, yet, they might be considered very similar when it comes to identifying and solving them using Stringology techniques. Different successful bioinformatics algorithms have been studied and introduced to solve different security problems such as malware detection, biometrics and big data. Firstly, we present a dynamic computer malware detection model; a novel approach for detecting malware code embedded in different types of computer files, with consistency, accuracy and in high speed without excessive memory usages. This model was inspired by REAL; an efficient read aligner used by next generation sequencing for processing biological data. In addition, we introduce a novel algorithmic approach to detect malicious URLs in image secret communications. Secondly, we also focus on biometrics, specifically fingerprint which is considered to be one of the most reliable and used technique to identify individuals. In particular, we introduce a new fingerprint matching technique, which matches the fingerprint information using circular approximate string matching to solve the rotation problem overcoming the previous methods’ obstacles. Finally, we conclude with an algorithmic approach to analyse big data readings from smart meters to confirm some privacy issues concerns.
31
Smith, Rebecca Nicole. "Combinatorial algorithms involving pattern containing and avoiding permutations." [Gainesville, Fla.] : University of Florida, 2005. http://purl.fcla.edu/fcla/etd/UFE0009783.
Full text
32
Cui, Xinwei. "Using genetic algorithms to solve combinatorial optimization problems." FIU Digital Commons, 1991. http://digitalcommons.fiu.edu/etd/2684.
Full textAbstract:
Genetic algorithms are stochastic search techniques based on the mechanics of natural selection and natural genetics. Genetic algorithms differ from traditional analytical methods by using genetic operators and historic cumulative information to prune the search space and generate plausible solutions. Recent research has shown that genetic algorithms have a large range and growing number of applications.
The research presented in this thesis is that of using genetic algorithms to solve some typical combinatorial optimization problems, namely the Clique, Vertex Cover and Max Cut problems. All of these are NP-Complete problems. The empirical results show that genetic algorithms can provide efficient search heuristics for solving these combinatorial optimization problems.
Genetic algorithms are inherently parallel. The Connection Machine system makes parallel implementation of these inherently parallel algorithms possible. Both sequential genetic algorithms and parallel genetic algorithms for Clique, Vertex Cover and Max Cut problems have been developed and implemented on the SUN4 and the Connection Machine systems respectively.
33
Uppman, Hannes. "On Some Combinatorial Optimization Problems : Algorithms and Complexity." Doctoral thesis, Linköpings universitet, Programvara och system, 2015. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-116859.
Full textAbstract:
This thesis is about the computational complexity of several classes of combinatorial optimization problems, all related to the constraint satisfaction problems. A constraint language consists of a domain and a set of relations on the domain. For each such language there is a constraint satisfaction problem (CSP). In this problem we are given a set of variables and a collection of constraints, each of which is constraining some variables with a relation in the language. The goal is to determine if domain values can be assigned to the variables in a way that satisfies all constraints. An important question is for which constraint languages the corresponding CSP can be solved in polynomial time. We study this kind of question for optimization problems related to the CSPs. The main focus is on extended minimum cost homomorphism problems. These are optimization versions of CSPs where instances come with an objective function given by a weighted sum of unary cost functions, and where the goal is not only to determine if a solution exists, but to find one of minimum cost. We prove a complete classification of the complexity for these problems on three-element domains. We also obtain a classification for the so-called conservative case. Another class of combinatorial optimization problems are the surjective maximum CSPs. These problems are variants of CSPs where a non-negative weight is attached to each constraint, and the objective is to find a surjective mapping of the variables to values that maximizes the weighted sum of satisfied constraints. The surjectivity requirement causes these problems to behave quite different from for example the minimum cost homomorphism problems, and many powerful techniques are not applicable. We prove a dichotomy for the complexity of the problems in this class on two-element domains. An essential ingredient in the proof is an algorithm that solves a generalized version of the minimum cut problem. This algorithm might be of independent interest. In a final part we study properties of NP-hard optimization problems. This is done with the aid of restricted forms of polynomial-time reductions that for example preserves solvability in sub-exponential time. Two classes of optimization problems similar to those discussed above are considered, and for both we obtain what may be called an easiest NP-hard problem. We also establish some connections to the exponential time hypothesis.
34
Leino, Anders. "Exact and Monte-Carlo algorithms for combinatorial games." Thesis, Umeå universitet, Institutionen för fysik, 2014. http://urn.kb.se/resolve?urn=urn:nbn:se:umu:diva-88363.
Full textAbstract:
This thesis concerns combinatorial games and algorithms that can be used to play them.Basic definitions and results about combinatorial games are covered, and an implementation of the minimax algorithm with alpha-beta pruning is presented.Following this, we give a description and implementation of the common UCT (Upper Confidence bounds applied to Trees) variant of MCTS (Monte-Carlo tree search).Then, a framework for testing the behavior of UCT as first player, at various numbers of iterations (namely 2,7, ... 27), versus minimax as second player, is described.Finally, we present the results obtained by applying this framework to the 2.2 million smallest non-trivial positional games having winning sets of size either 2 or 3.It is seen that on almost all different classifications of the games studied, UCT converges quickly to near-perfect play.Denna rapport handlar om kombinatoriska spel och algoritmer som kan användas för att spela dessa.Grundläggande definitioner och resultat som berör kombinatoriska spel täcks, och en implementation av minimax-algoritmen med alpha-beta beskärning ges.Detta följs av en beskrivning samt en implementation av UCT varianten av MCTS (Monte-Carlo tree search).Sedan beskrivs ett ramverk för att testa beteendet för UCT som första spelare, vid olika antal iterationer (nämligen 2, 7, ... 27), mot minimax som andra spelare.Till sist beskrivs resultaten vi funnit genom att använda detta ramverk för att spela de 2,2 miljoner minsta icke triviala positionella spelen med vinstmängder av storlek antingen 2 eller 3.Vi finner att, för nästan alla olika klassificeringar av spel vi studerar, så konvergerar UCT snabbt mot nära perfekt spel.
35
Allwright, James. "Parallel algorithms for combinatorial optimization on transputer arrays." Thesis, University of Southampton, 1990. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.255769.
Full text
36
Li, Quan Ph D. Massachusetts Institute of Technology. "Algorithms and algorithmic obstacles for probabilistic combinatorial structures." Thesis, Massachusetts Institute of Technology, 2018. http://hdl.handle.net/1721.1/115765.
Full textAbstract:
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2018.Cataloged from PDF version of thesis.
Includes bibliographical references (pages 209-214).
We study efficient average-case (approximation) algorithms for combinatorial optimization problems, as well as explore the algorithmic obstacles for a variety of discrete optimization problems arising in the theory of random graphs, statistics and machine learning. In particular, we consider the average-case optimization for three NP-hard combinatorial optimization problems: Large Submatrix Selection, Maximum Cut (Max-Cut) of a graph and Matrix Completion. The Large Submatrix Selection problem is to find a k x k submatrix of an n x n matrix with i.i.d. standard Gaussian entries, which has the largest average entry. It was shown in [13] using non-constructive methods that the largest average value of a k x k submatrix is 2(1 + o(1) [square root] log n/k with high probability (w.h.p.) when k = O(log n/ log log n). We show that a natural greedy algorithm called Largest Average Submatrix LAS produces a submatrix with average value (1+ o(1)) [square root] 2 log n/k w.h.p. when k is constant and n grows, namely approximately [square root] 2 smaller. Then by drawing an analogy with the problem of finding cliques in random graphs, we propose a simple greedy algorithm which produces a k x k matrix with asymptotically the same average value (1+o(1) [square root] 2log n/k w.h.p., for k = o(log n). Since the maximum clique problem is a special case of the largest submatrix problem and the greedy algorithm is the best known algorithm for finding cliques in random graphs, it is tempting to believe that beating the factor [square root] 2 performance gap suffered by both algorithms might be very challenging. Surprisingly, we show the existence of a very simple algorithm which produces a k x k matrix with average value (1 + o[subscript]k(1) + o(1))(4/3) [square root] 2log n/k for k = o((log n)¹.⁵), that is, with asymptotic factor 4/3 when k grows. To get an insight into the algorithmic hardness of this problem, and motivated by methods originating in the theory of spin glasses, we conduct the so-called expected overlap analysis of matrices with average value asymptotically (1 + o(1))[alpha][square root] 2 log n/k for a fixed value [alpha] [epsilon] [1, fixed value a E [1, [square root]2]. The overlap corresponds to the number of common rows and common columns for pairs of matrices achieving this value. We discover numerically an intriguing phase transition at [alpha]* [delta]= 5[square root]2/(3[square root]3) ~~ 1.3608.. [epsilon] [4/3, [square root]2]: when [alpha] < [alpha]* the space of overlaps is a continuous subset of [0, 1]², whereas [alpha] = [alpha]* marks the onset of discontinuity, and as a result the model exhibits the Overlap Gap Property (OGP) when [alpha] > [alpha]*, appropriately defined. We conjecture that OGP observed for [alpha] > [alpha]* also marks the onset of the algorithmic hardness - no polynomial time algorithm exists for finding matrices with average value at least (1+o(1)[alpha][square root]2log n/k, when [alpha] > [alpha]* and k is a growing function of n. Finding a maximum cut of a graph is a well-known canonical NP-hard problem. We consider the problem of estimating the size of a maximum cut in a random Erdős-Rényi graph on n nodes and [cn] edges. We establish that the size of the maximum cut normalized by the number of nodes belongs to the interval [c/2 + 0.47523[square root]c,c/2 + 0.55909[square root]c] w.h.p. as n increases, for all sufficiently large c. We observe that every maximum size cut satisfies a certain local optimality property, and we compute the expected number of cuts with a given value satisfying this local optimality property. Estimating this expectation amounts to solving a rather involved multi-dimensional large deviations problem. We solve this underlying large deviation problem asymptotically as c increases and use it to obtain an improved upper bound on the Max-Cut value. The lower bound is obtained by application of the second moment method, coupled with the same local optimality constraint, and is shown to work up to the stated lower bound value c/2 + 0.47523[square root]c. We also obtain an improved lower bound of 1.36000n on the Max-Cut for the random cubic graph or any cubic graph with large girth, improving the previous best bound of 1.33773n. Matrix Completion is the problem of reconstructing a rank-k n x n matrix M from a sampling of its entries. We propose a new matrix completion algorithm using a novel sampling scheme based on a union of independent sparse random regular bipartite graphs. We show that under a certain incoherence assumption on M and for the case when both the rank and the condition number of M are bounded, w.h.p. our algorithm recovers an [epsilon]-approximation of M in terms of the Frobenius norm using O(nlog² (1/[epsilon])) samples and in linear time O(nlog² (1/[epsilon])). This provides the best known bounds both on the sample complexity and computational cost for reconstructing (approximately) an unknown low-rank matrix. The novelty of our algorithm is two new steps of thresholding singular values and rescaling singular vectors in the application of the "vanilla" alternating minimization algorithm. The structure of sparse random regular graphs is used heavily for controlling the impact of these regularization steps.
by Quan Li.
Ph. D.
37
Sinclair, Alistair John. "Randomised algorithms for counting and generating combinatorial structures." Thesis, University of Edinburgh, 1988. http://hdl.handle.net/1842/11392.
Full text
38
Yagiura, Mutsunori. "Studies on Metaheuristic Algorithms for Combinatorial Optimization Problems." Kyoto University, 1999. http://hdl.handle.net/2433/157060.
Full textAbstract:
本文データは平成22年度国立国会図書館の学位論文(博士)のデジタル化実施により作成された画像ファイルを基にpdf変換したものであるKyoto University (京都大学)
0048
新制・論文博士
博士(工学)
乙第10101号
論工博第3416号
新制||工||1146(附属図書館)
UT51-99-G578
(主査)教授 茨木 俊秀, 教授 岩間 一雄, 教授 加藤 直樹
学位規則第4条第2項該当
39
Land, Mark William Shannon. "Evolutionary algorithms with local search for combinatorial optimization /." Diss., Connect to a 24 p. preview or request complete full text in PDF format. Access restricted to UC campuses, 1998. http://wwwlib.umi.com/cr/ucsd/fullcit?p9914083.
Full text
40
Lomonosov, Andrew. "Graph and combinatorial algorithms for geometric constraint solving." [Gainesville, Fla.] : University of Florida, 2004. http://purl.fcla.edu/fcla/etd/UFE0001060.
Full text
41
Skidmore, Gerald. "Metaheuristics and combinatorial optimization problems /." Online version of thesis, 2006. https://ritdml.rit.edu/dspace/handle/1850/2319.
Full text
42
Nonobe, Koji. "Studies on General Purpose Heuristic Algorithms for Combinatorial Problems." 京都大学 (Kyoto University), 2000. http://hdl.handle.net/2433/180898.
Full text
43
Ghebreamlak, Kidane Asrat. "Analysis of Algorithms for Combinatorial Auctions and Related Problems." Doctoral thesis, Uppsala : Department of Mathematics, 2005. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-6246.
Full text
44
Richey, Michael Bruce. "Combinatorial optimization on series-parallel graphs : algorithms and complexity." Diss., Georgia Institute of Technology, 1985. http://hdl.handle.net/1853/24542.
Full text
45
Ryan, Mark Desmond Charles. "Hybrid genetic algorithms for real world combinatorial optimization problems." Thesis, University of East Anglia, 2001. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.393303.
Full text
46
Karapetyan, Daniil. "Design, evaluation and analysis of combinatorial optimization heuristic algorithms." Thesis, Royal Holloway, University of London, 2010. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.531316.
Full text
47
Fischer, Thomas. "Distributed memetic algorithms for graph theoretical combinatorial optimization problems." Berlin Logos-Verl, 2008. http://d-nb.info/994066945/04.
Full text
48
Voudouris, Christos. "Guided local search for combinatorial optimisation problems." Thesis, University of Essex, 1997. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.361019.
Full text
49
Niedermeier, Rolf. "Invitation to fixed-parameter algorithms /." Oxford [u.a.] : Oxford Univ. Press, 2006. http://www.gbv.de/dms/ilmenau/toc/500666768niede.PDF.
Full text
50
Cheng, Lok-lam, and 鄭樂霖. "Approximate string matching in DNA sequences." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2003. http://hub.hku.hk/bib/B29350591.
Full text