检索结果-内蒙古大学图书馆

A generative power-law search tree model

COMPUTERS & OPERATIONS RESEARCH 2009年第8期36卷 2376-2386页

作者： Carvalho, Alda Crato, Nuno Gomes, Carla Inst Super Engn Lisboa & Cemapre Lisbon Portugal Univ Tecn Lisboa Inst Econ & Management P-1100 Lisbon Portugal Cornell Univ Ithaca NY USA

It is now a well-established fact that search algorithms can exhibit heavy-tailed behavior. However, the reasons behind this fact are not well understood. We provide a generative search tree model whose distribution of the number of nodes visited during search is formally heavy-tailed. Our model allows us to generate search trees with any degree of heavy-tailedness. We also show how the different regimes observed for the runtime distributions of backtrack search methods across different constrainedness regions of random CSP models can be captured by a mixture of the so-called stable distributions. (c) 2008 Elsevier Ltd. All rights reserved.

关键词： random algorithms Heavy-tails Computational statistics

来源：评论

学校读者我要写书评

暂无评论

randomized consensus algorithms over large scale networks

引用

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS 2008年第4期26卷 634-649页

作者： Fagnani, Fabio Zampieri, Sandro Politecn Torino Dipartmento Matemat I-10129 Turin Italy Univ Padua Dept Informat Engn I-35131 Padua Italy

Various randomized consensus algorithms have been proposed in the literature. In some case randomness is due to the choice of a randomized network communication protocol. In other cases, randomness is simply caused by the potential unpredictability of the environment in which the distributed consensus algorithm is implemented. Conditions ensuring the convergence of these algorithms have already been proposed in the literature. As far as the rate of convergence of such algorithms, two approaches can be proposed. One is based on a mean square analysis, while a second is based on the concept of Lyapunov exponent. In this paper, by some concentration results, we prove that the mean square convergence analysis is the right approach when the number of agents is large. Differently from the existing literature, in this paper we do not stick to average preserving algorithms. Instead, we allow to reach consensus at a point which may differ from the average of the initial states. The advantage of such algorithms is that they do not require bidirectional communication among agents and thus they apply to more general contexts. Moreover, in many important contexts it is possible to prove that the displacement from the initial average tends to zero, when the number of agents goes to infinity.

关键词： consensus algorithms large-scale networks random algorithms concentration of performance mean square analysis

来源：评论

学校读者我要写书评

暂无评论

randomized multi-scale kernels learning with sparsity constraint regularization for regression

引用

INTERNATIONAL JOURNAL OF WAVELETS MULTIRESOLUTION AND INFORMATION PROCESSING 2019年第6期17卷

作者： Dong, Xue-Mei Weng, Hao Shi, Jian Gu, Yinhe Zhejiang Gongshang Univ Sch Stat & Math Hangzhou 310018 Zhejiang Peoples R China Hubei Univ Fac Math & Stat Hubei Key Lab Appl Math Wuhan 430062 Hubei Peoples R China

This paper presents a simple multiple kernel learning framework for complicated data modeling, where randomized multi-scale Gaussian kernels are employed as base kernels and a l(1)-norm regularizer is integrated as a sparsity constraint for the solution. The randomly pre- chosen scales provide random basis functions with diversity approximation ability and lead to extremely low computational complexity in finding the optimal solution. The random parameter appearing in the probability distribution and the regularizing factor are decided by the training data with cross validation techniques and the combination weights are solved by a well-posed linear system. Comparison experiments on one function approximation and three real-world regression problems of six learning algorithms are carried out. The way that multi-scale kernels fit the objective function is illustrated, the sparsity and the system robustness analysis with respect to the regularizing factor are given.

关键词： Multiple kernel learning random algorithms multi-scale kernels regression

来源：评论

学校读者我要写书评

暂无评论

An Optimal Greedy Algorithm for the Single Access Contention Resolution Problem

引用

IEEE ACCESS 2019年 7卷 28452-28463页

作者： Olivos-Castillo, Itzel C. Menchaca-Mendez, Ricardo Menchaca-Mendez, Rolando Carvalho, Marcelo M. Rivero-Angeles, Mario E. Inst Politecn Nacl Ctr Invest Comp Mexico City 07738 DF Mexico Univ Brasilia BR-70919970 Brasilia DF Brazil

