Log in

Relevant bibliographies by topics / Combinatorial algorithms on string / Journal articles

To see the other types of publications on this topic, follow the link: Combinatorial algorithms on string.

Journal articles on the topic 'Combinatorial algorithms on string'

Author: Grafiati

Published: 11 March 2023

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles 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 journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

Bernardini, Giulia, Huiping Chen, Alessio Conte, et al. "Combinatorial Algorithms for String Sanitization." ACM Transactions on Knowledge Discovery from Data 15, no. 1 (2021): 1–34. http://dx.doi.org/10.1145/3418683.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

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

Full text

Abstract:

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, and other styles

3

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

Full text

Abstract:

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 gr

APA, Harvard, Vancouver, ISO, and other styles

4

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

Full text

Abstract:

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 a

APA, Harvard, Vancouver, ISO, and other styles

5

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

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

Full text

Abstract:

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 t

APA, Harvard, Vancouver, ISO, and other styles

7

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 (2020): 145. http://dx.doi.org/10.3991/ijim.v14i18.16371.

Full text

Abstract:

<p class="0abstract"><strong>Abstract-</strong>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, lo

APA, Harvard, Vancouver, ISO, and other styles

8

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

Full text

Abstract:

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 optimizatio

APA, Harvard, Vancouver, ISO, and other styles

9

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

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

10

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 (2005): 1121–34. http://dx.doi.org/10.1142/s0129054105003698.

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

11

Bensouyad, Meriem, Nousseiba Guidoum, and Djamel-Eddine Saïdouni. "An Efficient Evolutionary Algorithm for Strict Strong Graph Coloring Problem." International Journal of Applied Evolutionary Computation 5, no. 2 (2014): 22–36. http://dx.doi.org/10.4018/ijaec.2014040102.

Full text

Abstract:

A very promising approach for combinatorial optimization is evolutionary algorithms. As an application, this paper deals with the strict strong graph coloring problem defined by Haddad and Kheddouci (2009) where the authors have proposed an exact polynomial time algorithm for trees. The aim of this paper is to introduce a new evolutionary algorithm for solving this problem for general graphs. It combines an original crossover and a powerful correction operator. Experiments of this new approach are carried out on large Dimacs Challenge benchmark graphs. Results show very competitive with and ev

APA, Harvard, Vancouver, ISO, and other styles

12

Alamro, Hayam, Mai Alzamel, Costas S. Iliopoulos, Solon P. Pissis, Wing-Kin Sung, and Steven Watts. "Efficient Identification of k-Closed Strings." International Journal of Foundations of Computer Science 31, no. 05 (2020): 595–610. http://dx.doi.org/10.1142/s0129054120500288.

Full text

Abstract:

A closed string contains a proper factor occurring as both a prefix and a suffix but not elsewhere in the string. Closed strings were introduced by Fici (WORDS 2011) as objects of combinatorial interest. This paper addresses a new problem by extending the closed string problem to the [Formula: see text]-closed string problem, for which a level of approximation is permitted up to a number of Hamming distance errors, set by the parameter [Formula: see text]. We address the problem of deciding whether or not a given string of length [Formula: see text] over an integer alphabet is [Formula: see te

APA, Harvard, Vancouver, ISO, and other styles

13

Alzamel, Mai, Lorraine A. K. Ayad, Giulia Bernardini, et al. "Comparing Degenerate Strings." Fundamenta Informaticae 175, no. 1-4 (2020): 41–58. http://dx.doi.org/10.3233/fi-2020-1947.

Full text

Abstract:

Uncertain sequences are compact representations of sets of similar strings. They highlight common segments by collapsing them, and explicitly represent varying segments by listing all possible options. A generalized degenerate string (GD string) is a type of uncertain sequence. Formally, a GD string Ŝ is a sequence of n sets of strings of total size N, where the ith set contains strings of the same length ki but this length can vary between different sets. We denote by W the sum of these lengths k0, k1, . . . , kn-1. Our main result is an 𝒪(N + M)-time algorithm for deciding whether two GD str

APA, Harvard, Vancouver, ISO, and other styles

14

MOOSA, TANAEEM M., SUMAIYA NAZEEN, M. SOHEL RAHMAN, and REZWANA REAZ. "INFERRING STRINGS FROM COVER ARRAYS." Discrete Mathematics, Algorithms and Applications 05, no. 02 (2013): 1360005. http://dx.doi.org/10.1142/s1793830913600057.

Full text

Abstract:

Covers, being one of the most popular form of regularities in strings, have drawn much attention in the relevant literature. In this paper, we focus on the problem of linear-time inference of strings from cover arrays using the least sized alphabet. We present an algorithm that can reconstruct a string x over a binary alphabet whenever a valid cover array C is given as an input. We have devised our algorithm using several interesting combinatorial properties of cover arrays as well as an interesting relation between border array and cover array. Our algorithm runs in linear-time. The fact that

APA, Harvard, Vancouver, ISO, and other styles

15

Lemström, Kjell, Gonzalo Navarro, and Yoan Pinzon. "Practical algorithms for transposition-invariant string-matching." Journal of Discrete Algorithms 3, no. 2-4 (2005): 267–92. http://dx.doi.org/10.1016/j.jda.2004.08.009.

Full text

APA, Harvard, Vancouver, ISO, and other styles

16

de Andrade, Carlos Eduardo, Rodrigo Franco Toso, Mauricio G. C. Resende, and Flávio Keidi Miyazawa. "Biased Random-Key Genetic Algorithms for the Winner Determination Problem in Combinatorial Auctions." Evolutionary Computation 23, no. 2 (2015): 279–307. http://dx.doi.org/10.1162/evco_a_00138.

Full text

Abstract:

In this paper we address the problem of picking a subset of bids in a general combinatorial auction so as to maximize the overall profit using the first-price model. This winner determination problem assumes that a single bidding round is held to determine both the winners and prices to be paid. We introduce six variants of biased random-key genetic algorithms for this problem. Three of them use a novel initialization technique that makes use of solutions of intermediate linear programming relaxations of an exact mixed integer linear programming model as initial chromosomes of the population.

APA, Harvard, Vancouver, ISO, and other styles

17

Hyyrö, Heikki. "Bit-parallel approximate string matching algorithms with transposition." Journal of Discrete Algorithms 3, no. 2-4 (2005): 215–29. http://dx.doi.org/10.1016/j.jda.2004.08.006.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

BRIMKOV, VALENTIN E. "OPTIMALLY FAST CRCW-PRAM TESTING 2D-ARRAYS FOR EXISTENCE OF REPETITIVE PATTERNS." International Journal of Pattern Recognition and Artificial Intelligence 15, no. 07 (2001): 1167–82. http://dx.doi.org/10.1142/s0218001401001349.

Full text

Abstract:

In classical combinatorial string matching repetitions and other regularities play a central role. Besides their theoretical importance, repetitions in strings have been found relevant to coding and automata theory, formal languages, data compression, and molecular biology. An important motivation for developing a 2D pattern matching theory is seen in its relation with pattern recognition, image processing, computer vision and multimedia. Repetitions in 2D arrays have been defined and classified recently.5 In this paper we present an optimally fast CRCW-PRAM algorithm for testing whether a giv

APA, Harvard, Vancouver, ISO, and other styles

19

Li, Xiu Ying, and Dong Ju Du. "Research on the Application of College Automated Course Scheduling System Based on Genetic Algorithm." Advanced Materials Research 760-762 (September 2013): 1782–85. http://dx.doi.org/10.4028/www.scientific.net/amr.760-762.1782.

Full text

Abstract:

A reasonable curriculum contributes to the improvement of the training and teaching quality of college students. Using computer which is speed and strong ability to arrange curriculum automatically is imperative. Automatically curriculum arrangement is a constrained, multi-objective and intricate combinatorial optimization problem. Based on genetic algorithm of population search, it is suitable to process complex and nonlinear optimization problems which it difficult to solve for traditional search methods. In this paper solves complex automated course scheduling using genetic algorithms.

APA, Harvard, Vancouver, ISO, and other styles

20

Skobtsov, Yu A. "Modern Immunological Models and Their Applications." Herald of the Bauman Moscow State Technical University. Series Instrument Engineering, no. 3 (140) (September 2022): 61–77. http://dx.doi.org/10.18698/0236-3933-2022-3-61-77.

Full text

Abstract:

he paper considers main models and algorithms of artificial immune systems, which are related to the evolutionary computation paradigm and used to search for potential solutions, each of which is represented by an artificial lymphocyte. Same as an individual in evolutionary computation, an artificial lymphocyte is most often encoded by a binary string or a vector of real numbers. As far as the main models of artificial immune systems are concerned, the clonal selection algorithm is close to the evolutionary strategy of evolutionary computing, though it uses more powerful mutation operators and

APA, Harvard, Vancouver, ISO, and other styles

21

ChinnarajiAnnamalai. "Application of Factorial and Binomial Identities in Information, Cybersecurity and Machine Learning." International Journal of Advanced Networking and Applications 14, no. 01 (2022): 5258–60. http://dx.doi.org/10.35444/ijana.2022.14103.

Full text

Abstract:

This paper presents application of the binomial and factorial identities and expansions that are used in artificial intelligence, machine learning, and cybersecurity. The factorial and binomial identities can be used as methodological advances for various algorithms and applications in information and computational science. Cybersecurity is the practice of protecting the computing systems, communication networks, data and programs from cyber-attacks. Its objective is to reduce the risk of cyber-attacks and protect against the unauthorized exploitation of systems and networks. For this purposes

APA, Harvard, Vancouver, ISO, and other styles

22

Adamczyk, Michał, Mai Alzamel, Panagiotis Charalampopoulos, and Jakub Radoszewski. "Palindromic Decompositions with Gaps and Errors." International Journal of Foundations of Computer Science 29, no. 08 (2018): 1311–29. http://dx.doi.org/10.1142/s0129054118430050.

Full text

Abstract:

Identifying palindromes in sequences has been an interesting line of research in combinatorics on words and also in computational biology, after the discovery of the relation of palindromes in the DNA sequence with the HIV virus. Efficient algorithms for the factorization of sequences into palindromes and maximal palindromes have been devised in recent years. We extend these studies by allowing gaps in decompositions and errors in palindromes, and also imposing a lower bound to the length of acceptable palindromes. We first present an on-line algorithm for obtaining a palindromic decomposition

APA, Harvard, Vancouver, ISO, and other styles

23

Badr, Elsayed, I. M. Selim, Hoda Mostafa, and Hala Attiya. "An Integer Linear Programming Model for Partially Ordered Sets." Journal of Mathematics 2022 (September 10, 2022): 1–9. http://dx.doi.org/10.1155/2022/7660174.

Full text

Abstract:

Linear programming is an important approach that is used to represent a large class of combinatorial optimization problems. The simplex algorithm is one of the algorithms for solving linear programming problems with exponential time complexity. Fortunately, this algorithm solves real-world problems with polynomial time complexity. In particular, a new Integer Linear Programming model (ILPM) is proposed for partially ordered sets. Robert Dilworth’s Decomposition theorem is formulated by ILPM and proves its correctness using the paradigm of strong duality in linear programming. Finally, ILPM is

APA, Harvard, Vancouver, ISO, and other styles

24

Simroth, Axel, Denise Holfeld, and Renè Brunsch. "Job Shop Production Planning under Uncertainty: A Monte Carlo Rollout Approach." Environment. Technology. Resources. Proceedings of the International Scientific and Practical Conference 3 (June 16, 2015): 175. http://dx.doi.org/10.17770/etr2015vol3.617.

Full text

Abstract:

<p>The Monte Carlo Rollout method (MCR) is a novel approach to solve combinatorial optimization problems with uncertainties approximatively. It combines ideas from Rollout algorithms for combinatorial optimization and the Monte Carlo Tree Search in game theory. In this paper the results of an investigation of applying the MCR to a Scheduling Problem are shown. The quality of the MCR method depends on the model parameters, search depth and search width, which are strong linked to process parameters. These dependencies are analyzed by different simulations. The paper also deals with the qu

APA, Harvard, Vancouver, ISO, and other styles

25

Dasygenis, Minas, and Kostas Stergiou. "Methods for Parallelizing Constraint Propagation through the Use of Strong Local Consistencies." International Journal on Artificial Intelligence Tools 27, no. 04 (2018): 1860002. http://dx.doi.org/10.1142/s0218213018600023.

Full text

Abstract:

Constraint programming (CP) is a powerful paradigm for various types of hard combinatorial problems. Constraint propagation techniques, such as arc consistency (AC), are used within solvers to prune inconsistent values from the domains of the variables and narrow down the search space. Local consistencies stronger than AC have the potential to prune the search space even more, but they are not widely used because they incur a high run time penalty in cases where they are unsuccessful. All constraint propagation techniques are sequential by nature, and thus they cannot be scaled up to modern mu

APA, Harvard, Vancouver, ISO, and other styles

26

Kim, Yong-Hyuk, Alberto Moraglio, Ahmed Kattan, and Yourim Yoon. "Geometric Generalisation of Surrogate Model-Based Optimisation to Combinatorial and Program Spaces." Mathematical Problems in Engineering 2014 (2014): 1–10. http://dx.doi.org/10.1155/2014/184540.

Full text

Abstract:

Surrogate models (SMs) can profitably be employed, often in conjunction with evolutionary algorithms, in optimisation in which it is expensive to test candidate solutions. The spatial intuition behind SMs makes them naturally suited to continuous problems, and the only combinatorial problems that have been previously addressed are those with solutions that can be encoded as integer vectors. We show how radial basis functions can provide a generalised SM for combinatorial problems which have a geometric solution representation, through the conversion of that representation to a different metric

APA, Harvard, Vancouver, ISO, and other styles

27

Halappanavar, Mahantesh, John Feo, Oreste Villa, Antonino Tumeo, and Alex Pothen. "Approximate weighted matching on emerging manycore and multithreaded architectures." International Journal of High Performance Computing Applications 26, no. 4 (2012): 413–30. http://dx.doi.org/10.1177/1094342012452893.

Full text

Abstract:

Graph matching is a prototypical combinatorial problem with many applications in high-performance scientific computing. Optimal algorithms for computing matchings are challenging to parallelize. Approximation algorithms are amenable to parallelization and are therefore important to compute matchings for large-scale problems. Approximation algorithms also generate nearly optimal solutions that are sufficient for many applications. In this paper we present multithreaded algorithms for computing half-approximate weighted matching on state-of-the-art multicore (Intel Nehalem and AMD Magny-Cours),

APA, Harvard, Vancouver, ISO, and other styles

28

Fotakis, Dimitris, Piotr Krysta, and Carmine Ventre. "The Power of Verification for Greedy Mechanism Design." Journal of Artificial Intelligence Research 62 (July 4, 2018): 459–88. http://dx.doi.org/10.1613/jair.1.11215.

Full text

Abstract:

    Greedy algorithms are known to provide, in polynomial time, near optimal approximation guarantees for Combinatorial Auctions (CAs) with multidimensional bidders. It is known that truthful greedy-like mechanisms for CAs with multi-minded bidders do not achieve good approximation guarantees. In this work, we seek a deeper understanding of greedy mechanism design and investigate under which general assumptions, we can have efficient and truthful greedy mechanisms for CAs. Towards this goal, we use the framework of priority algorithms and weak and strong verificat

APA, Harvard, Vancouver, ISO, and other styles

29

Feldman, A., G. Provan, and A. Van Gemund. "Approximate Model-Based Diagnosis Using Greedy Stochastic Search." Journal of Artificial Intelligence Research 38 (July 27, 2010): 371–413. http://dx.doi.org/10.1613/jair.3025.

Full text

Abstract:

We propose a StochAstic Fault diagnosis AlgoRIthm, called SAFARI, which trades off guarantees of computing minimal diagnoses for computational efficiency. We empirically demonstrate, using the 74XXX and ISCAS-85 suites of benchmark combinatorial circuits, that SAFARI achieves several orders-of-magnitude speedup over two well-known deterministic algorithms, CDA* and HA*, for multiple-fault diagnoses; further, SAFARI can compute a range of multiple-fault diagnoses that CDA* and HA* cannot. We also prove that SAFARI is optimal for a range of propositional fault models, such as the widely-used wea

APA, Harvard, Vancouver, ISO, and other styles

30

Caiafa, Cesar F., and Andrzej Cichocki. "Estimation of Sparse Nonnegative Sources from Noisy Overcomplete Mixtures Using MAP." Neural Computation 21, no. 12 (2009): 3487–518. http://dx.doi.org/10.1162/neco.2009.08-08-846.

Full text

Abstract:

In this letter, we propose a new algorithm for estimating sparse nonnegative sources from a set of noisy linear mixtures. In particular, we consider difficult situations with high noise levels and more sources than sensors (underdetermined case). We show that when sources are very sparse in time and overlapped at some locations, they can be recovered even with very low signal-to-noise ratio, and by using many fewer sensors than sources. A theoretical analysis based on Bayesian estimation tools is included showing strong connections with algorithms in related areas of research such as ICA, NMF,

APA, Harvard, Vancouver, ISO, and other styles

31

Funcke, Lena, Tobias Hartung, Beate Heinemann, et al. "Studying quantum algorithms for particle track reconstruction in the LUXE experiment." Journal of Physics: Conference Series 2438, no. 1 (2023): 012127. http://dx.doi.org/10.1088/1742-6596/2438/1/012127.

Full text

Abstract:

Abstract The LUXE experiment (LASER Und XFEL Experiment) is a new experiment in planning at DESY Hamburg, which will study Quantum Electrodynamics (QED) at the strong-field frontier. In this regime, QED is non-perturbative. This manifests itself in the creation of physical electron-positron pairs from the QED vacuum. LUXE intends to measure the positron production rate in this unprecedented regime by using, among others, a silicon tracking detector. The large number of expected positrons traversing the sensitive detector layers results in an extremely challenging combinatorial problem, which c

APA, Harvard, Vancouver, ISO, and other styles

32

Djurdjev, Mica, Robert Cep, Dejan Lukic, Aco Antic, Branislav Popovic, and Mijodrag Milosevic. "A Genetic Crow Search Algorithm for Optimization of Operation Sequencing in Process Planning." Applied Sciences 11, no. 5 (2021): 1981. http://dx.doi.org/10.3390/app11051981.

Full text

Abstract:

Computer-aided process planning represents the main link between computer-aided design and computer-aided manufacturing. One of the crucial tasks in computer-aided process planning is an operation sequencing problem. In order to find the optimal process plan, operation sequencing problem is formulated as an NP hard combinatorial problem. To solve this problem, a novel genetic crow search approach (GCSA) is proposed in this paper. The traditional CSA is improved by employing genetic strategies such as tournament selection, three-string crossover, shift and resource mutation. Moreover, adaptive

APA, Harvard, Vancouver, ISO, and other styles

33

Wang, Zhaocai, Xiaoguang Bao, and Tunhua Wu. "A Parallel Bioinspired Algorithm for Chinese Postman Problem Based on Molecular Computing." Computational Intelligence and Neuroscience 2021 (January 15, 2021): 1–13. http://dx.doi.org/10.1155/2021/8814947.

Full text

Abstract:

The Chinese postman problem is a classic resource allocation and scheduling problem, which has been widely used in practice. As a classical nondeterministic polynomial problem, finding its efficient algorithm has always been the research direction of scholars. In this paper, a new bioinspired algorithm is proposed to solve the Chinese postman problem based on molecular computation, which has the advantages of high computational efficiency, large storage capacity, and strong parallel computing ability. In the calculation, DNA chain is used to properly represent the vertex, edge, and correspondi

APA, Harvard, Vancouver, ISO, and other styles

34

Tutkun, Nedim, Alessandro Burgio, Michal Jasinski, Zbigniew Leonowicz, and Elzbieta Jasinska. "Intelligent Scheduling of Smart Home Appliances Based on Demand Response Considering the Cost and Peak-to-Average Ratio in Residential Homes." Energies 14, no. 24 (2021): 8510. http://dx.doi.org/10.3390/en14248510.

Full text

Abstract:

With recent developments, smart grids assured for residential customers the opportunity to schedule smart home appliances’ operation times to simultaneously reduce both the electricity bill and the PAR based on demand response, as well as increasing user comfort. It is clear that the multi-objective combinatorial optimization problem involves constraints and the consumer’s preferences, and the solution to the problem is a difficult task. There have been a limited number of investigations carried out so far to solve the indicated problems using metaheuristic techniques like particle swarm optim

APA, Harvard, Vancouver, ISO, and other styles

35

Bansal, Sulabh, and C. Patvardhan. "An Improved Generalized Quantum-Inspired Evolutionary Algorithm for Multiple Knapsack Problem." International Journal of Applied Evolutionary Computation 9, no. 1 (2018): 17–51. http://dx.doi.org/10.4018/ijaec.2018010102.

Full text

Abstract:

This article describes how the 0/1 Multiple Knapsack Problem (MKP), a generalization of popular 0/1 Knapsack Problem, is NP-hard and harder than simple Knapsack Problem. Solution of MKP involves two levels of choice – one for selecting an item to be placed and the other for selecting the knapsack in which it is to be placed. Quantum Inspired Evolutionary Algorithms (QIEAs), a subclass of Evolutionary algorithms, have been shown to be effective in solving difficult problems particularly NP-hard combinatorial optimization problems. QIEAs provide a general framework which needs to be customized a

APA, Harvard, Vancouver, ISO, and other styles

36

Lee, Hyun, and Chunghun Ha. "Sustainable Integrated Process Planning and Scheduling Optimization Using a Genetic Algorithm with an Integrated Chromosome Representation." Sustainability 11, no. 2 (2019): 502. http://dx.doi.org/10.3390/su11020502.

Full text

Abstract:

This paper proposes a genetic algorithm (GA) to find the pseudo-optimum of integrated process planning and scheduling (IPPS) problems. IPPS is a combinatorial optimization problem of the NP-complete class that aims to solve both process planning and scheduling simultaneously. The complexity of IPPS is very high because it reflects various flexibilities and constraints under flexible manufacturing environments. To cope with it, existing metaheuristics for IPPS have excluded some flexibilities and constraints from consideration or have built a complex structured algorithm. Particularly, GAs have

APA, Harvard, Vancouver, ISO, and other styles

37

RAVIKUMAR, BALA. "THE BENFORD-NEWCOMB DISTRIBUTION AND UNAMBIGUOUS CONTEXT-FREE LANGUAGES." International Journal of Foundations of Computer Science 19, no. 03 (2008): 717–27. http://dx.doi.org/10.1142/s0129054108005905.

Full text

Abstract:

For a string w ∈ {0,1, 2,…, d-1}*, let vald(w) denote the integer whose base d representation is the string w and let MSDd(x) denote the most significant or the leading digit of a positive integer x when x is written as a base d integer. Hirvensalo and Karhumäki [9] studied the problem of computing the leading digit in the ternary representation of 2x ans showed that this problem has a polynomial time algorithm. In [16], some applications are presented for the problem of computing the leading digit of AB for given inputs A and B. In this paper, we study this problem from a formal language poin

APA, Harvard, Vancouver, ISO, and other styles

38

Wu, C.-Y., and K.-Y. Tseng. "Stress-based binary differential evolution for topology optimization of structures." Proceedings of the Institution of Mechanical Engineers, Part C: Journal of Mechanical Engineering Science 224, no. 2 (2010): 443–57. http://dx.doi.org/10.1243/09544062jmes1764.

Full text

Abstract:

Differential evolution (DE) is a heuristic optimization method used to solve many optimization problems in real-value search space. It has the advantage of incorporating a relatively simple and efficient form of mutation and crossover. However, the operator of DE is based on floating-point representation only, and is difficult to use in solving combinatorial optimization problems. In this article, a modified binary DE is developed using binary bit-string frameworks with a logical operation binary mutation mechanism. Further, a new stress-based binary mutation mechanism is also proposed to driv

APA, Harvard, Vancouver, ISO, and other styles

39

López, Mario Rossainz, Ivo H. Pineda-Torres, Ivan Olmos Pineda, and José Arturo Olvera López. "Parallel Object Compositions for the Search of Sequences DNA Strings in the Construction of Gnomes." International Journal of Privacy and Health Information Management 7, no. 1 (2019): 18–44. http://dx.doi.org/10.4018/ijphim.2019010102.

Full text

Abstract:

Within an environment of parallel objects, an approach of structured parallel programming and the paradigm of the orientation to objects show a programming method based on high level parallel compositions or HLPCs to solve two problems of combinatorial optimization: grouping fragments of DNA sequences and the parallel exhaustive search (PES) of RNA strings that help the sequence and the assembly of DNAs. The pipeline and farm models are shown as HLPCs under the object orientation paradigm and with them it is proposed the creation of a new HLPCs that combines and uses the previous ones to solve

APA, Harvard, Vancouver, ISO, and other styles

40

Rodriguez-Fernandez, Angel E., Bernardo Gonzalez-Torres, Ricardo Menchaca-Mendez, and Peter F. Stadler. "Clustering Improves the Goemans–Williamson Approximation for the Max-Cut Problem." Computation 8, no. 3 (2020): 75. http://dx.doi.org/10.3390/computation8030075.

Full text

Abstract:

MAX-CUT is one of the well-studied NP-hard combinatorial optimization problems. It can be formulated as an Integer Quadratic Programming problem and admits a simple relaxation obtained by replacing the integer “spin” variables xi by unitary vectors v→i. The Goemans–Williamson rounding algorithm assigns the solution vectors of the relaxed quadratic program to a corresponding integer spin depending on the sign of the scalar product v→i·r→ with a random vector r→. Here, we investigate whether better graph cuts can be obtained by instead using a more sophisticated clustering algorithm. We answer t

APA, Harvard, Vancouver, ISO, and other styles

41

Grigoreva, Natalia S. "3/2-approximation algorithm for a single machine scheduling problem." Vestnik of Saint Petersburg University. Applied Mathematics. Computer Science. Control Processes 17, no. 3 (2021): 240–53. http://dx.doi.org/10.21638/11701/spbu10.2021.302.

Full text

Abstract:

The problem of minimizing the maximum delivery times while scheduling tasks on a single processor is a classical combinatorial optimization problem. Each task ui must be processed without interruption for t(ui) time units on the machine, which can process at most one task at time. Each task uw; has a release time r(ui), when the task is ready for processing, and a delivery time g(ui). Its delivery begins immediately after processing has been completed. The objective is to minimize the time, by which all jobs are delivered. In the Graham notation this problem is denoted by 1|rj,qi|Cmax, it has

APA, Harvard, Vancouver, ISO, and other styles

42

Zhang, Hao, Lihua Dou, Bin Xin, Ruowei Zhang, and Qing Wang. "Reconnaissance and Confirmation Task Planning of Multiple Fixed-Wing UAVs with Specific Payloads: A Comparison Study." Journal of Advanced Computational Intelligence and Intelligent Informatics 26, no. 4 (2022): 570–80. http://dx.doi.org/10.20965/jaciii.2022.p0570.

Full text

Abstract:

In this study, the reconnaissance and confirmation task planning of multiple fixed-wing unmanned aerial vehicles (UAV) with specific payloads, which is an NP-hard problem with strong constraints and mixed variables, is decomposed into two subproblems, task allocation with “payload-target” matching constraints, and fast path planning of the UAV group, for which two mathematical models are respectively established. A bi-layer collaborative solution framework is also proposed. The outer layer optimizes the allocation scheme between the UAVs and targets, whereas the inner layer generates the UAV p

APA, Harvard, Vancouver, ISO, and other styles

43

Torshin, I. Yu, O. A. Gromova, T. R. Grishina, and V. A. Semenov. "The positive and negative effects of using transdermal nonsteroidal anti-inflammatory drugs: chemoreactome analysis." Neurology, Neuropsychiatry, Psychosomatics 12, no. 5 (2020): 123–29. http://dx.doi.org/10.14412/2074-2711-2020-5-123-129.

Full text

Abstract:

Transdermal nonsteroidal anti-inflammatory drugs (NSAIDs) are actively used for mild and moderate pain syndrome, muscle contusions and sprains, sports injuries, and the widest range of musculoskeletal diseases. The transdermal administration of NSAIDs aims to create sufficiently high drug concentrations in the lesion focus, provided that the side effects associated with its systemic action are maximally reduced.Objective: to comparatively simulate the effects of transdermal NSAIDs.Material and methods. Chemoreactome profiling of six NSAIDs (meloxicam, diclofenac, ibuprofen, ketoprofen, nimesul

APA, Harvard, Vancouver, ISO, and other styles

44

Rubio, Fernando, and Ismael Rodríguez. "Water-Based Metaheuristics: How Water Dynamics Can Help Us to Solve NP-Hard Problems." Complexity 2019 (April 2, 2019): 1–13. http://dx.doi.org/10.1155/2019/4034258.

Full text

Abstract:

Many water-based optimization metaheuristics have been introduced during the last decade, both for combinatorial and for continuous optimization. Despite the strong similarities of these methods in terms of their underlying natural metaphors (most of them emulate, in some way or another, how drops collaboratively form paths down to the sea), in general the resulting algorithms are quite different in terms of their searching approach or their solution construction approach. For instance, each entity may represent a solution by itself or, alternatively, entities may construct solutions by modify

APA, Harvard, Vancouver, ISO, and other styles

45

DEVRIENDT, JO, BART BOGAERTS, MAURICE BRUYNOOGHE, and MARC DENECKER. "On local domain symmetry for model expansion." Theory and Practice of Logic Programming 16, no. 5-6 (2016): 636–52. http://dx.doi.org/10.1017/s1471068416000508.

Full text

Abstract:

AbstractSymmetry in combinatorial problems is an extensively studied topic. We continue this research in the context of model expansion problems, with the aim of automating the workflow of detecting and breaking symmetry. We focus onlocal domain symmetry, which is induced by permutations of domain elements, and which can be detected on a first-order level. As such, our work is a continuation of the symmetry exploitation techniques of model generation systems, while it differs from more recent symmetry breaking techniques in answer set programming which detect symmetry on ground programs. Our m

APA, Harvard, Vancouver, ISO, and other styles

46

Farhi, Edward, Jeffrey Goldstone, Sam Gutmann, and Leo Zhou. "The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size." Quantum 6 (July 7, 2022): 759. http://dx.doi.org/10.22331/q-2022-07-07-759.

Full text

Abstract:

The Quantum Approximate Optimization Algorithm (QAOA) is a general-purpose algorithm for combinatorial optimization problems whose performance can only improve with the number of layers p. While QAOA holds promise as an algorithm that can be run on near-term quantum computers, its computational power has not been fully explored. In this work, we study the QAOA applied to the Sherrington-Kirkpatrick (SK) model, which can be understood as energy minimization of n spins with all-to-all random signed couplings. There is a recent classical algorithm by Montanari that, assuming a widely believed con

APA, Harvard, Vancouver, ISO, and other styles

47

Chistikov, Dmitry, Rupak Majumdar, and Philipp Schepper. "Subcubic certificates for CFL reachability." Proceedings of the ACM on Programming Languages 6, POPL (2022): 1–29. http://dx.doi.org/10.1145/3498702.

Full text

Abstract:

Many problems in interprocedural program analysis can be modeled as the context-free language (CFL) reachability problem on graphs and can be solved in cubic time. Despite years of efforts, there are no known truly sub-cubic algorithms for this problem. We study the related certification task: given an instance of CFL reachability, are there small and efficiently checkable certificates for the existence and for the non-existence of a path? We show that, in both scenarios, there exist succinct certificates ( O ( n 2 ) in the size of the problem) and these certificates can be checked in subcubic

APA, Harvard, Vancouver, ISO, and other styles

48

Qian, Chao, Yang Yu, and Zhi-Hua Zhou. "Analyzing Evolutionary Optimization in Noisy Environments." Evolutionary Computation 26, no. 1 (2018): 1–41. http://dx.doi.org/10.1162/evco_a_00170.

Full text

Abstract:

Many optimization tasks must be handled in noisy environments, where the exact evaluation of a solution cannot be obtained, only a noisy one. For optimization of noisy tasks, evolutionary algorithms (EAs), a type of stochastic metaheuristic search algorithm, have been widely and successfully applied. Previous work mainly focuses on the empirical study and design of EAs for optimization under noisy conditions, while the theoretical understandings are largely insufficient. In this study, we first investigate how noisy fitness can affect the running time of EAs. Two kinds of noise-helpful problem

APA, Harvard, Vancouver, ISO, and other styles

49

Sutton, Andrew M., Francisco Chicano, and L. Darrell Whitley. "Fitness Function Distributions over Generalized Search Neighborhoods in the q-ary Hypercube." Evolutionary Computation 21, no. 4 (2013): 561–90. http://dx.doi.org/10.1162/evco_a_00098.

Full text

Abstract:

The frequency distribution of a fitness function over regions of its domain is an important quantity for understanding the behavior of algorithms that employ randomized sampling to search the function. In general, exactly characterizing this distribution is at least as hard as the search problem, since the solutions typically live in the tails of the distribution. However, in some cases it is possible to efficiently retrieve a collection of quantities (called moments) that describe the distribution. In this paper, we consider functions of bounded epistasis that are defined over length-n string

APA, Harvard, Vancouver, ISO, and other styles

50

Koutris, Paraschos, and Shaleen Deep. "The Fine-Grained Complexity of CFL Reachability." Proceedings of the ACM on Programming Languages 7, POPL (2023): 1713–39. http://dx.doi.org/10.1145/3571252.

Full text

Abstract:

Many problems in static program analysis can be modeled as the context-free language (CFL) reachability problem on directed labeled graphs. The CFL reachability problem can be generally solved in time O ( n 3 ), where n is the number of vertices in the graph, with some specific cases that can be solved faster. In this work, we ask the following question: given a specific CFL, what is the exact exponent in the monomial of the running time? In other words, for which cases do we have linear, quadratic or cubic algorithms, and are there problems with intermediate runtimes? This question is inspire

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!