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

A SUBEXPONENTIAL algorithm FOR ABSTRACT OPTIMIZATION PROBLEMS

SIAM JOURNAL ON COMPUTING 1995年第5期24卷 1018-1035页

作者： GARTNER, B FREE UNIV BERLIN INST INFORMAT TAKUSTR 9 D-14195 BERLIN GERMANY

An abstract optimization problem (AOP) is a triple (H, <, Phi) where H is a finite set, < is a total order on 2(H), and Phi is an oracle that, for given F subset of or equal to G subset of or equal to H, either reports that F = min(<){F'\F' subset of or equal to G} or returns a set F' subset of or equal to G with F' < F. Solving the problem means finding the minimum set in H. We present a randomized algorithm that solves any AOP with an expected number of at most e(2 root n+0(4 root Inn)) oracle calls, n = \H\. In contrast, any deterministic algorithm needs to make 2(n) - 1 oracle calls in the worst case. The algorithm is applied to the problem of finding the distance between two n-vertex (or n-facet) convex polyhedra in d-space, and the computation of the smallest ball containing n points in d-space;for both problems we give the first subexponential bounds in the arithmetic model of computation.

关键词： COMPUTATIONAL GEOMETRY SMALLEST ENCLOSING BALL DISTANCE BETWEEN CONVEX POLYHEDRA LOCAL OPTIMIZATION randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Models and algorithms for packing rectangles into the smallest square

引用

COMPUTERS & OPERATIONS RESEARCH 2015年 63卷 161-171页

作者： Martello, Silvano Monaci, Michele Univ Bologna DEI Guglielmo Marconi I-40136 Bologna Italy Univ Padua DEI I-35131 Padua Italy

We consider the problem of determining the smallest square into which a given set of rectangular items can be packed without overlapping. We present an ILP model, an exact approach based on the iterated execution of a two-dimensional packing algorithm, and a randomized metaheuristic. Such approaches are valid both for the case where the rectangles have fixed orientation and the case where they can be rotated by 90 degrees. We computationally evaluate the performance and the limits of the proposed approaches on a large set of instances, including a number of classical benchmarks from the literature, for both cases above, and for the special case where the items are squares. (C) 2015 Elsevier Ltd. All rights reserved.

关键词： Two dimensional packing Mathematical model randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

A Monte Carlo algorithm for real time task scheduling on multi-core processors with software controlled dynamic voltage scaling

引用

APPLIED MATHEMATICAL MODELLING 2014年第7-8期38卷 1929-1947页

作者： Mishra, Abhishek Tripathi, Anil Kumar Indian Inst Technol Jodhpur Ctr Excellence Informat & Commun Technol Jodhpur 342011 Rajasthan India Banaras Hindu Univ Indian Inst Technol Dept Comp Engn Varanasi 221005 Uttar Pradesh India

The task scheduling problem for multi-core processors is an important algorithm design issue. Dynamic voltage scaling (DVS) is used to reduce the energy consumption of cores. We ponder the problem of task scheduling on a multi-core processor with software controlled DVS where the objective is to reduce the energy consumption. We consider a system with a single multi-core processor with software controlled DVS having a finite set of core speeds and discuss a task scheduling problem associated with it. The problem that we address is to find a minimum energy task schedule for a given set of independent tasks that have to be completed within a given common deadline. We propose a Monte Carlo algorithm of complexity O(t(mp + q + log(t)) + p(t + q)(D-pq + n)) for solving the task scheduling problem and compare it with the optimal algorithm. Here t is the number of tasks, p is the number of cores, q is the number of core speeds, m is an integer parameter that is the number of iterations we should try to get a feasible solution before declaring that no solution is possible, n is an integer parameter that is the number of iterations we should try to reduce the energy consumption when we get a feasible solution, and D is the common deadline of the tasks. (C) 2013 Elsevier Inc. All rights reserved.

关键词： Dynamic voltage scaling Energy efficient scheduling Multi-core processor randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Anycast service model and its QoS routing algorithm

引用

Journal of Central South University 2001年第2期8卷 135-139页

作者： WANG Jian xin, CHEN Song qiao, CHEN Jian er (College of Information Science and Engineering, Central South University, Changsha 410083, China) 1. College of Information Science and Engineering Central South University 410083 Changsha China

