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

probabilistic analysis OF K-DIMENSIONAL PACKING algorithms

INFORMATION PROCESSING LETTERS 1995年第1期55卷 17-24页

作者： HONG, DW LEUNG, JYT UNIV NEBRASKA DEPT COMP SCI & ENGNLINCOLNNE 68588

In the k-dimensional packing problem, we are given a set I=(b(1), b(2),..., b(n)) of k-dimensional boxes and a k-dimensional box B with unit length in each of the first k-1 dimensions and unbounded length in the kth dimension. Each box b(i) is represented by a k-tuple b(i) = (x(i)((1)),..., x(i)((k-1)), x(i)((k))) is an element of (0, 1](k-1) X (0, infinity), where x((j)) denotes its length in the jth dimension, 1 less than or equal to j less than or equal to k. We are asked to find a packing of I into B such that each box is packed orthogonally and oriented in all k dimensions and such that the height in the kth dimension of the packing is minimized. The k-dimensional packing problem is known to be NP-hard for each k > 1. In this note, we study the average-case behavior of a class of algorithms, which includes any optimal algorithm and an on-line algorithm. Let A denote an algorithm in this class. Assume that b(1), b(2),..., b(n) are independent, identically distributed according to a distribution F(x((1)),.., x((k-1)), x((k))) over (0, 1](k-1) X (0, infinity), and the marginal distribution F-k of x((k)) satisfies the property that there is a positive number Lu at which the moment generating function M(Fk)(t) has a finite value C-a > 0. It is shown that for each given s > 0, there is an N-s,N-F > 0 such that for all n greater than or equal to N-s,N-F, Pr(\A(b(1),..., b(n))/n - Gamma\>s) < (2 + C-a)exp(-(sa/3)(2/3)n(1/3)), where Gamma = lim(n-->infinity)E[A(b(1),..., b(n))]/n and A(b(1),..., b(n)) denotes the height in the kth dimension of the packing of (b(1),..., b(n)) produced by A.

关键词： probabilistic analysis of algorithms NP-HARD K-DIMENSIONAL PACKING ONLINE ALGORITHM

来源：评论

学校读者我要写书评

暂无评论

On average case complexity of SAT for symmetric distribution

引用

Journal of Logic and Computation 1995年第1期5卷 71-71页

作者： Makowsky, J. Sharell, A. Faculty of Computer Science Technion-Israel Institute of Technology Haifa Israel Laboratoire de Recherche en Informatique Université 91405 Orsay Paris-Sud France

We investigate in this paper ‘natural’ distributions for the satisfiability problem (SAT) of prepositional logic, using concepts previously introduced by to study the average-case complexity of NP-complete problems. Gurevich showed that a problem with aflatdistribution is not DistNP complete (for deterministic reductions), unless DEXPTIme ≠ NEXPTlme. We express the known results concerningfixed sizeandfixed densitydistributions for CNF in the framework of average-case complexity and show that all these distributions are flat. We introduce the family of symmetric distributions, which generalizes those mentioned before, and show that bounded symmetric distributions on ordered tuples of clauses (CNFTupIes) and onk-CNF (sets ofk-literal-clauses), are flat. This eliminates all these distributions as candidates for ‘provably hard’ (i.e. DistNP complete) distributions for SAT, if one considers only deterministic reductions. Given the (presumed) naturalness and generality of these distributions, this result supports evidence that (at least polynomial-time, no-error) randomized reductions are appropriate in average-case complexity. We also observe, that there are non-flat distributions for which SAT is polynomial on the average, but that this is due to the particular choice of the size functions. Finally, Chváal and Szemerédi have shown that for certain fixed size distributions (which are also flat) resolution is exponential for almost all instances. We use this to show that every resolution algorithm will need at least exp(nα) (for any 0 ≤ α ≤ 1) time on the average. In other words, resolution-based algorithms will not establish that SAT, with these distributions, is in AverP.

关键词： Average case complexity probabilistic analysis of algorithms Resolution Satisfiability problem

来源：评论

学校读者我要写书评

暂无评论

Fast Approximate MaximumA PosterioriRestoration of Multicolour Images

引用

Journal of the Royal Statistical Society: Series B (Statistical Methodology) 1995年第3期57卷 485-500页

作者： Pablo A. Ferrari Arnoldo Frigessi Paula Gonzaga de Sá Universidade de São Paulo Brazil Terza Università di Roma and Consiglio Nazionale delle Ricerche Rome Italy Université Catholique de Louvain Louvain-la-Neuve Belgium

