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

Monte Carlo and Las Vegas randomized algorithms for systems and control - An introduction

EUROPEAN JOURNAL OF CONTROL 2007年第2-3期13卷 189-203页

作者： Tempo, Roberto Ishii, Hideaki Politecn Torino CNR IEIIT I-10129 Turin Italy Tokyo Inst Technol Dept Computat Intelligence & Syst Sci Midori Ku Yokohama Kanagawa 2268502 Japan

In this paper, we present an introduction to Monte Carlo and Las Vegas randomized algorithms for systems and control. Specific applications of these algorithms include stability analysis, Lyapunov functions, and distr... 详细信息

关键词： systems and control probabilistic approach randomized algorithms Monte Carlo algorithms Las Vegas algorithms

来源：评论

学校读者我要写书评

暂无评论

NON-EXHAUSTIVE JOIN ORDERING SEARCH algorithms FOR LJQO

NON-EXHAUSTIVE JOIN ORDERING SEARCH ALGORITHMS FOR LJQO

引用

13th International Conference on Enterprise Information Systems (ICEIS 2011)

作者： Bini, Tarcizio Alexandre Lange, Adrian Sunye, Marcos Sfair Silva, Fabian de Almeida, Eduardo Cunha Univ Fed Parana Dept Informat Ctr Politecn Curitiba Parana Brazil

ISBN: (纸本)9789898425539

In relational database systems the optimization of select-project-join queries is a combinatorial problem. The use of exhaustive search methods is prohibitive because of the exponential increase of the search space. randomized searches are used to find near optimal plans in polynomial time. In this paper, we investigate the large join query optimization (LJQO) problem by extending randomized algorithms and implementing a 2PO algorithm as a query optimizer in a popular open-source DBMS. We compare our solution with an implementation of a genetic algorithm. Through a multidimensional test schema, we discuss pros and cons about the behavior of these algorithms. Our results show that 2PO algorithm is fast to run and the costs of generated plans are better in most cases when compared to those of the genetic algorithms.

关键词： Query optimization Join ordering randomized algorithms Genetic algorithms

来源：评论

学校读者我要写书评

暂无评论

Rapid randomized Pruning for Fast Greedy Distributed algorithms

Rapid Randomized Pruning for Fast Greedy Distributed Algorit...

引用

29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing

作者： Pandit, Saurav Pemmaraju, Sriram V. Univ Iowa Dept Comp Sci Iowa City IA 52242 USA

ISBN: (纸本)9781605588889

We start by defining a pruning process involving sellers on one side and buyers on the other. The goal is to quickly select a subset of the sellers so that the products that these sellers bring to the market has small cost ratio, i.e., the ratio of the total cost of the selected sellers' products to amount that interested buyers are willing to pay. As modeled here, the pruning process can be used to speed up distributed implementations of greedy algorithms (e.g., for minimum dominating set, facility location, etc). We present a randomized instance of the pruning process that, for any positive k, runs in O(k) communication rounds with O(log N)-sized messages, yielding a cost ratio of O(N-c/k). Here N is the product of the number of sellers and number of buyers and c is a small constant. Using this O(k)-round pruning algorithm as the basis, we derive several simple, greedy, O(k)-round distributed approximation algorithms for AIDS and facility location (both metric and non-metric versions). Our algorithms achieve optimal approximation ratios in polylogarithmic rounds and shave a "logarithmic factor" off the best, known, approximation factor, typically achieved using LP-rounding techniques.

关键词： Distributed algorithms Facility Location Greedy algorithms Minimum Dominating Set Primal-dual algorithms randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

randomized min-max optimization: the exact risk of multiple cost levels

Randomized min-max optimization: the exact risk of multiple ...

引用

IEEE Conference on Decision and Control

作者： Algo Care Simone Garatti Marco C. Campi Dipartimento di Ingegneria Informazione Universita di Brescia via Branze 38 25123 Brescia Italia Dipartimento di Elettronica e Informazione Politecnico di Milano piazza Leonardo da Vinci 32 20133 Milano Italia Dipartimento di Ingegneria dell'Informazione Universita di Brescia via Branze 38 25123 Brescia Italia

ISBN: (纸本)9781612848006

In this paper, we present a theoretical result that applies to convex optimization problems in the presence of an uncertain stochastic parameter. We consider the min-max sample-based solution, i.e. the min-max solution computed over a finite sample of instances of the uncertain stochastic parameter, and the costs incurred by this solution in correspondence of the sampled parameter instances. Our goal is to evaluate the risks associated to the various costs, where the risk associated to a cost is the probability that the cost is exceeded when a new uncertainty instance is seen. The theoretical result proven in this paper is that the risks form a random vector whose probability distribution is always an ordered Dirichlet distribution, irrespective of the probability measure of the uncertain stochastic parameter. This evaluation characterizes completely the risks associated to the costs, and represents a full-fledged result on the reliability of the min-max sample-based solution.

关键词： randomized algorithms Optimization Optimization algorithms

来源：评论

学校读者我要写书评

暂无评论