In the Internet, a group of replicated servers is commonly used in order to improve the scalability of network service. Anycast service is a new network service that can improve network load distribution and simplify certain applications. In this paper, the authors described a simple anycast service model in the Internet without significant affecting the routing and protocol processing infrastructure that was already in place, and proposed an anycast QoS routing algorithm for this model. The algorithm used randomized method to balance network load and improve its performance. Several new techniques are proposed in the algorithm, first, theminimum hops for each node are used in the algorithm, which are used as metric for computing the probability of possible out links. The metric is pre computed for each node in the network, which can simplify the network complexity and provide the routing process with useful information. Second, randomness is used at the link level and depends dynamically on the routing configuration. This provides great flexibility for the routing process, prevents the routing process from overusing certain fixed routing paths, and adequately balances the delay of the routing path. the authors assess the quality of QoS algorithm in terms of the acceptance ratio on anycast QoS requests, and the simulation results on a variety of network topologies and on various parameters show that the algorithm has good performances and can balance network load effectively.

关键词： QoS anycast service network routing randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Optimal Linear Bernoulli Factories for Small Mean Problems

引用

METHODOLOGY AND COMPUTING IN APPLIED PROBABILITY 2017年第2期19卷 631-645页

作者： Huber, Mark Claremont Mckenna Coll Claremont CA 91711 USA

Suppose a coin with unknown probability p of heads can be flipped as often as desired. A Bernoulli factory for a function f is an algorithm that uses flips of the coin together with auxiliary randomness to flip a single coin with probability f(p) of heads. Applications include perfect sampling from the stationary distribution of certain regenerative processes. When f is analytic, the problem can be reduced to a Bernoulli factory of the form f(p) = C p for constant C. Presented here is a new algorithm that for small values of C p, requires roughly only C coin flips. From information theoretic considerations, this is also conjectured to be (to first order) the minimum number of flips needed by any such algorithm. For large values of C p, the new algorithm can also be used to build a new Bernoulli factory that uses only 80 % of the expected coin flips of the older method. In addition, the new method also applies to the more general problem of a linear multivariate Bernoulli factory, where there are k coins, the kth coin has unknown probability p (k) of heads, and the goal is to simulate a coin flip with probability C (1) p (1)+ai + C (k) p (k) of heads.

关键词： randomized algorithm Near perfect simulation Regenerative processes

来源：评论

学校读者我要写书评

暂无评论

Sharp phase transition for the random-cluster and Potts models via decision trees

引用

ANNALS OF MATHEMATICS 2019年第1期189卷 75-99页

作者： Duminil-Copin, Hugo Raoufi, Aran Tassion, Vincent IHES Bures Sur Yvette France Swiss Fed Inst Technol Zurich Switzerland

We prove an inequality on decision trees on monotonic measures which generalizes the OSSS inequality on product spaces. As an application, we use this inequality to prove a number of new results on lattice spin models and their random-cluster representations. More precisely, we prove that For the Potts model on transitive graphs, correlations decay exponentially fast for beta < beta(c.) For the random-cluster model with cluster weight q >= 1 on transitive graphs, correlations decay exponentially fast in the subcritical regime and the cluster-density satisfies the mean-field lower bound in the supercritical regime. For the random-cluster models with cluster weight q >= 1 on planar quasi-transitive graphs G, p(c)(G)p(c)(G*)/(1 - P-c(G)) (1- p(c)(G*)) = q. As a special case, we obtain the value of the critical point for the square, triangular and hexagonal lattices. (This provides a short proof of a result of Beffara and the first author dating from 2012.) These results have many applications for the understanding of the subcritical (respectively disordered) phase of all these models. The techniques developed in this paper have potential to be extended to a wide class of models including the Ashkin-Teller model, continuum percolation models such as Voronoi percolation and Boolean percolation, super-level sets of massive Gaussian free field, and the random-cluster and Potts models with infinite range interactions.

关键词： percolation model Potts model randomized algorithm sharp threshold exponential decay

来源：评论

学校读者我要写书评

暂无评论

SVD-based algorithms for tensor wheel decomposition

引用

ADVANCES IN COMPUTATIONAL MATHEMATICS 2024年第5期50卷 1-23页

作者： Wang, Mengyu Cui, Honghua Li, Hanyu Chongqing Univ Coll Math & Stat Chongqing Peoples R China Xiamen Univ Wang Yanan Inst Studies Econ Fujian Peoples R China Chongqing Univ Key Lab Nonlinear Anal & its Applicat Minist Educ Chongqing Peoples R China

Tensor wheel (TW) decomposition combines the popular tensor ring and fully connected tensor network decompositions and has achieved excellent performance in tensor completion problem. A standard method to compute this decomposition is the alternating least squares (ALS). However, it usually suffers from slow convergence and numerical instability. In this work, the fast and robust SVD-based algorithms are investigated. Based on a result on TW-ranks, we first propose a deterministic algorithm that can estimate the TW decomposition of the target tensor under a controllable accuracy. Then, the randomized versions of this algorithm are presented, which can be divided into two categories and allow various types of sketching. Numerical results on synthetic and real data show that our algorithms have much better performance than the ALS-based method and are also quite robust. In addition, with one SVD-based algorithm, we also numerically explore the variability of TW decomposition with respect to TW-ranks and the comparisons between TW decomposition and other famous formats in terms of the performance on approximation and compression.

