Готові списки джерел за темами / Combinatorial algorithms on string

Зміст

Статті в журналах
Дисертації
Книги
Частини книг
Тези доповідей конференцій
Звіти організацій

Добірка наукової літератури з теми "Combinatorial algorithms on string"

Автор: Grafiati

Опубліковано: 11 березня 2023

Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями

Оберіть тип джерела:

Ознайомтеся зі списками актуальних статей, книг, дисертацій, тез та інших наукових джерел на тему "Combinatorial algorithms on string".

Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.

Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.

Статті в журналах з теми "Combinatorial algorithms on string"

Bernardini, Giulia, Huiping Chen, Alessio Conte, Roberto Grossi, Grigorios Loukides, Nadia Pisanti, Solon P. Pissis, Giovanna Rosone, and Michelle Sweering. "Combinatorial Algorithms for String Sanitization." ACM Transactions on Knowledge Discovery from Data 15, no. 1 (January 6, 2021): 1–34. http://dx.doi.org/10.1145/3418683.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

TAKAOKA, TADAO, and STEPHEN VIOLICH. "FUSING LOOPLESS ALGORITHMS FOR COMBINATORIAL GENERATION." International Journal of Foundations of Computer Science 18, no. 02 (April 2007): 263–93. http://dx.doi.org/10.1142/s0129054107004681.

Повний текст джерела

Анотація:

Some combinatorial generation problems can be broken into subproblems for which loopless algorithms already exist. This article discusses means by which loopless algorithms can be fused to produce a new loopless algorithm that solves the original problem. It demonstrates this method with two new loopless algorithms. The first generates well-formed parenthesis strings containing two different types of parentheses. The second generates multiset permutations in linear space using only arrays; it is simpler and more efficient than the recent algorithm of Korsh & LaFollette.

Стилі APA, Harvard, Vancouver, ISO та ін.

Ambainis, Andris, and Ashley Montanaro. "Quantum algorithms for search with wildcards and combinatorial group testing." Quantum Information and Computation 14, no. 5&6 (May 2014): 439–53. http://dx.doi.org/10.26421/qic14.5-6-4.

Повний текст джерела

Анотація:

We consider two combinatorial problems. The first we call ``search with wildcards'': given an unknown $n$-bit string $x$, and the ability to check whether any subset of the bits of $x$ is equal to a provided query string, the goal is to output $x$. We give a nearly optimal $O(\sqrt{n} \log n)$ quantum query algorithm for search with wildcards, beating the classical lower bound of $\Omega(n)$ queries. Rather than using amplitude amplification or a quantum walk, our algorithm is ultimately based on the solution to a state discrimination problem. The second problem we consider is combinatorial group testing, which is the task of identifying a subset of at most $k$ special items out of a set of $n$ items, given the ability to make queries of the form ``does the set $S$ contain any special items?''\ for any subset $S$ of the $n$ items. We give a simple quantum algorithm which uses $O(k)$ queries to solve this problem, as compared with the classical lower bound of $\Omega(k \log(n/k))$ queries.

Стилі APA, Harvard, Vancouver, ISO та ін.

Moraglio, A., J. Togelius, and S. Silva. "Geometric Differential Evolution for Combinatorial and Programs Spaces." Evolutionary Computation 21, no. 4 (November 2013): 591–624. http://dx.doi.org/10.1162/evco_a_00099.

Повний текст джерела

Анотація:

Geometric differential evolution (GDE) is a recently introduced formal generalization of traditional differential evolution (DE) that can be used to derive specific differential evolution algorithms for both continuous and combinatorial spaces retaining the same geometric interpretation of the dynamics of the DE search across representations. In this article, we first review the theory behind the GDE algorithm, then, we use this framework to formally derive specific GDE for search spaces associated with binary strings, permutations, vectors of permutations and genetic programs. The resulting algorithms are representation-specific differential evolution algorithms searching the target spaces by acting directly on their underlying representations. We present experimental results for each of the new algorithms on a number of well-known problems comprising NK-landscapes, TSP, and Sudoku, for binary strings, permutations, and vectors of permutations. We also present results for the regression, artificial ant, parity, and multiplexer problems within the genetic programming domain. Experiments show that overall the new DE algorithms are competitive with well-tuned standard search algorithms.