Fast Computation of Small Cuts via Cycle Space Sampling

引用

ACM TRANSACTIONS ON algorithms 2011年第4期7卷 46-46页

作者： Pritchard, David Thurimella, Ramakrishna Ecole Polytech Fed Lausanne EPFL SB MATHAA DISOPT CH-1015 Lausanne Switzerland Univ Denver Denver CO 80208 USA

We describe a new sampling-based method to determine cuts in an undirected graph. For a graph (V, E), its cycle space is the family of all subsets of E that have even degree at each vertex. We prove that with high probability, sampling the cycle space identifies the cuts of a graph. This leads to simple new linear-time sequential algorithms for finding all cut edges and cut pairs (a set of 2 edges that form a cut) of a graph. In the model of distributed computing in a graph G = (V, E) with O(log vertical bar V vertical bar)-bit messages, our approach yields faster algorithms for several problems. The diameter of G is denoted by D, and the maximum degree by Delta. We obtain simple O(D)-time distributed algorithms to find all cut edges, 2-edge-connected components, and cut pairs, matching or improving upon previous time bounds. Under natural conditions these new algorithms are universally optimal-that is, a Omega(D)-time lower bound holds on every graph. We obtain a O(D + Delta/log vertical bar V vertical bar)-time distributed algorithm for finding cut vertices;this is faster than the best previous algorithm when Delta, D = O(root vertical bar V vertical bar). A simple extension of our work yields the first distributed algorithm with sub-linear time for 3-edge-connected components. The basic distributed algorithms are Monte Carlo, but they can be made Las Vegas without increasing the asymptotic complexity. In the model of parallel computing on the EREW PRAM, our approach yields a simple algorithm with optimal time complexity O(log V) for finding cut pairs and 3-edge-connected components.

关键词： Distributed algorithms graph connectivity linear algebra parallel algorithms randomized algorithms universal optimality

来源：评论

学校读者我要写书评

暂无评论

Secretary Problems: Laminar Matroid and Interval Scheduling 11

Secretary Problems: Laminar Matroid and Interval Scheduling

引用

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete algorithms

作者： Sungjin Im Yajun Wang Department of Computer Science University of Illinois Microsoft Research Asia Beijing

ISBN: (纸本)9780898719932

The classical secretary problem studies the problem of hiring the best secretary from among the secretaries who arrive in random order by making immediate and irrevocable decisions. After the interesting connection to online mechanism design was found [19, 20], the random order input assumption has been studied for a variety of problems. Babaioff et al. [4] formalized a general version of the secretary problem, namely the matroid secretary problem. In the problem, a secretary corresponds to an element in the universe U. The goal is to select the maximum weight independent set. They conjectured that the matroid secretary problem, for any matroid, allows a constant competitive algorithm. The conjecture remains open. Some constant approximation algorithms are currently known for some special cases of matroids. Another interesting type of secretary problem was studied where elements have non-uniform sizes, as is the case in the knapsack secretary problem [3, 6]. In this paper, we consider two interesting secretary problems. One is when the matroid is a laminar matroid, which generalizes uniform / partition / truncated partition matroids. For the laminar matroid secretary problem, using a novel replacement rule which we call "kick next," we give the first constant-competitive algorithm. The other is the interval scheduling secretary problem, which generalizes the knapsack secretary problem. In this problem, each job J_i arrives with interval I_i, processing time pi and weight w_i. If J_i is accepted, then it must be scheduled during I_i, not necessarily continuously. The goal is to accept the jobs of the maximum total weight which are schedulable. We give a simple O(logD)-competitive algorithm and a nearly matching lower bound on the competitive ratio of any randomized algorithm, where D is the maximum interval length of any job.

关键词： secretary Matroid jobs maximum length gun overall weight combat total weight randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

An Optimal Lower Bound for Buffer Management in Multi-Queue Switches 11

An Optimal Lower Bound for Buffer Management in Multi-Queue ...

引用

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete algorithms

作者： Marcin Bienkowski Institute of Computer Science University of Wroclaw

ISBN: (纸本)9780898719932

In the online packet buffering problem (also known as the unweighted FIFO variant of buffer management), we focus on a single network packet switching device with several input ports and one output port. This device forwards unit-size, unit-value packets from input ports to the output port. Buffers attached to input ports may accumulate incoming packets for later transmission; if they cannot accommodate all incoming packets, the excess is lost. A packet buffering algorithm has to choose from which buffers to transmit packets in order to minimize the number of lost packets and thus maximize the throughput. We present a tight lower bound of e/(e - 1) ≈ 1.582 on the competitive ratio of the throughput maximization, which holds even for randomized algorithms. This improves the previously best known lower bound of 1.4659 and matches the performance of the algorithm Random Schedule. Our result contradicts the claimed performance of the Random Permutation algorithm; we point out a flaw in its original analysis.

关键词： Online algorithms Packet buffering Buffer management Multi-queue switches input port Packet Lower bound buffers output ports randomized algorithms Throughput

来源：评论

学校读者我要写书评

暂无评论