We present the greedy optimal algorithm for contention resolution (GOAL-CR), a greedy algorithm that solves a variant of the standard contention resolution problem where a set of nodes want to access a shared resource only once, and the objective is to minimize the time it takes for all the nodes to access the resource successfully. These assumptions hold, for instance, in event reporting applications or in the cluster formation phase of wireless sensor networks. We formally prove that the GOAL-CR computes access policies that minimize the expected contention resolution time. We also show, numerically, that the performance of the greedy policies is close to that of a protocol with complete information about the exact number of nodes that have not yet accessed the resource;this latter assumption is hard to fulfill in practice but allows the derivation of a lower bound for the problem. In addition, we show how to adapt the algorithm to scenarios where there is uncertainty in the initial number of nodes and to scenarios where nodes have very limited memory. Finally, we use simulations to show the robustness of the GOAL-CR against asynchronous starts.

关键词： algorithms contention resolution greedy algorithms optimization random algorithms wireless sensor networks

来源：评论

学校读者我要写书评

暂无评论

Drawing from hats by noise-based logic

引用

INTERNATIONAL JOURNAL OF PARALLEL EMERGENT AND DISTRIBUTED SYSTEMS 2017年第3期32卷 244-251页

作者： Zhang, Bruce Kish, Laszlo Bela Granqvist, Claes-Goran Texas A&M Univ Dept Elect Engn College Stn TX 77843 USA Uppsala Univ Dept Engn Sci Angstrom Lab Uppsala Sweden

We utilize the asymmetric random telegraph wave-based instantaneous noise-base logic scheme to represent the problem of drawing numbers from a hat, and we consider two identical hats with the first 2(N) integer numbers. In the first problem, Alice secretly draws an arbitrary number from one of the hats, and Bob must find out which hat is missing a number. In the second problem, Alice removes a known number from one of the hats and another known number from the other hat, and Bob must identify these hats. We show that, when the preparation of the hats with the numbers is accounted for, the noise-based logic scheme always provides an exponential speed-up and/ or it requires exponentially smaller computational complexity than deterministic alternatives. Both the stochasticity and the ability to superpose numbers are essential components of the exponential improvement.

关键词： Noise-based logic random algorithms superposition computational complexity

来源：评论

学校读者我要写书评

暂无评论

Best and Worst Case Permutations for random Online Domination of the Path

引用

DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE 2017年第2期19卷

作者： Coscia, Christopher DeWitt, Jonathan Yang, Fan Zhang, Yiguang Dartmouth Coll Dept Math Hanover NH 03755 USA Haverford Coll Dept Math & Stat Haverford PA 19041 USA Carnegie Mellon Univ Dept Math Sci Pittsburgh PA 15213 USA Stanford Univ Dept Stat Stanford CA 94305 USA

We study a randomized algorithm for graph domination, by which, according to a uniformly chosen permutation, vertices are revealed and added to the dominating set if not already dominated. We determine the expected size of the dominating set produced by the algorithm for the path graph P-n and use this to derive the expected size for some related families of graphs. We then provide a much-refined analysis of the worst and best cases of this algorithm on P-n and enumerate the permutations for which the algorithm has the worst-possible performance and best-possible performance. The case of dominating the path graph has connections to previous work of Bouwer and Star, and of Gessel on greedily coloring the path.

关键词： permutations graph domination random algorithms path graphs asymptotics

来源：评论

学校读者我要写书评

暂无评论

An efficient statistical method for subpixel optical flow detection

引用

ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE 2002年第2期15卷 169-176页

作者： Imiya, A Iwawaki, K Kawamoto, K Natl Inst Informat Chiyoda Ku Tokyo 1018640 Japan Chiba Univ IMIT Media Technol Div Inage Ku Chiba 2638522 Japan Chiba Univ Sch Sci & Technol Inage Ku Chiba 2638522 Japan

In this paper, we show that the randomized sampling and voting process detects optical flow. We introduce a random sampling method for solving the least-squares model-fitting problem using a mathematical property for the construction of pseudo-inverse. Using an appropriate number of images from a sequence of images, our method detects subpixel motion in this sequence. It is possible to compute subpixel motions from a long-time interval. We use the accumulator space for the unification of these flow vectors which are computed from different time intervals. Numerical examples for the test image sequences show the performance of our method. (C) 2002 Published by Elsevier Science Ltd.