Стилі APA, Harvard, Vancouver, ISO та ін.

Nazeen, Sumaiya, M. Sohel Rahman, and Rezwana Reaz. "Indeterminate string inference algorithms." Journal of Discrete Algorithms 10 (January 2012): 23–34. http://dx.doi.org/10.1016/j.jda.2011.08.002.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Graf, Alessandra, David G. Harris, and Penny Haxell. "Algorithms for Weighted Independent Transversals and Strong Colouring." ACM Transactions on Algorithms 18, no. 1 (January 31, 2022): 1–16. http://dx.doi.org/10.1145/3474057.

Повний текст джерела

Анотація:

An independent transversal (IT) in a graph with a given vertex partition is an independent set consisting of one vertex in each partition class. Several sufficient conditions are known for the existence of an IT in a given graph and vertex partition, which have been used over the years to solve many combinatorial problems. Some of these IT existence theorems have algorithmic proofs, but there remains a gap between the best existential bounds and the bounds obtainable by efficient algorithms. Recently, Graf and Haxell (2018) described a new (deterministic) algorithm that asymptotically closes this gap, but there are limitations on its applicability. In this article, we develop a randomized algorithm that is much more widely applicable, and demonstrate its use by giving efficient algorithms for two problems concerning the strong chromatic number of graphs.

Стилі APA, Harvard, Vancouver, ISO та ін.

Hamad, Ibrahim Ismael, and Mohammad S. Hasan. "A Review: On using ACO Based Hybrid Algorithms for Path Planning of Multi-Mobile Robotics." International Journal of Interactive Mobile Technologies (iJIM) 14, no. 18 (November 10, 2020): 145. http://dx.doi.org/10.3991/ijim.v14i18.16371.

Повний текст джерела

Анотація:

Abstract-The path planning for Multi Mobile Robotic (MMR) system is a recent combinatorial optimisation problem. In the last decade, many researches have been published to solve this problem. Most of these researches focused on metaheuristic algorithms. This paper reviews articles on Ant Colony Optimisation (ACO) and its hybrid versions to solve the problem. The original Dorigo’s ACO algorithm uses exploration and exploitation phases to find the shortest route in a combinatorial optimisation problem in general without touching mapping, localisation and perception. Due to the properties of MMR, adaptations have been made to ACO algorithms. In this review paper, a literature survey of the recent studies on upgrading, modifications and applications of the ACO algorithms has been discussed to evaluate the application of the different versions of ACO in the MMR domain. The evaluation considered the quality, speed of convergence, robustness, scalability, flexibility of MMR and obstacle avoidance, static and dynamic environment characteristics of the tasks.

Стилі APA, Harvard, Vancouver, ISO та ін.

Saud, Suhair, Halife Kodaz, and İsmail Babaoğlu. "Solving Travelling Salesman Problem by Using Optimization Algorithms." KnE Social Sciences 3, no. 1 (January 15, 2018): 17. http://dx.doi.org/10.18502/kss.v3i1.1394.

Повний текст джерела

Анотація:

This paper presents the performances of different types of optimization techniques used in artificial intelligence (AI), these are Ant Colony Optimization (ACO), Improved Particle Swarm Optimization with a new operator (IPSO), Shuffled Frog Leaping Algorithms (SFLA) and modified shuffled frog leaping algorithm by using a crossover and mutation operators. They were used to solve the traveling salesman problem (TSP) which is one of the popular and classical route planning problems of research and it is considered as one of the widely known of combinatorial optimization. Combinatorial optimization problems are usually simple to state but very difficult to solve. ACO, PSO, and SFLA are intelligent meta-heuristic optimization algorithms with strong ability to analyze the optimization problems and find the optimal solution. They were tested on benchmark problems from TSPLIB and the test results were compared with each other.Keywords: Ant colony optimization, shuffled frog leaping algorithms, travelling salesman problem, improved particle swarm optimization