We propose a new algorithm for the approximation of the maximum a posteriori (MAP) restoration of noisy images. The image restoration problem is considered in a Bayesian setting. We assume as prior distribution multicolour Markov random fields on a graph whose main restriction is the presence of only pairwise site interactions. The noise is modelled as a Bernoulli field. Computing the mode of the posterior distribution is NP complete, i.e. can (very likely) be done only in a time exponential in the number of sites of the underlying graph. Our algorithm runs in polynomial time and is based on the coding of the colours. It produces an image with the following property: either a pixel is coloured with one of the possible colours or it is left blank. In the first case we prove that this is the colour of the site in the exact MAP restoration. The quality of the approximation is then measured by the number of sites being left blank. We assess the performance of the new algorithm by numerical experiments on the simple three-colour Potts model. More rigorously, we present a probabilistic analysis of the algorithm. The results indicate that the approximation is quite often sufficiently good for the interpretation of the image.

关键词： bayesian image restoration coding ford–fulkerson's max-flow algorithm markov random fields probabilistic analysis of algorithms simulated annealing

来源：评论

学校读者我要写书评

暂无评论

probabilistic analysis OF NETWORK FLOW algorithms

引用

MATHEMATICS OF OPERATIONS RESEARCH 1993年第1期18卷 71-97页

作者： KARP, RM MOTWANI, R NISAN, N STANFORD UNIV DEPT COMP SCI STANFORD CA 94305 USA HEBREW UNIV JERUSALEM JERUSALEM ISRAEL

This paper is concerned with the design and probabilistic analysis of algorithms for the maximum-flow problem and capacitated transportation problems. These algorithms run in linear time and, under certain assumptions about the probability distribution of edge capacities, obtain an optimal solution with high probability. The design of our algorithms is based on the following general method, which we call the mimicking method, for solving problems in which some of the input data are deterministic and some are random with a known distribution: 1. Replace each random variable in the problem by its expectation;this gives a deterministic problem instance that has a special form, making it particularly easy to solve;2. Solve the resulting deterministic problem instance;3. Taking into account the actual values of the random variables, mimic the solution of the deterministic instance to obtain a near-optimal solution to the original problem;4. Fine-tune this suboptimal solution to obtain an optimal solution. We present linear time algorithms to compute a feasible flow in directed and undirected capacitated transportation problem instances. The algorithms are shown to be successful with high probability when the probability distribution of the input data satisfies certain assumptions. We also consider the maximum flow problem with multiple sources and sinks. We show that with high probability the minimum cut isolates either the sources or the sinks, and we give a linear-time algorithm that produces a maximum flow with high probability.

关键词： probabilistic analysis of algorithms MAXIMUM FLOW PROBLEM TRANSPORTATION PROBLEM

来源：评论

学校读者我要写书评

暂无评论

FAST NEAREST-NEIGHBOR SEARCH IN DISSIMILARITY SPACES

引用

IEEE TRANSACTIONS ON PATTERN analysis AND MACHINE INTELLIGENCE 1993年第9期15卷 957-962页

作者： FARAGO, A LINDER, T LUGOSI, G Tech. Univ. of Budapest Hungary

A fast nearest-neighbor algorithm is presented. It works in general spaces where the known cell (bucketing) techniques cannot be implemented for various reasons, such as the absence of coordinate structure and/or high dimensionality. The central idea has already appeared several times in the literature with extensive computer simulation results. This paper provides an exact probabilistic analysis or this family of algorithms, proving its O(1) asymptotic average complexity measured in the number of dissimilarity calculations.

关键词： AVERAGE COMPLEXITY DISSIMILARITY SPACES FAST NEAREST-NEIGHBOR SEARCH PATTERN RECOGNITION probabilistic analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

INTRODUCTION TO THE INTERFACE OF PROBABILITY AND algorithms

引用

STATISTICAL SCIENCE 1993年第1期8卷 3-9页

作者： ALDOUS, D STEELE, JM UNIV CALIF BERKELEY DEPT STATBERKELEYCA 94720 UNIV PENN WHARTON SCHDEPT STATPHILADELPHIAPA 19104

Probability and algorithms enjoy an almost boisterous interaction that has led to an active, extensive literature that touches fields as diverse as number theory and the design of computer hardware. This article offer... 详细信息

关键词： ASSIGNMENT PROBLEM probabilistic algorithms probabilistic analysis of algorithms RANDOMIZATION

来源：评论

学校读者我要写书评

暂无评论

ON THE POWER OF ADAPTIVE INFORMATION FOR FUNCTIONS WITH SINGULARITIES

引用

MATHEMATICS OF COMPUTATION 1992年第197期58卷 285-304页

作者： WASILKOWSKI, GW GAO, F UNIV BRITISH COLUMBIA DEPT COMP SCIVANCOUVER V6T 1W5BCCANADA

