Relevant bibliographies by topics / Randomised algorithm

Contents

  1. Journal articles
  2. Dissertations / Theses
  3. Books
  4. Book chapters
  5. Conference papers
  6. Reports

Academic literature on the topic 'Randomised algorithm'

Author: Grafiati
Published: 4 June 2021
Last updated: 18 February 2022

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

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Randomised algorithm.'

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.

Journal articles on the topic "Randomised algorithm"

1

Petford, A. D., and D. J. A. Welsh. "A randomised 3-colouring algorithm." Discrete Mathematics 74, no. 1-2 (1989): 253–61. http://dx.doi.org/10.1016/0012-365x(89)90214-8.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

GIL, JOSEPH (YOSSI), and YOAV ZIBIN. "Randomised algorithms for isomorphisms of simple types." Mathematical Structures in Computer Science 17, no. 3 (2007): 565–84. http://dx.doi.org/10.1017/s0960129507006068.

Full text
Abstract:
We give the first linear time (randomised) algorithm for the first order isomorphism problem, that is, the isomorphism of non-recursive types involving product- and function-type constructors, under the axioms of commutativity and associativity of products, currying and distributivity of functions over products. This problem can also be thought of as the problem of formal equality-testing of multi-variate expressions involving only multiplications and exponentiation. Previous work gave a deterministic O(n log2n) time and O(n) space algorithm for the problem (n being the input size). Our specific contribution includes two randomised algorithms for the problem: (i)an O(n) time Monte Carlo algorithm (that is, with a small probability it may decide erroneously that the two types are isomorphic), and(ii)an O(n log n) expected time and O(n) space Las Vegas algorithm (that is, with a small probability it may execute long). The algorithms rely on a preprocessing stage, which computes the sequence of the first n primes in O(n log n/log log n) time and space.
APA, Harvard, Vancouver, ISO, and other styles
3

Bera, Debajyoti, and Sapv Tharrmashastha. "Quantum and Randomised Algorithms for Non-linearity Estimation." ACM Transactions on Quantum Computing 2, no. 2 (2021): 1–27. http://dx.doi.org/10.1145/3456509.

Full text
Abstract:
Non-linearity of a Boolean function indicates how far it is from any linear function. Despite there being several strong results about identifying a linear function and distinguishing one from a sufficiently non-linear function, we found a surprising lack of work on computing the non-linearity of a function. The non-linearity is related to the Walsh coefficient with the largest absolute value; however, the naive attempt of picking the maximum after constructing a Walsh spectrum requires Θ (2 n ) queries to an n -bit function. We improve the scenario by designing highly efficient quantum and randomised algorithms to approximate the non-linearity allowing additive error, denoted λ, with query complexities that depend polynomially on λ. We prove lower bounds to show that these are not very far from the optimal ones. The number of queries made by our randomised algorithm is linear in n , already an exponential improvement, and the number of queries made by our quantum algorithm is surprisingly independent of n . Our randomised algorithm uses a Goldreich-Levin style of navigating all Walsh coefficients and our quantum algorithm uses a clever combination of Deutsch-Jozsa, amplitude amplification and amplitude estimation to improve upon the existing quantum versions of the Goldreich-Levin technique.
APA, Harvard, Vancouver, ISO, and other styles
4

Dyer, M., R. Kannan, and L. Stougie. "A simple randomised algorithm for convex optimisation." Mathematical Programming 147, no. 1-2 (2013): 207–29. http://dx.doi.org/10.1007/s10107-013-0718-0.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Fan, Xiying, Chuanhe Huang, Junyu Zhu, and Bin Fu. "Replication-Based Data Dissemination in Connected Internet of Vehicles." Wireless Communications and Mobile Computing 2019 (April 4, 2019): 1–16. http://dx.doi.org/10.1155/2019/2150524.

Full text
Abstract:
Due to the dynamically changing topology of Internet of Vehicles (IoV), it is a challenging issue to achieve efficient data dissemination in IoV. This paper considers strongly connected IoV with a number of heterogenous vehicular nodes to disseminate information and studies distributed replication-based data dissemination algorithms to improve the performance of data dissemination. Accordingly, two data replication algorithms, a deterministic algorithm and a distributed randomised algorithm, are proposed. In the proposed algorithms, the number of message copies spread in the network is limited and the network will be balanced after a series of average operations among the nodes. The number of communication stages needed for network balance shows the complexity of network convergence as well as network convergence speed. It is proved that the network can achieve a balanced status after a finite number of communication stages. Meanwhile, the upper and lower bounds of the time complexity are derived when the distributed randomised algorithm is applied. Detailed mathematical results show that the network can be balanced quickly in complete graph; thus highly efficient data dissemination can be guaranteed in dense IoV. Simulation results present that the proposed randomised algorithm outperforms the present schemes in terms of transmissions and dissemination delay.
APA, Harvard, Vancouver, ISO, and other styles
6

HÖGBERG, JOHANNA. "A randomised inference algorithm for regular tree languages." Natural Language Engineering 17, no. 2 (2011): 203–19. http://dx.doi.org/10.1017/s1351324911000064.

Full text
Abstract:
AbstractWe present a randomised inference algorithm for regular tree languages. The algorithm takes as input two disjoint finite nonempty sets of trees 𝒫 and 𝒩 and outputs a nondeterministic finite tree automaton that accepts every tree in 𝒫 and rejects every tree in 𝒩. The output automaton typically represents a nontrivial generalisation of the examples given in 𝒫 and 𝒩. To obtain compact output automata, we use a heuristics similar to bisimulation minimisation. The algorithm has time complexity of $\ordo{\negsize \cdot \possize^2}$, where n𝒩 and n𝒫 are the size of 𝒩 and 𝒫, respectively. Experiments are conducted on a prototype implementation, and the empirical results appear to second the theoretical results.
APA, Harvard, Vancouver, ISO, and other styles
7