Стилі APA, Harvard, Vancouver, ISO та ін.

CLÉMENT, JULIEN, and LAURA GIAMBRUNO. "Representing prefix and border tables: results on enumeration." Mathematical Structures in Computer Science 27, no. 2 (May 22, 2015): 257–76. http://dx.doi.org/10.1017/s0960129515000146.

Повний текст джерела

Анотація:

For some text algorithms, the real measure for the complexity analysis is not the string itself but its structure stored in its prefix table or equivalently border table. In this paper, we define the combinatorial class of prefix lists, namely a sequence of integers together with their size, and an injection ψ from the class of prefix tables to the class of prefix lists. We call a valid prefix list the image by ψ of a prefix table. In particular, we describe algorithms converting a prefix/border table to a prefix list and inverse linear algorithms from computing from a prefix list L = ψ(P) two words respectively in a minimal size alphabet and on a maximal size alphabet with P as prefix table. We then give a new upper bound on the number of prefix tables for strings of length n (on any alphabet) which is of order (1 + ϕ)n (with $\varphi=\frac{1+\sqrt{5}}{2}$ the golden mean) and also present a corresponding lower bound.

Стилі APA, Harvard, Vancouver, ISO та ін.

FONTAINE, MARC, STEFAN BURKHARDT, and JUHA KÄRKKÄINEN. "BDD-BASED ANALYSIS OF GAPPED q-GRAM FILTERS." International Journal of Foundations of Computer Science 16, no. 06 (December 2005): 1121–34. http://dx.doi.org/10.1142/s0129054105003698.

Повний текст джерела

Анотація:

Recently, there has been a surge of interest in gapped q-gram filters for approximate string matching. Important design parameters for filters are for example the value of q, the filter-threshold and in particular the shape (aka seed) of the filter. A good choice of parameters can improve the performance of a q-gram filter by orders of magnitude and optimizing these parameters is a nontrivial combinatorial problem. We describe a new method for analyzing gapped q-gram filters. This method is simple and generic. It applies to a variety of filters, overcomes many restrictions that are present in existing algorithms and can easily be extended to new filter variants. To implement our approach, we use an extended version of BDDs (Binary Decision Diagrams), a data structure that efficiently represents sets of bit-strings. In a second step, we define a new class of multi-shape filters and analyze these filters with the BDD-based approach. Experiments show that multi-shape filters can outperform the best single-shape filters, which are currently in use, in many aspects. The BDD-based algorithm is crucial for the design and analysis of these new and better multi-shape filters. Our results apply to the k-mismatches problem, i.e. approximate string matching with Hamming distance.

Стилі APA, Harvard, Vancouver, ISO та ін.

Більше джерел

Дисертації з теми "Combinatorial algorithms on string"

BERNARDINI, GIULIA. "COMBINATORIAL METHODS FOR BIOLOGICAL DATA." Doctoral thesis, Università degli Studi di Milano-Bicocca, 2021. http://hdl.handle.net/10281/305220.

Повний текст джерела

Анотація:

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.

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Анотація:

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.

Стилі APA, Harvard, Vancouver, ISO та ін.

Wright, Colin Douglas. "Combinatorial algorithms." Thesis, University of Cambridge, 1990. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.357944.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Aslidis, Anastasios Haralampos. "Combinatorial algorithms for stacking problems." Thesis, Massachusetts Institute of Technology, 1989. http://hdl.handle.net/1721.1/33478.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Naji, Azimi Zahra <1982&gt. "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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Naji, Azimi Zahra <1982&gt. "Algorithms for Combinatorial Optimization Problems." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2010. http://amsdottorato.unibo.it/2695/.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Fischer, Johannes. "Data Structures for Efficient String Algorithms." Diss., lmu, 2007. http://nbn-resolving.de/urn:nbn:de:bvb:19-75053.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Newman, Alantha. "Algorithms for string and graph layout." Thesis, Massachusetts Institute of Technology, 2004. http://hdl.handle.net/1721.1/28745.

