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

Self assembly of rectangular shapes on concentration programming and probabilistic tile assembly models

NATURAL COMPUTING 2012年第2期11卷 199-207页

作者： Kundeti, Vamsi Rajasekaran, Sanguthevar Univ Connecticut Dept Comp Sci & Engn Storrs CT 06269 USA

Efficient tile sets for self assembling rectilinear shapes is of critical importance in algorithmic self assembly. A lower bound on the tile complexity of any deterministic self assembly system for an n x n square is (inferred from the Kolmogrov complexity). Deterministic self assembly systems with an optimal tile complexity have been designed for squares and related shapes in the past. However designing unique tiles specific to a shape is still an intensive task in the laboratory. On the other hand copies of a tile can be made rapidly using PCR (polymerase chain reaction) experiments. This led to the study of self assembly on tile concentration programming models. We present two major results in this paper on the concentration programming model. First we show how to self assemble rectangles with a fixed aspect ratio (alpha:beta), with high probability, using tiles. This result is much stronger than the existing results by Kao et al. (randomized self-assembly for approximate shapes, LNCS, vol 5125. Springer, Heidelberg, 2008) and Doty (randomized self-assembly for exact shapes. In: proceedings of the 50th annual IEEE symposium on foundations of computer science (FOCS), IEEE, Atlanta. pp 85-94, 2009)-which can only self assembly squares and rely on tiles which perform binary arithmetic. On the other hand, our result is based on a technique called staircase sampling. This technique eliminates the need for sub-tiles which perform binary arithmetic, reduces the constant in the asymptotic bound, and eliminates the need for approximate frames (Kao et al. randomized self-assembly for approximate shapes, LNCS, vol 5125. Springer, Heidelberg, 2008) . Our second result applies staircase sampling on the equimolar concentration programming model (The tile complexity of linear assemblies. In: proceedings of the 36th international colloquium automata, languages and programming: Part I on ICALP '09, Springer-Verlag, pp 235-253, 2009), to self assemble rectangles (of fixed aspect r

关键词： Tile assembly model Concentration programming Self assembly algorithms Probabilistic self assembly model (PTAM) randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Testable and untestable classes of first-order formulae

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2012年第5期78卷 1557-1578页

作者： Jordan, Charles Zeugmann, Thomas Hokkaido Univ Div Comp Sci Sapporo Hokkaido 0600814 Japan

In property testing, the goal is to distinguish structures that have some desired property from those that are far from having the property, based on only a small, random sample of the structure. We focus on the classification of first-order sentences according to their testability. This classification was initiated by Alon et al. (2000) [2], who showed that graph properties expressible with prefix there exists*for all* are testable but that there is an untestable graph property expressible with quantifier prefix for all*there exists*. The main results of the present paper are as follows. We prove that all (relational) properties expressible with quantifier prefix there exists*for all there exists* (Ackermann's class with equality) are testable and also extend the positive result of Alon et al. (2000) [2] to relational structures using a recent result by Austin and Tao (2010) [8]. Finally, we simplify the untestable property of Alon et al. (2000) [2] and show that prefixes for all(3)there exists, for all(2)there exists for all, for all there exists for all(2) and for all there exists V there exists can express untestable graph properties when equality is allowed. (C) 2012 Elsevier Inc. All rights reserved.

关键词： Property testing Logic randomized algorithms Ackermann's class Ramsey's class

来源：评论

学校读者我要写书评

暂无评论

SAMPLING-BASED APPROXIMATION algorithms FOR MULTISTAGE STOCHASTIC OPTIMIZATION

引用

SIAM JOURNAL ON COMPUTING 2012年第4期41卷 975-1004页

作者： Swamy, Chaitanya Shmoys, David B. Univ Waterloo Dept Combinator & Optimizat Waterloo ON N2L 3G1 Canada Cornell Univ Dept Comp Sci Ithaca NY 14853 USA

Stochastic optimization problems provide a means to model uncertainty in the input data where the uncertainty is modeled by a probability distribution over the possible realizations of the actual data. We consider a broad class of these problems in which the realized input is revealed through a series of stages and hence are called multistage stochastic programming problems. Multistage stochastic programming and, in particular, multistage stochastic linear programs with full recourse, is a domain that has received a great deal of attention within the operations research community, mostly from the perspective of computational results in application settings. Our main result is to give the first fully polynomial approximation scheme for a broad class of multistage stochastic linear programming problems with any constant number of stages. The algorithm analyzed, known as the sample average approximation method, is quite simple and is the one most commonly used in practice. The algorithm accesses the input by means of a "black box" that can generate, given a series of outcomes for the initial stages, a sample of the input according to the conditional probability distribution (given those outcomes). We use this to obtain the first approximation algorithms for a variety of k-stage generalizations of basic combinatorial optimization problems including the set cover, vertex cover, multicut on trees, facility location, and multicommodity flow problems.

关键词： approximation algorithms stochastic optimization convex optimization randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

A Probabilistic Approach to Optimal Estimation - Part II: algorithms and Applications

A Probabilistic Approach to Optimal Estimation - Part II: Al...

引用

51st IEEE Annual Conference on Decision and Control (CDC)

作者： Dabbene, Fabrizio Sznaier, Mario Tempo, Roberto Politecn Torino CNR IEIIT Inst I-10129 Turin Italy Northeastern Univ Boston MA 02115 USA

ISBN: (纸本)9781467320665

In this paper, we develop randomized and deterministic algorithms for computing the probabilistic radius of information associated to an identification problem, and the corresponding optimal probabilistic estimate. To compute this estimate, in the companion paper [11] the concept of optimal violation function is introduced. Moreover, for the case of uniform distributions, it is shown how its computation is related to the solution of a (quasi) concave optimization problem, based on to the maximization of the volume of a specially constructed polytope. In this second paper, we move a step further and develop specific algorithms for addressing this problem. In particular, since the problem is NP-hard, we propose both randomized relaxations (based on a probabilistic volume oracle and stochastic optimization algorithms), and deterministic ones (based on semi-definite programming). Finally, we present a numerical example illustrating the performance of the proposed algorithms.

关键词： System identification optimal algorithms randomized algorithms uncertain systems

来源：评论

学校读者我要写书评

暂无评论

Fast Algorithm for Finding True Number of Clusters. Applications to Control Systems

Fast Algorithm for Finding True Number of Clusters. Applicat...

引用

24th Chinese Control and Decision Conference (CCDC)

作者： Morozkov, Mikhail Granichin, Oleg Volkovich, Zeev Zhang, Xuming St Petersburg State Univ Dept Math & Mech Univ Skii Pr 28 St Petersburg 198504 Russia Braude Coll Engn Dept ORT IL-21982 Karmiel Israel Huazhong Univ Sci & Technol Sch Life Sci & Technol Dept Biomed Engn Wuhan 430074 Peoples R China

ISBN: (纸本)9781457720727

One of the most difficult problems in cluster analysis is the identification of the number of groups in a given data set. In this paper we offer the randomized approach in the rate distortion framework. A randomized algorithm has been suggested to allocate this position. The scenario approach is used to significantly reduce the computational complexity. With ability to determine the true number of clusters and perform clustering in real-time operational mode we outline several applications in control systems and decision-making problems that can benefit from algorithm in question essentially. We also provide simulation results to show considerable speed optimization with guaranteed level of probability.

关键词： Clustering randomized algorithms Adaptive Control Optimitzaion

来源：评论

学校读者我要写书评

暂无评论

The Constrained Ski-Rental Problem and its Application to Online Cloud Cost Optimization

The Constrained Ski-Rental Problem and its Application to On...

引用

IEEE INFOCOM

作者： Ali Khanafer Murali Kodialam Krishna P. N. Puttaswamy Coordinated Science Laboratory University of Illinois at Urbana-Champaign USA Bell Laboratories Alcatel-Lucent Murray Hill NJ USA

ISBN: (纸本)9781467359443

Cloud service providers (CSPs) enable tenants to elastically scale their resources to meet their demands. In fact, there are various types of resources offered at various price points. While running applications on the cloud, a tenant aiming to minimize cost is often faced with crucial trade-off considerations. For instance, upon each arrival of a query, a web application can either choose to pay for CPU to compute the response fresh, or pay for cache storage to store the response so as to reduce the compute costs of future requests. The Ski-Rental problem abstracts such scenarios where a tenant is faced with a to-rent-or-to-buy trade-off;in its basic form, a skier should choose between renting or buying a set of skis without knowing the number of days she will be skiing. In this paper, we introduce a variant of the classical Ski-Rental problem in which we assume that the skier knows the first (or second) moment of the distribution of the number of ski days in a season. We demonstrate that utilizing this information leads to achieving the best worst-case expected competitive ratio (CR) performance. Our method yields a new class of randomized algorithms that provide arrivals-distribution-free performance guarantees. Further, we apply our solution to a cloud file system and demonstrate the cost savings obtained in comparison to other competing schemes. Simulations illustrate that our scheme exhibits robust average-cost performance that combines the best of the well-known deterministic and randomized schemes previously proposed to tackle the Ski-Rental problem.

关键词： tenants Property Leasing Remuneration Wages cost analysis cache storage skier moment distribution Skiing File systems randomized algorithms second moment central processing units Scheme tradeoffs

来源：评论

学校读者我要写书评

暂无评论

A Parallel Tiled Solver for Dense Symmetric Indefinite Systems on Multicore Architectures

A Parallel Tiled Solver for Dense Symmetric Indefinite Syste...

引用

26th IEEE International Parallel and Distributed Processing Symposium (IPDPS) / Workshop on High Performance Data Intensive Computing

作者： Baboulin, Marc Becker, Dulceneia Dongarra, Jack Inria Saclay Ile de France F-91893 Orsay France Univ Paris Sud F-91405 Orsay France Univ Tennessee Knoxville TN 37996 USA Oak Ridge Natl Lab Oak Ridge TN USA Univ Manchester Manchester Lancs England

ISBN: (纸本)9780769546759

We describe an efficient and innovative parallel tiled algorithm for solving symmetric indefinite systems on multicore architectures. This solver avoids pivoting by using a multiplicative preconditioning based on symmetric randomization. This randomization prevents the communication overhead due to pivoting, is computationally inexpensive and requires very little storage. Following randomization, a tiled factorization is used that reduces synchronization by using static or dynamic scheduling. We compare Gflop/s performance of our solver with other types of factorizations on a current multicore machine and we provide tests on accuracy using LAPACK test cases.

关键词： dense linear algebra symmetric indefinite systems randomized algorithms tiled factorization

来源：评论

学校读者我要写书评

暂无评论

Probability Distributions Achieving the Equilibrium of an AND-OR Tree under Directional algorithms

Probability Distributions Achieving the Equilibrium of an AN...

引用

International MultiConference of Engineers and Computer Scientists (IMECS 2012)

作者： Suzuki, Toshio Nakamura, Ryota Tokyo Metropolitan Univ Dept Math & Informat Sci Hachioji Tokyo 1920397 Japan Shimizu Corp Shimizu Shizuoka Japan

ISBN: (纸本)9789881925114

Consider a probability distribution d on the truth assignments to a perfect binary AND-OR tree. Liu and Tanaka (2007) extends the work of Saks and Wigderson (1986), and they characterize the eigen-distribution, the distribution achieving the equilibrium, as the uniform distribution on the 1-set (the set of all reluctant assignments for which the root has the value 1). We show that the uniqueness of the eigen-distribution fails provided that we restrict ourselves to directional algorithms. An alpha-beta pruning algorithm is said to be directional (Pearl, 1980) if for some linear ordering of the leaves (Boolean variables) it never selects for examination a leaf situated to the left of a previously examined leaf. We also show that the following weak version of the Liu-Tanaka result holds for the situation where only directional algorithms are considered;a distribution is eigen if and only if it is a distribution on the 1-set such that the cost does not depend on an associated deterministic algorithm.

关键词： AND-OR tree directional algorithm computational complexity randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Matching with our Eyes Closed

Matching with our Eyes Closed

引用

IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS)

作者： Goel, Gagan Tripathi, Pushkar Google Res New York NY 10024 USA Georgia Inst Technol Atlanta GA USA

ISBN: (纸本)9781467343831

Motivated by an application in kidney exchange, we study the following query-commit problem: we are given the set of vertices of a non-bipartite graph G. The set of edges in this graph are not known ahead of time. We can query any pair of vertices to determine if they are adjacent. If the queried edge exists, we are committed to match the two endpoints. Our objective is to maximize the size of the matching. This restriction in the amount of information available to the algorithm constraints us to implement myopic, greedy-like algorithms. A simple deterministic greedy algorithm achieves a factor 1/2 which is tight for deterministic algorithms. An important open question in this direction is to give a randomized greedy algorithm that has a significantly better approximation factor. This question was first asked almost 20 years ago by Dyer and Frieze [9] where they showed that a natural randomized strategy of picking edges uniformly at random doesn't help and has an approximation factor of 1/2 + o(1). They left it as an open question to devise a better randomized greedy algorithm. In subsequent work, Aronson, Dyer, Frieze, and Suen [2] gave a different randomized greedy algorithm and showed that it attains a factor 0.5 + epsilon where epsilon is 0.0000025. In this paper we propose and analyze a new randomized greedy algorithm for finding a large matching in a general graph and use it to solve the query commit problem mentioned above. We show that our algorithm attains a factor of at least 0.56, a significant improvement over 0.50000025. We also show that no randomized algorithm can have an approximation factor better than 0.7916 for the query commit problem. For another large and interesting class of randomized algorithms that we call vertex-iterative algorithms, we show that no vertex-iterative algorithm can have an approximation factor better than 0.75.

关键词： Matching randomized algorithms Combinatorial Optimization

来源：评论

学校读者我要写书评

暂无评论

Fast distributed smoothing of relative measurements

Fast distributed smoothing of relative measurements

引用

51st IEEE Annual Conference on Decision and Control (CDC)

作者： Freris, Nikolaos M. Zouzias, Anastasios Ecole Polytech Fed Lausanne Sch Comp & Commun Sci CH-1015 Lausanne Switzerland Univ Toronto Dept Comp Sci Toronto ON Canada

ISBN: (纸本)9781467320665

We consider the problem of estimation from noisy relative measurements in a network. In previous work, a distributed scheme for obtaining least-squares (LS) estimates was developed based on the Jacobi algorithm;in a synchronous version, the algorithm was shown to converge exponentially and bounds on the rate of convergence have been obtained. In this paper, we design and analyze a new class of distributed asynchronous smoothing algorithms based on a randomized version of Kaczmarz algorithm for solving linear systems. One of the proposed schemes applies randomized Kaczmarz directly to the noisy linear system, whereas the other one operates on the normal equations for LS estimation. We analyze the expected convergence rate of the proposed algorithms depending solely on properties of the network topology. Inspired by the analytical insights, we propose a distributed smoothing algorithm, namely randomized Kaczmarz Over-smoothing (RKO), which has demonstrated significant improvement over existing protocols in terms of both convergence speedup and energy savings.

关键词： Smoothing Distributed algorithms Clock synchronization randomized algorithms Least Squares Estimation Wireless Networks Sensor networks

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：