Fränti, P., and J. Kivijärvi. "Randomised Local Search Algorithm for the Clustering Problem." Pattern Analysis & Applications 3, no. 4 (2000): 358–69. http://dx.doi.org/10.1007/s100440070007.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

El Ouali, Mourad, Helena Fohlin, and Anand Srivastav. "A randomised approximation algorithm for the hitting set problem." Theoretical Computer Science 555 (October 2014): 23–34. http://dx.doi.org/10.1016/j.tcs.2014.03.029.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Annan, J. D. "A Randomised Approximation Algorithm for Counting the Number of Forests in Dense Graphs." Combinatorics, Probability and Computing 3, no. 3 (1994): 273–83. http://dx.doi.org/10.1017/s0963548300001188.

Full text
Abstract:
A polynomial-time randomised algorithm for uniformly generating forests in a dense graph is presented. Using this, a fully polynomial randomised approximation scheme (fpras) for counting the number of forests in a dense graph is created.
APA, Harvard, Vancouver, ISO, and other styles
10

Cheyne, H., V. Hundley, D. Dowding, et al. "Effects of algorithm for diagnosis of active labour: cluster randomised trial." BMJ 337, dec08 2 (2008): a2396. http://dx.doi.org/10.1136/bmj.a2396.

Full text
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Randomised algorithm"

1

Fontaine, Allyx. "Analyses et preuves formelles d'algorithmes distribués probabilistes." Thesis, Bordeaux, 2014. http://www.theses.fr/2014BORD0091/document.

Full text
Abstract:
L’intérêt porté aux algorithmes probabilistes est, entre autres,dû à leur simplicité. Cependant, leur analyse peut devenir très complexeet ce particulièrement dans le domaine du distribué. Nous mettons en évidencedes algorithmes, optimaux en terme de complexité en bits résolvantles problèmes du MIS et du couplage maximal dans les anneaux, qui suiventle même schéma. Nous élaborons une méthode qui unifie les résultatsde bornes inférieures pour la complexité en bits pour les problèmes duMIS, du couplage maximal et de la coloration. La complexité de ces analysespouvant facilement mener à l’erreur et l’existence de nombreux modèlesdépendant d’hypothèses implicites nous ont motivés à modéliserde façon formelle les algorithmes distribués probabilistes correspondant ànotre modèle (par passage de messages, anonyme et synchrone), en vuede prouver formellement des propriétés relatives à leur analyse. Pour cela,nous développons une bibliothèque, RDA, basée sur l’assistant de preuveCoq<br>Probabilistic algorithms are simple to formulate. However, theiranalysis can become very complex, especially in the field of distributedcomputing. We present algorithms - optimal in terms of bit complexityand solving the problems of MIS and maximal matching in rings - that followthe same scheme.We develop a method that unifies the bit complexitylower bound results to solve MIS, maximal matching and coloration problems.The complexity of these analyses, which can easily lead to errors,together with the existence of many models depending on implicit assumptionsmotivated us to formally model the probabilistic distributed algorithmscorresponding to our model (message passing, anonymous andsynchronous). Our aim is to formally prove the properties related to theiranalysis. For this purpose, we develop a library, called RDA, based on theCoq proof assistant
APA, Harvard, Vancouver, ISO, and other styles
2

Schmitt, Jochen, Michael Meurer, Uta Schwanebeck, Xina Grählert, and Knut Schäkel. "Treatment Following an Evidence-Based Algorithm versus Individualised Symptom-Oriented Treatment for Atopic Eczema: A Randomised Controlled Trial." Karger, 2008. https://tud.qucosa.de/id/qucosa%3A27651.

Full text
Abstract:
Background: Evidence-based treatment algorithms, successfully established for asthma, are missing for atopic eczema (AE). Objectives: To investigate whether treatment according to an evidence-based algorithm is an effective and applicable concept for the management of AE. Methods: Based on a systematic literature review, we developed an evidence-based severity-score-oriented treatment algorithm for AE and compared its effectiveness to that of an individualised symptom-oriented treatment (individual therapy) in a randomised controlled trial. Sixty-three participants were randomised to algorithm (n = 32) or individual therapy (n = 31) and treated accordingly for 12 months. Study end points included difference between baseline SCORAD and mean SCORAD under treatment (primary end point), quality of life and treatment utilisation. Analysis was by intention to treat (registration: ClinicalTrials.gov:NCT00148746). Results: No statistically significant differences in clinical or subjective response were observed between groups. Treatment following the algorithm and individual treatment both effectively controlled AE. Mean SCORAD reductions were 47% (95% confidence interval, CI = 38–55; algorithm) and 42% (95% CI = 29–54; individual). Clinical response was paralleled by improved quality of life in both groups. Physicians adhered to the algorithm option in 93% of their treatment decisions. Conclusion: Treatment following an evidence-based algorithm is an effective and applicable concept for the management of AE but does not show clear advantages compared to individualised treatment in a dermatological setting.<br>Dieser Beitrag ist mit Zustimmung des Rechteinhabers aufgrund einer (DFG-geförderten) Allianz- bzw. Nationallizenz frei zugänglich.
APA, Harvard, Vancouver, ISO, and other styles
3

Cheyne, Helen L. "The development and testing of an algorithm to support midwives’ diagnosis of active labour in primiparous women." Thesis, University of Stirling, 2008. http://hdl.handle.net/1893/494.