Повний текст джерела

Анотація:

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.

Стилі APA, Harvard, Vancouver, ISO та ін.

Cruz, Mencía Francisco. "Enhancing performance on combinatorial optimization algorithms." Doctoral thesis, Universitat Autònoma de Barcelona, 2018. http://hdl.handle.net/10803/665199.

Повний текст джерела

Анотація:

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.

Стилі APA, Harvard, Vancouver, ISO та ін.

Більше джерел

Книги з теми "Combinatorial algorithms on string"

Combinatorial algorithms. Bristol: Adam Hilger, 1990.

Знайти повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Flocchini, Paola, and Lucia Moura, eds. Combinatorial Algorithms. Cham: Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-79987-8.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Bazgan, Cristina, and Henning Fernau, eds. Combinatorial Algorithms. Cham: Springer International Publishing, 2022. http://dx.doi.org/10.1007/978-3-031-06678-8.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Fiala, Jiří, Jan Kratochvíl, and Mirka Miller, eds. Combinatorial Algorithms. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. http://dx.doi.org/10.1007/978-3-642-10217-2.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Colbourn, Charles J., Roberto Grossi, and Nadia Pisanti, eds. Combinatorial Algorithms. Cham: Springer International Publishing, 2019. http://dx.doi.org/10.1007/978-3-030-25005-8.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Lipták, Zsuzsanna, and William F. Smyth, eds. Combinatorial Algorithms. Cham: Springer International Publishing, 2016. http://dx.doi.org/10.1007/978-3-319-29516-9.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Gąsieniec, Leszek, Ralf Klasing, and Tomasz Radzik, eds. Combinatorial Algorithms. Cham: Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-48966-3.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Mäkinen, Veli, Simon J. Puglisi, and Leena Salmela, eds. Combinatorial Algorithms. Cham: Springer International Publishing, 2016. http://dx.doi.org/10.1007/978-3-319-44543-4.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Jan, Kratochvíl, Mirka Miller, and Dalibor Froncek, eds. Combinatorial Algorithms. Cham: Springer International Publishing, 2015. http://dx.doi.org/10.1007/978-3-319-19315-1.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Brankovic, Ljiljana, Joe Ryan, and William F. Smyth, eds. Combinatorial Algorithms. Cham: Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-319-78825-8.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Більше джерел

Частини книг з теми "Combinatorial algorithms on string"