Sparse Features for PCA-Like Linear Regression 11

Sparse Features for PCA-Like Linear Regression

引用

Annual Conference on Neural Information Processing Systems

作者： Christos Boutsidis Petros Drineas Malik Magdon-Ismail Mathematical Sciences Department IBM T. J. Watson Research Center Yorktown Heights New York Computer Science Department Rensselaer Polytechnic Institute Troy NY 12180

ISBN: (纸本)9781618395993

Principal Components Analysis (PCA) is often used as a feature extraction procedure. Given a matrix X E R~(n×d), whose rows represent n data points with respect to d features, the top k right singular vectors of X (the so-called eigenfeatures), are arbitrary linear combinations of all available features. The eigenfeatures are very useful in data analysis, including the regularization of linear regression. Enforcing sparsity on the eigenfeatures, i.e., forcing them to be linear combinations of only a small number of actual features (as opposed to all available features), can promote better generalization error and improve the interpretability of the eigenfeatures. We present deterministic and randomized algorithms that construct such sparse eigenfeatures while provably achieving in-sample performance comparable to regularized linear regression. Our algorithms are relatively simple and practically efficient, and we demonstrate their performance on several data sets.

关键词： Linear Regression generalization error Feature extraction randomized algorithms interpretability Data analysis deterministic algorithms

来源：评论

学校读者我要写书评

暂无评论

Fast Information Spreading in Graphs with Large Weak Conductance 11

Fast Information Spreading in Graphs with Large Weak Conduct...

引用

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete algorithms

作者： Keren Censor-Hillel Hadas Shachnai Department of Computer Science Technion

ISBN: (纸本)9780898719932

Gathering data from nodes in a network is at the heart of many distributed applications, most notably, while performing a global task. We consider information spreading among n nodes of a network, where each node v has a message m(v) which must be received by all other nodes. The time required for information spreading has been previously upper-bounded with an inverse relationship to the conductance of the underlying communication graph. This implies high running times for graphs with small conductance. The main contribution of this paper is an information spreading algorithm which overcomes communication bottlenecks and thus achieves fast information spreading for a wide class of graphs, despite their small conductance. As a key tool in our study we use the recently defined concept of weak conductance, a generalization of classic graph conductance which measures how well-connected the components of a graph are. Our hybrid algorithm, which alternates between random and deterministic communication phases, exploits the connectivity within components by first applying partial information spreading, after which messages are sent across bottlenecks, thus spreading further throughout the network. This yields substantial improvements over the best known running times of algorithms for information spreading on any graph that has a large weak conductance, from polynomial to polylogarithmic number of rounds. We demonstrate the power of fast information spreading in accomplishing global tasks on the leader election problem, which lies at the core of distributed computing. Our results yield an algorithm for leader election that has a scalable running time on graphs with large weak conductance, improving significantly upon previous results.

关键词： Distributed computing randomized algorithms Weak conductance Information spreading Leader election Distributed computing Conductance randomized algorithms algorithms

来源：评论

学校读者我要写书评

暂无评论

A subexponential lower bound for the Random Facet algorithm for Parity Games 11

A subexponential lower bound for the Random Facet algorithm ...

引用

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete algorithms

作者： Oliver Friedmann Thomas Dueholm Hansen Uri Zwick Department of Computer Science University of Munich Department of Computer Science Aarhus University

ISBN: (纸本)9780898719932

Parity Games form an intriguing family of infinite duration games whose solution is equivalent to the solution of important problems in automatic verification and automata theory. They also form a very natural subclass of Deterministic Mean Payoff Games, which in turn is a very natural subclass of turn-based Stochastic Mean Payoff Games. It is a major open problem whether these game families can be solved in polynomial time. The currently theoretically fastest algorithms for the solution of all these games are adaptations of the randomized algorithms of Kalai and of Matousek, Sharir and Welzl for LP-type problems, an abstract generalization of linear programming. The expected running time of both algorithms is subexponential in the size of the game, i.e., 2~(O((n log n)~(1/2))), where n is the number of vertices in the game. We focus in this paper on the algorithm of Matousek, Sharir and Welzl and refer to it as the Random Facet algorithm. Matousek constructed a family of abstract optimization problems such that the expected running time of the Random Facet algorithm, when run on a random instance from this family, is close to the subexponential upper bound given above. This shows that in the abstract setting, the 2~(O((n log n)~(1/2))) upper bound on the complexity of the Random Facet algorithm is essentially tight. It is not known, however, whether the abstract optimization problems constructed by Matousek correspond to games of any of the families mentioned above. There was some hope, therefore, that the Random Facet algorithm, when applied to, say, parity games, may run in polynomial time. We show, that this, unfortunately, is not the case by constructing explicit parity games on which the expected running time of the Random Facet algorithm is close to the subexponential upper bound. The games we use mimic the behavior of a randomized counter. They are also the first explicit LP-type problems on which the Random Facet algorithm is not polynomial.

关键词： Game theory Runtime Articular Bone Surface algorithms family Game animals Upper bound Random Polynomial time AUTOMATA THEORY randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：