Full text
Abstract:
The research in this thesis aimed to develop an algorithm to support midwives’ diagnosis of active labour in primiparous women and to compare the effectiveness of the algorithm with standard care in terms of maternal and neonatal outcomes. Four linked studies are presented following the template suggested by the Medical Research Council (MRC 2000) Framework for development and evaluation of randomised controlled trials (RCT) for complex interventions to improve health. Study one Aim: To develop an algorithm for diagnosis of active labour in primiparous women. Methods: An informal telephone survey was conducted with senior midwives to assess the need for a decision support tool for the diagnosis of active labour. A literature review identified the key cues for inclusion in the algorithm which was then drafted. Focus group interviews were conducted with midwives to ascertain the cues used by midwives in diagnosing active labour. Findings: Thirteen midwives took part in focus groups. They described using informational cues which could be separated into two categories: those arising from the woman (Physical signs, Distress and coping, Woman's expectations and Social factors) and those from the institution (Midwifery care, Organisational factors and Justifying actions). Study Two Aim: Preliminary testing of the algorithm Methods: Vignettes and questionnaires were used to test the consistency of midwives’ judgements (inter-rater reliability), the content of the algorithm and its acceptability to midwives (face and content validity). The study was conducted in two stages: the first stage (23 midwives) involved vignettes and questionnaires and the second stage (20 midwives) involved vignettes only. Findings: In the first stage a Kappa score of 0.45 indicated only moderate agreement between midwives using the algorithm. After modifying the algorithm, the Kappa score in stage two was 0.86, indicating a high level of agreement. While the majority of the midwives reported that the algorithm was easy to complete, most were able to identify snags or make suggestions for its improvement. Based on the findings of this study the algorithm was modified and the final version was developed. Study three Aim: To assess the feasibility of carrying out a cluster randomised trial (CRT) of the algorithm, in Scotland. Specifically, to identify maternity units potentially willing to participate in a CRT, to test the implementation strategy for the trial and to collect baseline data to inform the sample size calculation. Methods: A questionnaire and interviews were used. The CRT methods were piloted in two maternity units and the algorithm was used for a three-month period in order to test its acceptability and provide estimates of compliance and consent rates. Results: All maternity units surveyed expressed an interest in the proposed study. Midwives’ compliance with study protocol differed between units, although the consent rate of women was high (89% and 84%). Ultimately, one unit achieved 100% of the required sample and the other 60%. The midwives reported that the algorithm was acceptable and was a useful tool, particularly for teaching inexperienced midwives. Study four Aim: To compare the effectiveness of the algorithm for diagnosis of active labour in primiparous women with standard care in terms of maternal and neonatal outcomes. Method: A cluster randomised trial Participants: Fourteen maternity units in Scotland. Midwives in experimental sites used the algorithm to assist their diagnosis of active labour. Seven experimental units collected data from 1029 women at baseline and 896 post intervention. The seven control units had 1291 women at baseline and 1287 after study implementation. Outcomes: The primary outcome was the percentage use of oxytocin for augmentation of labour. Secondary outcomes were medical interventions in labour, labour admission management, unplanned out of hospital births and clinical outcomes for mothers and babies. Results: There was no significant difference between groups in percentage use of oxytocin for augmentation of labour or for the use of medical interventions in labour. Women in the algorithm group were more likely to be discharged from the labour suite following their first labour assessment and subsequently have more pre-labour admissions. Conclusion The studies presented in this thesis represent the full process of developing and testing a complex healthcare intervention (the algorithm). The final study, a national cluster randomised trial, demonstrated that the use of the algorithm did not result in a reduction in the number of women who received oxytocin for augmentation or the use of medical interventions in labour. The results suggest that misdiagnosis of labour is not the main reason for higher rates of intervention experienced by women admitted to labour wards while not yet in active labour. These studies contribute significantly to the debate on care of women in early labour, the organisation of maternity care and to maternity care research.
APA, Harvard, Vancouver, ISO, and other styles
4

Vu, Khac Ky. "Random projection for high-dimensional optimization." Thesis, Université Paris-Saclay (ComUE), 2016. http://www.theses.fr/2016SACLX031/document.

Full text
Abstract:
À l'ère de la numérisation, les données devient pas cher et facile à obtenir. Cela se traduit par de nombreux nouveaux problèmes d'optimisation avec de très grandes tailles. En particulier, pour le même genre de problèmes, le nombre de variables et de contraintes sont énormes. En outre, dans de nombreux paramètres d'application tels que ceux dans l'apprentissage de la machine, une solution précise est moins préférée que celles approximatives mais robustes. Il est un véritable défi pour les algorithmes traditionnels, qui sont utilisés pour bien travailler avec des problèmes de taille moyenne, pour faire face à ces nouvelles circonstances.Au lieu de développer des algorithmes qui évoluent bien à résoudre ces problèmes directement, une idée naturelle est de les transformer en problèmes de petite taille qui se rapporte fortement aux originaux. Étant donné que les nouvelles sont de tailles gérables, ils peuvent encore être résolus efficacement par des méthodes classiques. Les solutions obtenues par ces nouveaux problèmes, cependant, nous donner un aperçu des problèmes originaux. Dans cette thèse, nous allons exploiter l'idée ci-dessus pour résoudre certains problèmes de grande dimension optimisation. En particulier, nous appliquons une technique spéciale appelée projection aléatoire pour intégrer les données du problème dans les espaces de faible dimension, et de reformuler environ le problème de telle manière qu'il devient très facile à résoudre, mais capte toujours l'information la plus importante.Dans le chapitre 3, nous étudions les problèmes d'optimisation dans leurs formes de faisabilité. En particulier, nous étudions le problème que l'on appelle l'adhésion linéaire restreint. Cette classe contient de nombreux problèmes importants tels que la faisabilité linéaire et entier. Nous proposonsd'appliquer une projection aléatoire aux contraintes linéaires etnous voulons trouver des conditions sur T, de sorte que les deux problèmes de faisabilité sont équivalentes avec une forte probabilité.Dans le chapitre 4, nous continuons à étudier le problème ci-dessus dans le cas où l'ensemble restreint est un ensemble convexe. Nous établissons les relations entre les problèmes originaux et projetés sur la base du concept de la largeur gaussienne, qui est populaire dans la détection comprimé. En particulier, nous montrons que les deux problèmes sont équivalents avec une forte probabilité aussi longtemps que pour une projection aléatoire échantillonné à partir ensemble sous-gaussienne avec grande dimension suffisante (dépend de la largeur gaussienne).Dans le chapitre 5, nous étudions le problème de l'adhésion euclidienne:.. `` Étant donné un vecteur b et un euclidienne ensemble fermé X, décider si b est en Xor pas "Ceci est une généralisation du problème de l'appartenance linéaire restreinte précédemment considéré. Nous employons une gaussienne projection aléatoire T pour l'intégrer à la fois b et X dans un espace de dimension inférieure et étudier la version projetée correspondant. Lorsque X est fini ou dénombrable, en utilisant un argument simple, nous montrons que les deux problèmes sont équivalents presque sûrement quelle que soit la dimension projetée. Dans le cas où X peut être indénombrable, nous prouvons que les problèmes initiaux et prévus sont également équivalentes si la dimension d projetée est proportionnelle à une dimension intrinsèque de l'ensemble X. En particulier, nous employons la définition de doubler la dimension estimer la relation entre les deux problèmes.Dans le chapitre 6, nous proposons d'appliquer des projections aléatoires pour la zone de confiance sous-problème. Nous réduisons le nombre de variables en utilisant une projection aléatoire et prouver que des solutions optimales pour le nouveau problème sont en fait des solutions approchées de l'original. Ce résultat peut être utilisé dans le cadre de confiance-région pour étudier l'optimisation de boîte noire et l'optimisation des produits dérivés libre<br>In the digitization age, data becomes cheap and easy to obtain. That results in many new optimization problems with extremely large sizes. In particular, for the same kind of problems, the numbers of variables and constraints are huge. Moreover, in many application settings such as those in Machine learning, an accurate solution is less preferred as approximate but robust ones. It is a real challenge for traditional algorithms, which are used to work well with average-size problems, to deal with these new circumstances.Instead of developing algorithms that scale up well to solve these problems directly, one natural idea is to transform them into small-size problems that strongly relates to the originals. Since the new ones are of manageable sizes, they can still be solved efficiently by classical methods. The solutions obtained by these new problems, however, will provide us insight into the original problems. In this thesis, we will exploit the above idea to solve some high-dimensional optimization problems. In particular, we apply a special technique called random projection to embed the problem data into low dimensional spaces, and approximately reformulate the problem in such a way that it becomes very easy to solve but still captures the most important information. Therefore, by solving the projected problem, we either obtain an approximate solution or an approximate objective value for the original problem.We will apply random projection to study a number of important optimization problems, including linear and integer programming (Chapter 3), convex optimization with linear constraints (Chapter 4), membership and approximate nearest neighbor (Chapter 5) and trust-region subproblems (Chapter 6).In Chapter 3, we study optimization problems in their feasibility forms. In particular, we study the so-called restricted linear membership problem. This class contains many important problems such as linear and integer feasibility. We proposeto apply a random projection to the linear constraints, andwe want to find conditions on T, so that the two feasibility problems are equivalent with high probability.In Chapter 4, we continue to study the above problem in the case the restricted set is a convex set. Under that assumption, we can define a tangent cone at some point with minimal squared error. We establish the relations between the original and projected problems based on the concept of Gaussian width, which is popular in compressed sensing. In particular, we prove thatthe two problems are equivalent with high probability as long as for some random projection sampled from sub-gaussian ensemble with large enough dimension (depends on the gaussian width).In Chapter 5, we study the Euclidean membership problem: ``Given a vector b and a Euclidean closed set X, decide whether b is in Xor not". This is a generalization of the restricted linear membership problem considered previously. We employ a Gaussian random projection T to embed both b and X into a lower dimension space and study the corresponding projected version: ``Decide whether Tb is in T(X) or not". When X is finite or countable, using a straightforward argument, we prove that the two problems are equivalent almost surely regardless the projected dimension. In the case when X may be uncountable, we prove that the original and projected problems are also equivalent if the projected dimension d is proportional to some intrinsic dimension of the set X. In particular, we employ the definition of doubling dimension estimate the relation between the two problems.In Chapter 6, we propose to apply random projections for the trust-region subproblem. We reduce the number of variables by using a random projection and prove that optimal solutions for the new problem are actually approximate solutions of the original. This result can be used in the trust-region framework to study black-box optimization and derivative-free optimization
APA, Harvard, Vancouver, ISO, and other styles
5

Meshkinfamfard, Sepehr. "Randomised algorithms on networks." Thesis, Durham University, 2016. http://etheses.dur.ac.uk/11476/.

Full text
Abstract:
Networks form an indispensable part of our lives. In particular, computer networks have ranked amongst the most influential networks in recent times. In such an ever-evolving and fast growing network, the primary concern is to understand and analyse different aspects of the network behaviour, such as the quality of service and efficient information propagation. It is also desirable to predict the behaviour of a large computer network if, for example, one of the computers is infected by a virus. In all of the aforementioned cases, we need protocols that are able to make local decisions and handle the dynamic changes in the network topology. Here, randomised algorithms are preferred because many deterministic algorithms often require a central control. In this thesis, we investigate three network-based randomised algorithms, threshold load balancing with weighted tasks, the pull-Moran process and the coalescing-branching random walk. Each of these algorithms has extensive applicability within networks and computational complexity within computer science. In this thesis we investigate threshold-based load balancing protocols. We introduce a generalisation of protocols in [2, 3] to weighted tasks. This thesis also analyses an evolutionary-based process called the death-birth update, defined here as the Pull-Moran process. We show that a class of strong universal amplifiers does not exist for the Pull-Moran process. We show that any class of selective amplifiers in the (standard) Moran process is a class of selective suppressors under the Pull-Moran process. We then introduce a class of selective amplifiers called Punk graphs. Finally, we improve the broadcasting time of the coalescing-branching (COBRA) walk analysed in [4], for random regular graphs. Here, we look into the COBRA approach as a randomised rumour spreading protocol.
APA, Harvard, Vancouver, ISO, and other styles
6

Contreras, Felipe. "A uniform randomized routing algorithm." Thesis, University of Ottawa (Canada), 2002. http://hdl.handle.net/10393/6222.

Full text
Abstract:
Given a set of routes between pairs of sites over a communication network, the traffic load of a link measures the number of routes using it. We analyze traffic load for some randomized local routing algorithms, some of which assume geometric information on the network. We also propose a uniform randomized routing algorithm generating uniform distributed routes between a pair of sites where only source, destination and current neighbor information are available.
APA, Harvard, Vancouver, ISO, and other styles
7

Brugaletta, Luca. "Randomized configuration for Algorithm Selector SUNNY." Bachelor's thesis, Alma Mater Studiorum - Università di Bologna, 2019. http://amslaurea.unibo.it/17573/.

Full text
Abstract:
In questa tesi abbiamo analizzato i comportamenti dell'algoritmo Sunny andando a modificare il metodo di scelta delle feature, principalmente passando da un approccio sequenziale ad uno casuale. Abbiamo implementato e confrontato 3 tecniche oltre a quella di partenza: -randk: sfrutta un approccio puramente casuale per il calcolo delle n feature e della k. -simann: sfrutta la tecnica di ottimizzazione di simulated annealing per calcolare le n feature e il valore di k. -simann-mod: come simann, ma utilizza parametri diversi per il calcolo. All'interno di questa tesi troviamo i risultati dell'esperimento e i vantaggi che si possono avere nell'utilizzo di una tecnica che non visita tutte le possibili soluzioni, ma solamente un numero ridotto di esse.
APA, Harvard, Vancouver, ISO, and other styles
8

Andersson, Gunnar. "Some new randomized approximation algorithms." Doctoral thesis, KTH, Numerical Analysis and Computer Science, NADA, 2000. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-2971.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Wastell, Christopher Michael. "Communication patterns for randomized algorithms." Thesis, Durham University, 2018. http://etheses.dur.ac.uk/12525/.

Full text
Abstract:
Examples of large scale networks include the Internet, peer-to-peer networks, parallel computing systems, cloud computing systems, sensor networks, and social networks. Efficient dissemination of information in large networks such as these is a funda- mental problem. In many scenarios the gathering of information by a centralised controller can be impractical. When designing and analysing distributed algorithms we must consider the limitations imposed by the heterogeneity of devices in the networks. Devices may have limited computational ability or space. This makes randomised algorithms attractive solutions. Randomised algorithms can often be simpler and easier to implement than their deterministic counterparts. This thesis analyses the effect of communication patterns on the performance of distributed randomised algorithms. We study randomized algorithms with application to three different areas. Firstly, we study a generalization of the balls-into-bins game. Balls into bins games have been used to analyse randomised load balancing. Under the Greedy[d] allocation scheme each ball queries the load of d random bins and is then allocated to the least loaded of them. We consider an infinite, parallel setting where expectedly λn balls are allocated in parallel according to the Greedy[d] allocation scheme in to n bins and subsequently each non-empty bin removes a ball. Our results show that for d = 1,2, the Greedy[d] allocation scheme is self-stabilizing and that in any round the maximum system load for high arrival rates is exponentially smaller for d = 2 compared to d = 1 (w.h.p). Secondly, we introduce protocols that solve the plurality consensus problem on arbitrary graphs for arbitrarily small bias. Typically, protocols depend heavily on the employed communication mechanism. Our protocols are based on an interest- ing relationship between plurality consensus and distributed load balancing. This relationship allows us to design protocols that are both time and space efficient and generalize the state of the art for a large range of problem parameters. Finally, we investigate the effect of restricting the communication of the classical PULL algorithm for randomised rumour spreading. Rumour spreading (broadcast) is a fundamental task in distributed computing. Under the classical PULL algo- rithm, a node with the rumour that receives multiple requests is able to respond to all of them in a given round. Our model restricts nodes such that they can re- spond to at most one request per round. Our results show that the restricted PULL algorithm is optimal for several graph classes such as complete graphs, expanders, random graphs and several Cayley graphs.
APA, Harvard, Vancouver, ISO, and other styles
10

Vaikuntanathan, Vinod. "Randomized algorithms for reliable broadcast." Thesis, Massachusetts Institute of Technology, 2009. http://hdl.handle.net/1721.1/47746.

Full text
Abstract:
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2009.<br>Includes bibliographical references (p. 82-85).<br>In this thesis, we design randomized algorithms for classical problems in fault tolerant distributed computing in the full-information model. The full-information model is a strong adversarial model which imposes no restrictions on the computational power of the faulty players nor on the information available to them. Namely, the faulty players are infinitely powerful and are privy to all the communications in the network. Our main result is the construction of two efficient randomized protocols for Byzantine agreement, a classical problem in distributed computing. Byzantine agreement is the problem of simulating the reliable broadcast functionality in a network where all communication is person-to-person. We design two randomized Byzantine agreement protocols in a synchronous network with an expected round-complexity of O(log n) rounds. One of the protocols is resilient against an all-powerful, full-information adversary that corrupts less than a third of the number of players (whereas the other protocol is resilient against a fourth fraction of corruptions). Our protocols have the following additional features. * The fault-tolerance of our protocols can be increased to less a half fraction of faults, if there is a public-key infrastructure setup available that allows the players to compute (public-key) digital signatures. * Our protocols work even if the source of randomness is a "somewhat random" source (also called a Santha-Vazirani source). The price we pay is a decreased fault-tolerance. Our second result is the design of a compiler that transforms a randomized distributed protocol that tolerates benign, fail-stop faults into a protocol that tolerates malicious, Byzantine faults. Fail-stop faults follow the protocol specification, but may stop in the middle of the execution. On the other hand, Byzantine faults are arbitrarily malicious.<br>(cont.) The resulting protocol has almost the same fault-tolerance and efficiency as the original protocol. Our compiler suggests a modular way to design distributed protocols: first, design a protocol that tolerates fail-stop faults, and use our compiler to "boost" the fault-tolerance to Byzantine faults. The design of the compiler is based on a new protocol technique that we develop, called "auditing" of distributed protocols.<br>by Vinod Vaikuntanathan.<br>Ph.D.
APA, Harvard, Vancouver, ISO, and other styles
More sources

Books on the topic "Randomised algorithm"

1

Prabhakar, Raghavan, ed. Randomized algorithms. Cambridge University Press, 1995.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
2

Bubley, Russ. Randomized Algorithms: Approximation, Generation and Counting. Springer London, 2001.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
3

Bubley, Russ. Randomized Algorithms: Approximation, Generation and Counting. Springer London, 2001. http://dx.doi.org/10.1007/978-1-4471-0695-1.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

HromkoviČ, Juraj. Design and Analysis of Randomized Algorithms. Springer Berlin Heidelberg, 2005. http://dx.doi.org/10.1007/3-540-27903-2.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Clarkson, Kenneth L. Randomized parallel algorithms for trapezoidal diagrams. Courant Institute of Mathematical Sciences, New York University, 1991.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
6

Towards dynamic randomized algorithms in computational geometry. Springer-Verlag, 1993.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
7

Computational geometry: An introduction through randomized algorithms. Prentice-Hall, 1994.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
8

Teillaud, Monique. Towards Dynamic Randomized Algorithms in Computational Geometry. Springer Berlin Heidelberg, 1993. http://dx.doi.org/10.1007/3-540-57503-0.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Garefalakis, Theodoulos. A family of randomized algorithms for list accessing. University of Toronto, Dept. of Computer Science, 1997.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
10

Granichin, Oleg, Zeev Volkovich, and Dvora Toledano-Kitai. Randomized Algorithms in Automatic Control and Data Mining. Springer Berlin Heidelberg, 2015. http://dx.doi.org/10.1007/978-3-642-54786-7.

Full text
APA, Harvard, Vancouver, ISO, and other styles
More sources

Book chapters on the topic "Randomised algorithm"

1

El Ouali, Mourad, Helena Fohlin, and Anand Srivastav. "A Randomised Approximation Algorithm for the Hitting Set Problem." In WALCOM: Algorithms and Computation. Springer Berlin Heidelberg, 2013. http://dx.doi.org/10.1007/978-3-642-36065-7_11.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

El Ouali, Mourad, Helena Fohlin, and Anand Srivastav. "A Randomised Approximation Algorithm for the Partial Vertex Cover Problem in Hypergraphs." In Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2012. http://dx.doi.org/10.1007/978-3-642-34862-4_13.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Métivier, Yves, John Michael Robson, Nasser Saheb-Djahromi, and Akka Zemmari. "Brief Annoucement: Analysis of an Optimal Bit Complexity Randomised Distributed Vertex Colouring Algorithm." In Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2009. http://dx.doi.org/10.1007/978-3-642-10877-8_28.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Hromkovič, Juraj. "Randomized Algorithms." In Texts in Theoretical Computer Science. An EATCS Series. Springer Berlin Heidelberg, 2004. http://dx.doi.org/10.1007/978-3-662-05269-3_5.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Hromkovič, Juraj. "Randomized Algorithms." In Texts in Theoretical Computer Science An EATCS Series. Springer Berlin Heidelberg, 2001. http://dx.doi.org/10.1007/978-3-662-04616-6_5.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Jukna, Stasys. "Randomized Algorithms." In Texts in Theoretical Computer Science. An EATCS Series. Springer Berlin Heidelberg, 2001. http://dx.doi.org/10.1007/978-3-662-04650-0_27.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Uehara, Ryuhei. "Randomized Algorithms." In First Course in Algorithms Through Puzzles. Springer Singapore, 2018. http://dx.doi.org/10.1007/978-981-13-3188-6_6.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Che, Maolin, and Yimin Wei. "Randomized Algorithms." In Theory and Computation of Complex Tensors and its Applications. Springer Singapore, 2020. http://dx.doi.org/10.1007/978-981-15-2059-4_8.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Alippi, Cesare. "Randomized Algorithms." In Intelligence for Embedded Systems. Springer International Publishing, 2014. http://dx.doi.org/10.1007/978-3-319-05278-6_4.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Rajaraman, Rajmohan. "Randomized Rounding." In Encyclopedia of Algorithms. Springer US, 2008. http://dx.doi.org/10.1007/978-0-387-30162-4_327.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Randomised algorithm"

1

Onose, Alexandru, Rafael E. Carrillo, Jason D. McEwen, and Yves Wiaux. "A randomised primal-dual algorithm for distributed radio-interferometric imaging." In 2016 24th European Signal Processing Conference (EUSIPCO). IEEE, 2016. http://dx.doi.org/10.1109/eusipco.2016.7760488.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Gupta, Anchit, and Shivaram Kalyanakrishnan. "Improved Strong Worst-case Upper Bounds for MDP Planning." In Twenty-Sixth International Joint Conference on Artificial Intelligence. International Joint Conferences on Artificial Intelligence Organization, 2017. http://dx.doi.org/10.24963/ijcai.2017/248.

Full text
Abstract:
The Markov Decision Problem (MDP) plays a central role in AI as an abstraction of sequential decision making. We contribute to the theoretical analysis of MDP PLANNING, which is the problem of computing an optimal policy for a given MDP. Specifically, we furnish improved STRONG WORST-CASE upper bounds on the running time of MDP planning. Strong bounds are those that depend only on the number of states n and the number of actions k in the specified MDP; they have no dependence on affiliated variables such as the discount factor and the number of bits needed to represent the MDP. Worst-case bounds apply to EVERY run of an algorithm; randomised algorithms can typically yield faster EXPECTED running times. While the special case of 2-action MDPs (that is, k = 2) has recently received some attention, bounds for general k have remained to be improved for several decades. Our contributions are to this general case. For k &gt;= 3, the tightest strong upper bound shown to date for MDP planning belongs to a family of algorithms called Policy Iteration. This bound is only a polynomial improvement over a trivial bound of poly(n, k) k^{n} [Mansour and Singh, 1999]. In this paper, we generalise a contrasting algorithm called the Fibonacci Seesaw, and derive a bound of poly(n, k) k^{0.6834n}. The key construct we use is a template to map algorithms for the 2-action setting to the general setting. Interestingly, this idea can also be used to design Policy Iteration algorithms with a running time upper bound of poly(n, k) k^{0.7207n}. Both our results improve upon bounds that have stood for several decades.
APA, Harvard, Vancouver, ISO, and other styles
3

Selmair, Maximilian, Sascha Hamzehi, and Klaus-Juergen Meier. "Evaluation Of Algorithm Performance For Simulated Square And Non-Square Logistic Assignment Problems." In 35th ECMS International Conference on Modelling and Simulation. ECMS, 2021. http://dx.doi.org/10.7148/2021-0016.

Full text
Abstract:
The optimal allocation of transportation tasks to a fleet of vehicles, especially for large-scale systems of more than 20 Autonomous Mobile Robots (AMRs), remains a major challenge in logistics. Optimal in this context refers to two criteria: how close a result is to the best achievable objective value and the shortest possible computational time. Operations research has provided different methods that can be applied to solve this assignment problem. Our literature review has revealed six commonly applied methods to solve this problem. In this paper, we compared three optimal methods (Integer Linear Programming, Hungarian Method and the Jonker Volgenant Castanon algorithm) to three three heuristic methods (Greedy Search algorithm, Vogel’s Approximation Method and Vogel’s Approximation Method for non-quadratic Matrices). The latter group generally yield results faster, but were not developed to provide optimal results in terms of the optimal objective value. Every method was applied to 20.000 randomised samples of matrices, which differed in scale and configuration, in simulation experiments in order to determine the results’ proximity to the optimal solution as well as their computational time. The simulation results demonstrate that all methods vary in their time needed to solve the assignment problem scenarios as well as in the respective quality of the solution. Based on these results yielded by computing quadratic and non-quadratic matrices of different scales, we have concluded that the Jonker Volgenant Castanon algorithm is deemed to be the best method for solving quadratic and non-quadratic assignment problems with optimal precision. However, if performance in terms of computational time is prioritised for large non-quadratic matrices (50×300 and larger), the Vogel’s Approximation Method for non-quadratic Matrices generates faster approximated solutions.
APA, Harvard, Vancouver, ISO, and other styles
4

Abboud, Ralph, İsmail İlkan Ceylan, and Radoslav Dimitrov. "On the Approximability of Weighted Model Integration on DNF Structures." In 17th International Conference on Principles of Knowledge Representation and Reasoning {KR-2020}. International Joint Conferences on Artificial Intelligence Organization, 2020. http://dx.doi.org/10.24963/kr.2020/85.

Full text
Abstract:
Weighted model counting (WMC) consists of computing the weighted sum of all satisfying assignments of a propositional formula. WMC is well-known to be #P-hard for exact solving, but admits a fully polynomial randomised approximation scheme (FPRAS) when restricted to DNF structures. In this work, we study weighted model integration, a generalization of weighted model counting which involves real variables in addition to propositional variables, and pose the following question: Does weighted model integration on DNF structures admit an FPRAS? Building on classical results from approximate volume computation and approximate weighted model counting, we show that weighted model integration on DNF structures can indeed be approximated for a class of weight functions. Our approximation algorithm is based on three subroutines, each of which can be a weak (i.e., approximate), or a strong (i.e., exact) oracle, and in all cases, comes along with accuracy guarantees. We experimentally verify our approach over randomly generated DNF instances of varying sizes, and show that our algorithm scales to large problem instances, involving up to 1K variables, which are currently out of reach for existing, general-purpose weighted model integration solvers.
APA, Harvard, Vancouver, ISO, and other styles
5

Eggensperger, Katharina, Marius Lindauer, and Frank Hutter. "Neural Networks for Predicting Algorithm Runtime Distributions." In Twenty-Seventh International Joint Conference on Artificial Intelligence {IJCAI-18}. International Joint Conferences on Artificial Intelligence Organization, 2018. http://dx.doi.org/10.24963/ijcai.2018/200.

Full text
Abstract:
Many state-of-the-art algorithms for solving hard combinatorial problems in artificial intelligence (AI) include elements of stochasticity that lead to high variations in runtime, even for a fixed problem instance. Knowledge about the resulting runtime distributions (RTDs) of algorithms on given problem instances can be exploited in various meta-algorithmic procedures, such as algorithm selection, portfolios, and randomized restarts. Previous work has shown that machine learning can be used to individually predict mean, median and variance of RTDs. To establish a new state-of-the-art in predicting RTDs, we demonstrate that the parameters of an RTD should be learned jointly and that neural networks can do this well by directly optimizing the likelihood of an RTD given runtime observations. In an empirical study involving five algorithms for SAT solving and AI planning, we show that neural networks predict the true RTDs of unseen instances better than previous methods, and can even do so when only few runtime observations are available per training instance.
APA, Harvard, Vancouver, ISO, and other styles
6

Wang, Puyu, Liang Wu, and Yunwen Lei. "Stability and Generalization for Randomized Coordinate Descent." In Thirtieth International Joint Conference on Artificial Intelligence {IJCAI-21}. International Joint Conferences on Artificial Intelligence Organization, 2021. http://dx.doi.org/10.24963/ijcai.2021/427.

Full text
Abstract:
Randomized coordinate descent (RCD) is a popular optimization algorithm with wide applications in various machine learning problems, which motivates a lot of theoretical analysis on its convergence behavior. As a comparison, there is no work studying how the models trained by RCD would generalize to test examples. In this paper, we initialize the generalization analysis of RCD by leveraging the powerful tool of algorithmic stability. We establish argument stability bounds of RCD for both convex and strongly convex objectives, from which we develop optimal generalization bounds by showing how to early-stop the algorithm to tradeoff the estimation and optimization. Our analysis shows that RCD enjoys better stability as compared to stochastic gradient descent.
APA, Harvard, Vancouver, ISO, and other styles
7

Briest, Patrick, Shuchi Chawla, Robert Kleinberg, and S. Matthew Weinberg. "Pricing Randomized Allocations." In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2010. http://dx.doi.org/10.1137/1.9781611973075.49.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Matuschke, Jannik, Martin Skutella, and José A. Soto. "Robust randomized matchings." In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2014. http://dx.doi.org/10.1137/1.9781611973730.127.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Feuilloley, Laurent, and Pierre Fraigniaud. "Randomized Local Network Computing." In SPAA '15: 27th ACM Symposium on Parallelism in Algorithms and Architectures. ACM, 2015. http://dx.doi.org/10.1145/2755573.2755596.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

El-Shaer, Ahmed H., and Masayoshi Tomizuka. "Multi-Objective H2/H∞ Static Output Feedback Control: A Hybrid LMI/Genetic Algorithm Approach." In ASME 2010 Dynamic Systems and Control Conference. ASMEDC, 2010. http://dx.doi.org/10.1115/dscc2010-4126.

Full text
Abstract:
This paper is concerned with the synthesis of static output feedback (SOF) control satisfying multi-objective H2/H∞ performance for LTI systems. Given an initially stabilizing SOF gain Ko, an estimate of the set of stabilizing gains is obtained using Monte Carlo based randomized search. A synthesis algorithm which combines both linear matrix inequalities (LMIs) and genetic algorithms (GA) is proposed. To improve the efficiency of this hybrid algorithm, the GA employs a projection-like operation so that the solution candidates lie in the interior of the set of stabilizing gains in a neighborhood of Ko.
APA, Harvard, Vancouver, ISO, and other styles

Reports on the topic "Randomised algorithm"

1

Jones, Peter W., Andrei Osipov, and Vladimir Rokhlin. A Randomized Approximate Nearest Neighbors Algorithm. Defense Technical Information Center, 2010. http://dx.doi.org/10.21236/ada555156.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Martinsson, Per-Gunnar, Vladimir Rockhlin, and Mark Tygert. A Randomized Algorithm for the Approximation of Matrices. Defense Technical Information Center, 2006. http://dx.doi.org/10.21236/ada458932.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Martinsson, Per-Gunnar, Vladimir Rokhlin, and Mark Tygert. A Randomized Algorithm for the Approximation of Matrices. Defense Technical Information Center, 2006. http://dx.doi.org/10.21236/ada458927.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Matei, Ion, Christoforos Somarakis, and John S. Baras. A Randomized Gossip Consenus Algorithm on Convex Metric Spaces. Defense Technical Information Center, 2012. http://dx.doi.org/10.21236/ada588967.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Jones, Peter W., Andrei Osipov, and Vladimir Rokhlin. A Randomized Approximate Nearest Neighbors Algorithm - A Short Version. Defense Technical Information Center, 2011. http://dx.doi.org/10.21236/ada639824.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Rokhlin, Vladimir, and Mark Tygert. A Fast Randomized Algorithm for Overdetermined Linear Least-Squares Regression. Defense Technical Information Center, 2008. http://dx.doi.org/10.21236/ada489855.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Weare, Jonathan. Ensemble simulation techniques and fast randomized algorithms (Final Closeout Report). Office of Scientific and Technical Information (OSTI), 2019. http://dx.doi.org/10.2172/1510999.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Pinar, Ali, Tamara G. Kolda, Kevin Thomas Carlberg, Grey Ballard, and Michael Mahoney. Unsupervised Learning Through Randomized Algorithms for High-Volume High-Velocity Data (ULTRA-HV). Office of Scientific and Technical Information (OSTI), 2018. http://dx.doi.org/10.2172/1417788.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Bhatnagar, Shalabh, Michael C. Fu, Steven I. Marcus, and Shashank Bhatnagar. Randomized Difference Two-Timescale Simultaneous Perturbation Stochastic Approximation Algorithms for Simulation Optimization of Hidden Markov Models. Defense Technical Information Center, 2000. http://dx.doi.org/10.21236/ada637176.

Full text
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Randomised algorithm' for particular source types:
Journal articles Dissertations / Theses Books
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!

To the bibliography