关键词： Tensor wheel decomposition SVD Alternating least squares Deterministic algorithm randomized algorithm Sketching

来源：评论

学校读者我要写书评

暂无评论

ON THE MONTE-CARLO BOOLEAN DECISION TREE COMPLEXITY OF READ-ONCE FORMULAS

引用

RANDOM STRUCTURES & algorithmS 1995年第1期6卷 75-87页

作者： SANTHA, M CNRS URA 410 Université Paris-Sud LRI 91405 Orsay France

In the boolean decision tree model there is at least a linear gap between the Monte Carlo and the Las Vegas complexity of a function depending on the error probability. We prove for a large class of read-once formulae that this trivial speed-up is the best that a Monte Carlo algorithm can achieve. For every formula F belonging to that class we show that the Monte Carlo complexity of F with two-sided error p is (1 - 2p)R(F), and with one-sided error p is (1 - p)R(F), where R(F) denotes the Las Vegas complexity of F. The result follows from a general lower bound that we derive on the Monte Carlo complexity of these formulae. This bound is analoguous to the lower bound due to Saks and Wigderson on their Las Vegas complexity. (C) 1995 John Wiley & Sons, Inc.

关键词： BOOLEAN DECISION TREE randomized algorithm READ-ONCE FORMULA LOWER BOUND

来源：评论

学校读者我要写书评

暂无评论

Survivors in leader election algorithms

引用

STATISTICS & PROBABILITY LETTERS 2013年第12期83卷 2743-2749页

作者： Kalpathy, Ravi Mahmoud, Hosam M. Rosenkrantz, Walter George Washington Univ Dept Stat Washington DC 20052 USA Univ Massachusetts Dept Math & Stat Amherst MA 01003 USA

We consider the number of survivors in a broad class affair leader election algorithms after a number of election rounds. We give sufficient conditions for the number of survivors to converge to a product of independent identically distributed random variables. The number of terms in the product is determined by the round number considered. Each individual term in the product is a limit of a scaled random variable associated with the splitting protocol. The proof is established via convergence (to 0) of the first-order Wasserstein distance from the product limit. In a broader context, the paper is a case study of a class of stochastic recursive equations. We give two illustrative examples, one with binomial splitting protocol (for which we show that a normalized version is asymptotically Gaussian) and one with uniform splitting protocol. (C) 2013 Elsevier B.V. All rights reserved.

关键词： randomized algorithm Leader election Stochastic recurrence Probability metrics Weak convergence

来源：评论

学校读者我要写书评

暂无评论

Disjoint Bases in a Polymatroid

引用

RANDOM STRUCTURES & algorithmS 2009年第4期35卷 418-430页

作者： Calinescu, Gruia Chekuri, Chandra Vondrak, Jan IIT Dept Comp Sci Chicago IL 60616 USA Univ Illinois Dept Comp Sci Urbana IL 61801 USA Princeton Univ Dept Math Princeton NJ 08544 USA

Let f : 2(N) -> Z(+) be a polymatroid (an integer-valued non-decreasing submodular set function with f(empty set) = 0). We call S (subset of) under bar N a base if f (S) = f (N). We consider the problern of finding, a maximum number of disjoint bases;we denote by m* be this base packing number. A simple upper bound on m* is given by k* = max{k : Sigma(i is an element of N)f(A)(i) >= kfa(N), for all A (subset of) under bar N) where f(A)(S) = f (A boolean OR S) - f (A). This upper bound is a natural generalization of the bound for matroids where it is known that m* = k* For polymatroids, we prove that m* >= (1 - o(1))k*/In f (N) and give a randomized polynomial time algorithm to find (1 - o(1))k*/In f (N) disjoint bases, assuming an oracle for f. We also derandomize the algorithm using minwise independent permutations and give a deterministic algorithm that finds (1 - is an element of)k*/In f(N) disjoint bases. The bound we obtain is almost tight because it is known there are polymatroids for which m* < (1 + o(1))k*/In f(N). Moreover it is known that unless NP <(subset of)under bar> DTIME(n(log log n)), for any is an element of > 0, there is no polynomial time algorithm to obtain a (1 + is an element of)/In f(N)-approximation to m*. Our result generalizes and unifies two results in the literature. (C) 2009 Wiley Periodicals, Inc. Random Struct. Alg., 35, 418-430, 2009

关键词： polymatroid integer packing randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：