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

hermiter: R package for sequential nonparametric estimation

COMPUTATIONAL STATISTICS 2024年第3期39卷 1127-1163页

作者： Stephanou, Michael Varughese, Melvin Rand Merchant Bank Johannesburg South Africa Univ Cape Town Cape Town South Africa Univ Western Australia Perth Australia

This article introduces the R package hermiter which facilitates estimation of univariate and bivariate probability density functions and cumulative distribution functions along with full quantile functions (univariate) and nonparametric correlation coefficients (bivariate) using Hermite series based estimators. The algorithms implemented in the hermiter package are particularly useful in the sequential setting (both stationary and non-stationary) and one-pass batch estimation setting for large data sets. In addition, the Hermite series based estimators are approximately mergeable allowing parallel and distributed estimation.

关键词： Fast Kendall Tau Fast quantiles Fast Spearman Rho Hermite series estimators Online algorithms sequential algorithms

来源：评论

学校读者我要写书评

暂无评论

Minimum number of queries for an adaptive liar search game with small sets

引用

DISCRETE OPTIMIZATION 2013年第4期10卷 233-240页

作者： Meng, Kun Lin, Chuang Yang, Yang Tsinghua Univ Dept Comp Sci & Technol Beijing 100084 Peoples R China Univ Sci & Technol Beijing Sch Comp & Commun Engn Beijing 100083 Peoples R China

To detect an unknown element x* from a finite set S = {1, 2, ... , n} by asking group-testing queries is a classical combinatorial optimization problem. We consider a variation of the problem, what we call the liar search game with small sets vertical bar n, e, <= k vertical bar and formulate it as follows: two players, say Paul and Carole, fix integers k >= 1, m > 0 and e >= 0 beforehand. Paul asks size restricted queries to find x*: "Is x* in A?", where A subset of S and vertical bar A vertical bar <= k. Carole answers them with "Yes" or "No" to tell whether x* belongs to A or not. Carole is permitted to lie at most e times. Paul wins if he finds x* within m rounds;otherwise Carole wins. Our goal is to determine the minimum value of m to assure Paul to win. Let f (n, e, <= k) = min{m vertical bar Paul wins the game [n, e, <= k] for the given integer m}. In this paper, we consider the sequential algorithms of the above game and obtain a tight bound L-upper(n, 1, <= k) such that f (n, 1, <= k) <= L-upper(n, 1, <= k) <= f (n, 1, <= k) + 1, and the exact value off (n, 1, <= k) for (1) n <= 2k + 1 and (2) n >= k(2) except for the case n = 15 and k = 3. Moreover, in the end of this paper, we conjecture the exact value off (n, 1, <= k) for general case and verify its correctness for k = infinity. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Liar search games sequential algorithms Small sets Worst-case

来源：评论

学校读者我要写书评

暂无评论

SKELETONS AND PERCEPTUAL GRAPHS

引用

SIGNAL PROCESSING 1989年第4期16卷 335-363页

作者： MEYER, F Centre de Morphologie Mathématique E.M.P. 35 rue St Honoré 77300 Fontainebleau France