We study from a probabilistic viewpoint the problem of locating singularities of functions using function evaluations. We show that, under the assumption of a Wiener-like probability distribution on the class of singular functions, an adaptive algorithm can locate a singular point accurately with only a small probability of failure. As an application, we show that an integration algorithm that adaptively locates a singular point is probabilistically superior to nonadaptive algorithms.

关键词： PIECEWISE REGULAR FUNCTIONS APPROXIMATING DETECTING SINGULAR POINTS probabilistic analysis of algorithms ADAPTIVE (SEQUENTIAL) algorithms ADAPTIVE QUADRATURES

来源：评论

学校读者我要写书评

暂无评论

probabilistic analysis OF A GROUPING ALGORITHM

引用

ALGORITHMICA 1991年第2期6卷 192-206页

作者： WONG, DF REINGOLD, EM UNIV ILLINOIS DEPT COMP SCIURBANAIL 61801

We study the grouping by swapping problem, which occurs in memory compaction and in computing the exponential of a matrix. In this problem we are given a sequence of n numbers drawn from {0,1,2,..., m-1} with repetitions allowed;we are to rearrange them, using as few swaps of adjacent elements as possible, into an order such that all the like numbers are grouped together. It is known that this problem is NP-hard. We present a probabilistic analysis of a grouping algorithm called MEDIAN that works by sorting the numbers in the sequence according to their median positions. Our results show that the expected behavior of MEDIAN is within 10% of optimal and is asymptotically optimal as n/m-->infinity or as n/m-->0.

关键词： probabilistic analysis of algorithms GROUPING BY SWAPPING MEMORY COMPACTION EXPONENTIAL OF A MATRIX

来源：评论

学校读者我要写书评

暂无评论

probabilistic analysis OF AN ALGORITHM FOR SOLVING THE K-DIMENSIONAL ALL-NEAREST-NEIGHBORS PROBLEM BY PROJECTION

引用

BIT 1991年第4期31卷 558-565页

作者： BARTLING, F HINRICHS, K UNIV GESAMTHSCH SIEGEN FACHBEREICH INFORMAT 12W-5900 SIEGENGERMANY UNIV MUNSTER FACHBEREICH INFORMAT 15W-4400 MUNSTERGERMANY

A well-known simple heuristic algorithm for solving the all-nearest-neighbors problem in the k-dimensional Euclidean space E(k), k > 1, projects the given point set S onto the x-axis. For each point q is-an-element-of S a nearest neighbor in S under any L(p)-metric (1 less-than-or-equal-to p less-than-or-equal-to infinity) is found by sweeping from q into two opposite directions along the x-axis. If delta(q) denotes the distance between q and its nearest neighbor in S the sweep process stops after all points in a vertical 2-delta(q)-slice centered around q have been examined. We show that this algorithm solves the all-nearest-neighbors problem for n independent and uniformly distributed points in the unit cube [0, 1]k in THETA(n2 -1/k) expected time, while its worst-case performance is THETA(n2).

关键词： COMPUTATIONAL GEOMETRY PLANE-SWEEP ALGORITHM PROXIMITY PROBLEMS ALL-NEAREST-NEIGHBOR PROBLEM probabilistic analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

The average quality of greedy-algorithms for the Subset-Sum-Maximization Problem

引用

ZOR - Methods and Models of Operations Research 1991年第2期35卷 113-149页

作者： Borgwardt, K.H. Tremel, B. Institut für Mathematik Universität Augsburg Augsburg 8900 Memminger Str. 6 Germany Röckingen 8821 Mittelburger Weg 6

This paper deals with the quality of approximative solutions for the Subset-Sum-Maximization-Problem maximize {Mathematical expression} subject to {Mathematical expression} where a_l,...,a_n,bεR⁺ and x_l,...x_nε{0,1}. produced by certain heuristics of a Greedy-type. Every heuristic under consideration realizes a feasible solution (x₁, ..., x_n) whose objective value is less or equal the optimal value, which is of course not greater than b. We use the gap between capacity b and realized value as an upper bound for the error made by the heuristic and as a criterion for quality. Under the stochastic model:a₁, ..., a_n, b independent, a₁...,a_n uniformly distributed on [0, 1], b uniformly distributed on [0, n] we derive the gap-distributions and the expected size of the gaps. The analyzed algorithms include four algorithms which can be done in linear time and four heuristics which require sorting, which means that they are done in O(nl nn) time. © 1991 Physica-Verlag.

关键词： Combinatorial Optimization Knapsack-Problems probabilistic analysis of algorithms Probability Theory

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：