Broder, Andrei. "Two counting problems solved via string encodings." In Combinatorial Algorithms on Words, 229–40. Berlin, Heidelberg: Springer Berlin Heidelberg, 1985. http://dx.doi.org/10.1007/978-3-642-82456-2_15.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Pinter, Ron Y. "Efficient String Matching with Don’t-Care Patterns." In Combinatorial Algorithms on Words, 11–29. Berlin, Heidelberg: Springer Berlin Heidelberg, 1985. http://dx.doi.org/10.1007/978-3-642-82456-2_2.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Lee, Jee-Soo, Dong Kyue Kim, Kunsoo Park, and Yookun Cho. "Efficient algorithms for approximate string matching with swaps." In Combinatorial Pattern Matching, 28–39. Berlin, Heidelberg: Springer Berlin Heidelberg, 1997. http://dx.doi.org/10.1007/3-540-63220-4_47.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Chang, William I., and Jordan Lampe. "Theoretical and empirical comparisons of approximate string matching algorithms." In Combinatorial Pattern Matching, 175–84. Berlin, Heidelberg: Springer Berlin Heidelberg, 1992. http://dx.doi.org/10.1007/3-540-56024-6_14.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Chen, Zhi-Zhong, Bin Ma, and Lusheng Wang. "Randomized and Parameterized Algorithms for the Closest String Problem." In Combinatorial Pattern Matching, 100–109. Cham: Springer International Publishing, 2014. http://dx.doi.org/10.1007/978-3-319-07566-2_11.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Allauzen, Cyril, and Mathieu Raffinot. "Simple Optimal String Matching Algorithm." In Combinatorial Pattern Matching, 364–74. Berlin, Heidelberg: Springer Berlin Heidelberg, 2000. http://dx.doi.org/10.1007/3-540-45123-4_30.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Raskhodnikova, Sofya, Dana Ron, Ronitt Rubinfeld, and Adam Smith. "Sublinear Algorithms for Approximating String Compressibility." In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 609–23. Berlin, Heidelberg: Springer Berlin Heidelberg, 2007. http://dx.doi.org/10.1007/978-3-540-74208-1_44.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Barth, Gerhard. "Relating the Average-Case Costs of the Brute-Force and Knuth-Morris-Pratt String Matching Algorithm." In Combinatorial Algorithms on Words, 45–58. Berlin, Heidelberg: Springer Berlin Heidelberg, 1985. http://dx.doi.org/10.1007/978-3-642-82456-2_4.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Baeza-Yates, Ricardo, and Gonzalo Navarro. "A faster algorithm for approximate string matching." In Combinatorial Pattern Matching, 1–23. Berlin, Heidelberg: Springer Berlin Heidelberg, 1996. http://dx.doi.org/10.1007/3-540-61258-0_1.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Odlyzko, A. M. "Enumeration of Strings." In Combinatorial Algorithms on Words, 205–28. Berlin, Heidelberg: Springer Berlin Heidelberg, 1985. http://dx.doi.org/10.1007/978-3-642-82456-2_14.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Тези доповідей конференцій з теми "Combinatorial algorithms on string"

Callanan, Jesse, Oladapo Ogunbodede, Maulikkumar Dhameliya, Jun Wang, and Rahul Rai. "Hierarchical Combinatorial Design and Optimization of Quasi-Periodic Metamaterial Structures." In ASME 2018 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. American Society of Mechanical Engineers, 2018. http://dx.doi.org/10.1115/detc2018-85914.

Повний текст джерела

Анотація:

As advanced manufacturing techniques such as additive manufacturing become widely available, it is of interest to investigate the potential advantages that arise when designing periodic metamaterials to achieve a specific desired behavior or physical property. Designing the fine scale detailed geometry of periodic metamaterials to achieve a specified behavior falls under the category of notoriously intractable inverse problems. To simplify solving the inverse problem, most relevant works represent metamaterials as periodic single unit cell structures repeated in regular lattices. Such representation simplifies modeling and simulation task but at the cost of possibly limiting the range of physical behaviors that can be achieved through the use of more than one unit cell structures. This article outlines a quasi-periodic representation that utilizes more than a single unit cell to generate periodic metamaterials. Additionally, a hierarchical optimization scheme to optimize the generating function for a quasi-periodic structure using the genetic algorithm (GA) and a barrier function interior point method is also sketched to solve the inverse problem. To demonstrate the utility of the proposed hierarchical optimization framework to solve quasi-periodic metamaterial inverse problem, a problem in which the objective is to minimize the total strain in the structure while subjected to weight and the total-size constraint is considered. We detail the overall computational approach in which geometric representation, optimization algorithms, and finite element analysis are coupled and report preliminary numerical experiments.

Стилі APA, Harvard, Vancouver, ISO та ін.

Fu, Yan, R. J. Yang, and Isheng Yeh. "Optimal Design of an Inflatable Knee Bolster Using Genetic Algorithms." In ASME 2001 International Mechanical Engineering Congress and Exposition. American Society of Mechanical Engineers, 2001. http://dx.doi.org/10.1115/imece2001/amd-25460.

Повний текст джерела

Анотація:

Abstract An inflatable knee bolster (IKB) is an inflatable airbag cushion deployed in the knee area in conjunction with the frontal airbags to reduce the potential lower-leg injuries. It is conceivable that an IKB can reduce the femur loads. However, its effects on the occupant head and chest injuries and its interaction with the other components of the occupant restraint system are unknown. The goal of this study is to evaluate the potential application of an inflatable knee bolster to improve the occupant safety performance, such as the U.S. new car assessment program (NCAP) star rating. An efficient genetic algorithm method is developed for solving this type of large-scaled, combinatorial, and discrete optimization problems. Genetic algorithm works simultaneously on a population of solution strings according to the survivor of the fitness and provides a population of solutions, which gives more flexibility for engineering implementation and produces a potential global optimal design. The results demonstrate that the genetic algorithm is a useful and applicable tool to optimize design configurations for large-scaled occupant simulation problems.

Стилі APA, Harvard, Vancouver, ISO та ін.

Tschiatschek, Sebastian, Aytunc Sahin, and Andreas Krause. "Differentiable Submodular Maximization." In Twenty-Seventh International Joint Conference on Artificial Intelligence {IJCAI-18}. California: International Joint Conferences on Artificial Intelligence Organization, 2018. http://dx.doi.org/10.24963/ijcai.2018/379.

Повний текст джерела

Анотація:

We consider learning of submodular functions from data. These functions are important in machine learning and have a wide range of applications, e.g. data summarization, feature selection and active learning. Despite their combinatorial nature, submodular functions can be maximized approximately with strong theoretical guarantees in polynomial time. Typically, learning the submodular function and optimization of that function are treated separately, i.e. the function is first learned using a proxy objective and subsequently maximized. In contrast, we show how to perform learning and optimization jointly. By interpreting the output of greedy maximization algorithms as distributions over sequences of items and smoothening these distributions, we obtain a differentiable objective. In this way, we can differentiate through the maximization algorithms and optimize the model to work well with the optimization algorithm. We theoretically characterize the error made by our approach, yielding insights into the tradeoff of smoothness and accuracy. We demonstrate the effectiveness of our approach for jointly learning and optimizing on synthetic maxcut data, and on real world applications such as product recommendation and image collection summarization.

Стилі APA, Harvard, Vancouver, ISO та ін.

Lladser, Manuel E. "Markovian embeddings of general random strings." In 2008 Proceedings of the Fifth Workshop on Analytic Algorithmics and Combinatorics (ANALCO). Philadelphia, PA: Society for Industrial and Applied Mathematics, 2008. http://dx.doi.org/10.1137/1.9781611972986.2.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Ghosh, Subhroshekhar, Thomas M. Liggett, and Robin Pemantle. "Multivariate CLT follows from strong Rayleigh property." In 2017 Proceedings of the Fourteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO). Philadelphia, PA: Society for Industrial and Applied Mathematics, 2017. http://dx.doi.org/10.1137/1.9781611974775.14.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Hagerup, Torben. "Optimal parallel string algorithms." In the twenty-sixth annual ACM symposium. New York, New York, USA: ACM Press, 1994. http://dx.doi.org/10.1145/195058.195202.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Pogarskaia, Tatiana, Sergey Lupuleac, Julia Shinder, and Philipp Westphal. "Optimization of the Installation Sequence for the Temporary Fasteners in the Aircraft Industry." In ASME 2021 International Mechanical Engineering Congress and Exposition. American Society of Mechanical Engineers, 2021. http://dx.doi.org/10.1115/imece2021-69579.

Повний текст джерела

Анотація:

Abstract Riveting and bolting are common assembly methods in aircraft production. The fasteners are installed immediately after hole drilling and fix the relative tangential displacements of the parts, that took place. A proper fastener sequence installation is very important because a wrong one can lead to a “bubble-effect”, when gap between parts after fastening becomes larger in some areas rather than being reduced. This circumstance affects the quality of the final assembly. For that reason, the efficient methods for determination of fastening sequence taking into account the specifics of the assembly process are needed. The problem is complicated by several aspects. First of all, it is a combinatorial problem with uncertain input data. Secondly, the assembly quality evaluation demands the time-consuming computations of the stress-strain state of the fastened parts caused by sequential installation of fasteners. Most commonly used strategies (heuristic methods, approximation algorithms) require a large number of computational iterations what dramatically complicates the problem. The paper presents the efficient methods of fastener sequence optimization based on greedy strategy and the specifics of the assembly process. Verification of the results by comparison to commonly used installation strategies shows its quality excellence.