关键词： Theil-Sen estimator subpixel analysis robust model fitting random algorithms optical flow

来源：评论

学校读者我要写书评

暂无评论

A PARALLEL GRAPH-COLORING HEURISTIC

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 1993年第3期14卷 654-669页

作者： JONES, MT PLASSMANN, PE

The problem of computing good graph colorings arises in many diverse applications, such as in the estimation of sparse Jacobians and in the development of efficient, parallel iterative methods for solving sparse linear systems. This paper presents an asynchronous graph coloring heuristic well suited to distributed memory parallel computers. Experimental results obtained on an Intel iPSC/860 are presented, which demonstrate that, for graphs arising from finite element applications, the heuristic exhibits scalable performance and generates colorings usually within three or four colors of the best-known linear time sequential heuristics. For bounded degree graphs, it is shown that the expected running time of the heuristic under the P-RAM computation model is bounded by EO(log(n)/log log(n)). This bound is an improvement over the previously known best upper bound for the expected running time of a random heuristic for the graph coloring problem.

关键词： DISTRIBUTED MEMORY COMPUTERS GRAPH COLORING HEURISTICS PARALLEL algorithms random algorithms SPARSE MATRICES

来源：评论

学校读者我要写书评

暂无评论

Analyzing Heuristic-based randomized Search Strategies for the Quantum Circuit Compilation Problem

引用

FUNDAMENTA INFORMATICAE 2020年第3-4期174卷 259-281页

作者： Oddi, Angelo Rasconi, Riccardo ISTC CNR Via San Martino Battaglia 44 I-00185 Rome Italy

In this work we investigate the performance of greedy randomised search (GRS) techniques to the problem of compiling quantum circuits to emerging quantum hardware. Quantum computing (QC) represents the next big step towards power consumption minimisation and CPU speed boost in the future of computing machines. Quantum computing uses quantum gates that manipulate multi-valued bits (qubits). A quantum circuit is composed of a number of qubits and a series of quantum gates that operate on those qubits, and whose execution realises a specific quantum algorithm. Current quantum computing technologies limit the qubit interaction distance allowing the execution of gates between adjacent qubits only. This has opened the way to the exploration of possible techniques aimed at guaranteeing nearest-neighbor (NN) compliance in any quantum circuit through the addition of a number of so-called swap gates between adjacent qubits. In addition, technological limitations (decoherence effect) impose that the overall duration (makespan) of the quantum circuit realization be minimized. One core contribution of the paper is the definition of two lexicographic ranking functions for quantum gate selection, using two keys: one key acts as a global closure metric to minimise the solution makespan;the second one is a local metric, which favours the mutual approach of the closest qstates pairs. We present a GRS procedure that synthesises NN-compliant quantum circuits realizations, starting from a set of benchmark instances of different size belonging to the Quantum Approximate Optimization Algorithm (QAOA) class tailored for the MaxCut problem. We propose a comparison between the presented meta-heuristics and the approaches used in the recent literature against the same benchmarks, both from the CPU efficiency and from the solution quality standpoint. In particular, we compare our approach against a reference benchmark initially proposed and subsequently expanded in [1] by considering: (i) vari

关键词： Quantum Computing Optimization Scheduling Planning Greedy Heuristics random algorithms

来源：评论

学校读者我要写书评

暂无评论

A HEURISTIC ALGORITHM FOR SMALL SEPARATORS IN ARBITRARY GRAPHS

引用

SIAM JOURNAL ON COMPUTING 1990年第2期19卷 267-280页

作者： PLAISTED, DA

Some heuristic random polynomial time algorithms for finding good cuts in arbitrary graphs are presented. A cut is good if there are a small number of edges across the cut and if the cut divides the set of vertices somewhat evenly. The algorithms obtain cuts from solutions to randomly chosen network flow problems based on the input graph. Probabilistic bounds for the goodness of the cut obtained in terms of the goodness of an optimal separator are derived. These bounds are valid for all input graphs. There is reason to think that the algorithm will perform better than the bounds indicate.

关键词： 68Q20 68Q25 graph algorithms random algorithms separators maximum flow network flow

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：