Based on the notion of homotopy, a complete theory of the skeleton in digital spaces is given. We derive from it several very fast and efficient algorithms for constructing the skeleton (sequential or contour following algorithms. In this way we obtain easily, for all types of digital grids, all transformations which belong to the same family as the skeleton: binary or grey tone skeletons, euclidian or geodesic skeletons, minimal skeletons or perceptual graphs, conditional bisectors, etc. The properties of the resulting skeleton make it a good candidate for being the correct discretization of the skeletons in the continuous plane. Zusammenfassung Eine vollständige Theorie des digitalen Skelettes wird dargelegt, die sich auf das Homotopie Konzept stütz. Davon werden mehrere sehr schnelle gleichwertige Algorithmen für die Skelett Erzeugung abgeleitet (sequentielle oder grenzenfolgende Algorithmen). Auf diese Weise ist es einfach, alle benachbarten Transformationen zu vollziehen, und das ganz unabhängig des benutzten digitalen Gitters: euklidische oder geodesische Skelette, binäre oder grauwert Skelette, minimale Skelette oder Gabriel Graphe, bedingte Halbierungslinien, usw. Die Eigenschaften des erzeugten Skelettes sind dermassen gut, das wir die Überzeugung haben, daß es sich da um die richtige Diskretisierung des Skelettes im kontinuierlichen Raum handelt.

关键词： Skeleton perceptual graph conditional bisector grey-tone images sequential algorithms crest-points upstream

来源：评论

学校读者我要写书评

暂无评论

THEORETICAL ESTIMATES OF BULK SPECIFIC DEPOSIT IN DEEP BED FILTERS

引用

WATER RESEARCH 1993年第3期27卷 377-387页

作者： OJHA, CSP GRAHAM, NJD IMPERIAL COLL SCI TECHNOL & MED DEPT CIVIL ENGNLONDON SW7 2BUENGLAND

The evaluation of bulk specific deposit values forms an integral part of deep bed filtration modelling. As the observations in filtration experiments are generally restricted to the monitoring of headloss and filtrate concentration (in mass units), estimates of only absolute specific deposit values (m/v) are possible. In many previous studies, a term known as the ''bulk factor'' is incorporated into the modelling of the filtration process such that the product of the bulk factor with the absolute specific deposit (m/v), gives an estimate of the bulk specific deposit (v/v). In these investigations the bulk factor is treated as constant. Alternatively, other authors have obtained the variation of the bulk factor with the absolute specific deposit by using Kozeny's headloss model. Thus, it can be seen that so far the process of obtaining a particular variation of the bulk factor and its subsequent use in the modelling of a filtration process has not been adequately considered. The present study presents a novel approach based on the development of sequential decision-making algorithms. It is concluded that this approach has the advantages of being computationally more efficient and avoids the need to assume a headloss model.

关键词： ABSOLUTE SPECIFIC DEPOSIT BULK FACTOR BULK SPECIFIC DEPOSIT FILTRATION MODELING DEEP BED FILTRATION HEADLOSS sequential algorithms

来源：评论

学校读者我要写书评

暂无评论

PARALLEL COMPUTATION OF 2-POINT BOUNDARY-VALUE-PROBLEMS VIA PARTICULAR SOLUTIONS

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 1993年第1期79卷 5-29页

作者： MIELE, A WANG, T 1. Aero-Astronautics Group Rice University Houston Texas

Nonlinear two-point boundary-value problems (TPBVP) can be reduced to the iterative solution of a sequence of linear problems by means of quasilinearization techniques. Therefore, the efficient solution of linear problems is the key to the efficient solution of nonlinear problems. Among the techniques available for solving linear two-point boundary-value problems, the method of particular solutions (MPS) is particularly attractive in that it employs only one differential system, the original nonhomogeneous system, albeit with different initial conditions. This feature of MPS makes it ideally suitable for implementation on parallel computers in that the following requirements are met: the computational effort is subdivided into separate tasks (particular solutions) assigned to the different processors;the tasks have nearly the same size;there is little intercommunication between the tasks. For the TPBVP, the speedup achievable is of O(n), where n is the dimension of the state vector, hence relatively modest for the differential systems of interest in trajectory optimization and guidance. This being the case, we transform the TPBVP into a multi-point boundary-value problem (MPBVP) involving m time subintervals, with m-l continuity conditions imposed at the interface of contiguous subintervals. For the MPBVP, the speedup achievable is of O(mn), hence substantially higher than that achievable for the TPBVP. It reduces to O(m) if the parallelism is implemented only in the time domain and not in the state domain. A drawback of the multi-point approach is that it requires the solution of a large linear algebraic system for the constants of the particular solutions. This drawback can be offset by exploiting the particular nature of the interface conditions: if the vector of constants for the first subinterval is known, the vector of constants for the subsequent subintervals can be obtained with linear transformations. Using decomposition techniques together with the discret

关键词： 2-POINT BOUNDARY-VALUE PROBLEMS MULTIPOINT BOUNDARY-VALUE PROBLEMS MODIFIED QUASI-LINEARIZATION ALGORITHM METHOD OF PARTICULAR SOLUTIONS sequential algorithms PARALLEL algorithms, PARALLEL COMPUTATION TRAJECTORY OPTIMIZATION TRAJECTORY GUIDANCE

来源：评论

学校读者我要写书评

暂无评论

The expressive power of abstract-state machines

引用

COMPUTING AND INFORMATICS 2003年第3-4期22卷 209-219页

作者： Reisig, W Humboldt Univ Inst Informat D-10099 Berlin Germany

Conventional computation models assume symbolic representations of states and actions. Gurevich's "Abstract-State Machine" model takes a more liberal position: Any mathematical structure may serve as a state. This results in,:a computational model that is more powerful and more universal than standard computation models" [5]. We characterize the Abstract-State Machine model as a special class of transition systems that widely extends the class of "computable" transition systems. This characterization is based on a fundamental Theorem of Y. Gurevich.

关键词： specification technique expressive power computation models sequential algorithms transition systems Abstract State Machines

来源：评论

学校读者我要写书评

暂无评论

THE NECESSARY AND SUFFICIENT CONDITION FOR THE WORST-CASE MALE OPTIMAL STABLE MATCHING

引用

INFORMATION PROCESSING LETTERS 1990年第5期34卷 261-263页

作者： KUO, RT TSENG, SS NATL CHIAO TUNG UNIV INST COMP & INFORMAT SCIHSINCHU 30050TAIWAN

The purpose of this paper is to consider the worst-case choice for the sequential stable matching problem. We give the necessary and sufficient condition for the worst-case execution, which leads the sequential stable matching algorithm to take the maximum number of proposals. We then point out that the probability that the worst-case execution occurs when a sequential stable matching algorithm is employed is extremely small.

关键词： Stable matching problem worst-case execution sequential algorithms

来源：评论

学校读者我要写书评

暂无评论

FORWARD-BACKWARD-HALF FORWARD ALGORITHM FOR SOLVING MONOTONE INCLUSIONS

引用

SIAM JOURNAL ON OPTIMIZATION 2018年第4期28卷 2839-2871页

作者： Briceno-Arias, Luis M. Davis, Damek Univ Tecn Federico Santa Maria Dept Math Santiago Chile Cornell Univ Sch Operat Res & Informat Engn Ithaca NY 14850 USA

Tseng's algorithm finds a zero of the sum of a maximally monotone operator and a monotone continuous operator by evaluating the latter twice per iteration. In this paper, we modify Tseng's algorithm for finding a zero of the sum of three operators, where we add a cocoercive operator to the inclusion. Since the sum of a cocoercive and a monotone-Lipschitz operator is monotone and Lipschitz, we could use Tseng's method for solving this problem, but implementing both operators twice per iteration and without taking into advantage the cocoercivity property of one operator. Instead, in our approach, although the continuous monotone operator must still be evaluated twice, we exploit the cocoercivity of one operator by evaluating it only once per iteration. Moreover, when the cocoercive or continuous-monotone operators are zero it reduces to Tseng's algorithm or forward-backward splittings, respectively, unifying in this way both algorithms. In addition, we provide a preconditioned version of the proposed method including non-self-adjoint linear operators in the computation of resolvents and the single-valued operators involved. This approach allows us to also extend previous variable metric versions of the Tseng and forward-backward methods and simplify their conditions on the underlying metrics. We also exploit the case in which non-self-adjoint linear operators are triangular by blocks in the primal-dual product space for solving primal-dual composite monotone inclusions, obtaining Gauss-Seidel-type algorithms which generalize several primal-dual methods available in the literature. Finally we explore applications to the obstacle problem, empirical risk minimization, distributed optimization, and nonlinear programming and we illustrate the performance of the method via some numerical simulations.

关键词： convex optimization forward-backward splitting monotone operator theory sequential algorithms Tseng's splitting

来源：评论

学校读者我要写书评

暂无评论

The knapsack sharing problem: An exact algorithm

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2002年第1期6卷 35-54页

作者： Hifi, M Sadfi, S Univ Paris 01 Maison Sci Econ CERMSEM F-75647 Paris 13 France Univ Versailles PRiSM F-78035 Versailles France Univ Paris 11 Ctr Orsay LRI CNRSURA 410 F-91405 Orsay France

In this paper, we propose an exact algorithm for the knapsack sharing problem. The proposed algorithm seems quite efficient in the sense that it solves quickly some large problem instances. The problem is decomposed into a series of single constraint knapsack problems;and by applying the dynamic programming and another strategy, we solve optimally the original problem. The performance of the exact algorithm is evaluated on a set of medium and large problem instances (a total of 240 problem instances). This algorithm is parallelizable and this is one of its important feature.

关键词： combinatorial optimization knapsack sharing dynamic programming sequential algorithms

来源：评论

学校读者我要写书评

暂无评论

Optimal and nearly optimal algorithms for approximating polynomial zeros

引用

COMPUTERS & MATHEMATICS WITH APPLICATIONS 1996年第12期31卷 97-138页

作者： Pan, VY Department of Mathematics and Computer Science Lehman College City University of New York Bronx NY 10468 U.S.A.

We substantially improve the known algorithms for approximating all the complex zeros of an n(th) degree polynomial p(x). Our new algorithms save both Boolean and arithmetic sequential time, versus the previous best algorithms of Schonhage [1], Pan [2], and Neff and Pelf [3]. In parallel (NC) implementation, we dramatically decrease the number of processors, versus the parallel algorithm of Neff [4], which was the only NC algorithm known for this problem so far. Specifically, under the simple normalization assumption that the variable a: has been scaled so as to confine the zeros of p(x) to the unit disc {x : \x\ less than or equal to 1}, our algorithms (which promise to be practically effective) approximate all the zeros of p(a) within the absolute error bound 2(-b), by using order of n arithmetic operations and order of (b + n)n(2) Boolean (bitwise) operations (in both cases up to within polylogarithmic factors). The algorithms allow their optimal (work preserving) NC parallelization, so that they can be implemented by using polylogarithmic time and the orders of n arithmetic processors or (b + n)n(2) Boolean processors. All the cited bounds on the computational complexity are within polylogarithmic factors from the optimum (in terms of n and b) under both arithmetic and Boolean models of computation (in the Boolean case, under the additional (realistic) assumption that n = O(b)).

关键词： complex polynomial zeros approximation polynomial factorization parallel algorithms computational complexity sequential algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：