Стилі APA, Harvard, Vancouver, ISO та ін.

Shaw, Peter. "Combinatorial Algorithms in Machine Learning." In 2018 First International Conference on Artificial Intelligence for Industries (AI4I). IEEE, 2018. http://dx.doi.org/10.1109/ai4i.2018.8665720.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Cormode, Graham, and S. Muthukrishnan. "Combinatorial Algorithms for Compressed Sensing." In 2006 40th Annual Conference on Information Sciences and Systems. IEEE, 2006. http://dx.doi.org/10.1109/ciss.2006.286461.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Bansal, Nikhil, and Ryan Williams. "Regularity Lemmas and Combinatorial Algorithms." In 2009 IEEE 50th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2009. http://dx.doi.org/10.1109/focs.2009.76.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Звіти організацій з теми "Combinatorial algorithms on string"

Pinar, Ali. High-performance combinatorial algorithms. Office of Scientific and Technical Information (OSTI), October 2003. http://dx.doi.org/10.2172/820273.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Pothen, Alex. Combinatorial Algorithms in Scientific Computing. Office of Scientific and Technical Information (OSTI), February 2021. http://dx.doi.org/10.2172/1765882.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Leighton, Tom. Parallel and Distributed Computing Combinatorial Algorithms. Fort Belvoir, VA: Defense Technical Information Center, October 1993. http://dx.doi.org/10.21236/ada277333.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Laub, Alan J., and Charles Kenney. Numerically Stable Algorithms in String Dynamics. Fort Belvoir, VA: Defense Technical Information Center, September 1993. http://dx.doi.org/10.21236/ada275898.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Goldberg, Andrew V., Serge A. Plotkin, and Eva Tardos. Combinatorial Algorithms for the Generalized Circulation Problem. Fort Belvoir, VA: Defense Technical Information Center, May 1988. http://dx.doi.org/10.21236/ada197409.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Plotkin, Serge. Research in Graph Algorithms and Combinatorial Optimization. Fort Belvoir, VA: Defense Technical Information Center, March 1995. http://dx.doi.org/10.21236/ada292630.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Shepherd, F. B. Fundamentals of Combinatorial Optimization and Algorithms Design: December Report. Fort Belvoir, VA: Defense Technical Information Center, February 2005. http://dx.doi.org/10.21236/ada429923.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Darbha, Swaroop, Sivakumar Rathinam, and K. R. Rajagopal. Combinatorial Motion Planning Algorithms for a Heterogeneous Collection of Unmanned Vehicles. Fort Belvoir, VA: Defense Technical Information Center, October 2013. http://dx.doi.org/10.21236/ada590747.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Boman, Erik G., Umit V. Catalyurek, Cedric Chevalier, Karen D. Devine, Assefaw H. Gebremedhin, Paul D. Hovland, Alex Pothen, et al. Combinatorial Algorithms to Enable Computational Science and Engineering: Work from the CSCAPES Institute. Office of Scientific and Technical Information (OSTI), January 2015. http://dx.doi.org/10.2172/1167393.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Bennett, Janine Camille, David Minot Day, and Scott A. Mitchell. Summary of the CSRI Workshop on Combinatorial Algebraic Topology (CAT): Software, Applications, & Algorithms. Office of Scientific and Technical Information (OSTI), November 2009. http://dx.doi.org/10.2172/1324989.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Ми пропонуємо знижки на всі преміум-плани для авторів, чиї праці увійшли до тематичних добірок літератури. Зв'яжіться з нами, щоб отримати унікальний промокод!