Geometric separation and exact solutions for the parameterized independent set problem on disk graphs

We consider the parameterized problem, whether for a given set  of n disks (of bounded radius ratio) in the Euclidean plane there exists a set of k non-intersecting disks. For this problem, we expose an algorithm running in time that is—to our knowledge—the first algorithm with running time bounded by an exponential with a sublinear exponent. For λ-precision disk graphs of bounded radius ratio, we show that the problem is fixed parameter tractable with a running time  . The results are based on problem kernelization and a new “geometric ( -separator) theorem” which holds for all disk graphs of bounded radius ratio. The presented algorithm then performs, in a first step, a “geometric problem kernelization” and, in a second step, uses divide-and-conquer based on our new “geometric separator theorem.”     

非参数混合效应模型中的删除诊断

本文考虑了非参数混合模型中的子集删除诊断．在非参数混合模型的框架下,得到了用两种方法所得非参数元素估计的系数矩阵相等,同时用两种方法得到的随机效应预测的系数矩阵也相同．在此等价性的基础上,我们将现有文献中对线性模型的11删除=替代”准则推广至非参数混合模型场合．不仅得到了固定效应的删除诊断公式,还得到了随机效应的删除诊断公式．此外,我们通过模拟数据分析和真实数据分析说明了我们方法的有效性．     

Exploiting structure in quantified formulas

We study the computational problem “find the value of the quantified formula obtained by quantifying the variables in a sum of terms.” The “sum” can be based on any commutative monoid, the “quantifiers” need only satisfy two simple conditions, and the variables can have any finite domain. This problem is a generalization of the problem “given a sum-of-products of terms, find the value of the sum” studied in [R.E. Stearns and H.B. Hunt III, SIAM J. Comput. 25 (1996) 448–476]. A data structure called a “structure tree” is defined which displays information about “subproblems” that can be solved independently during the process of evaluating the formula. Some formulas have “good” structure trees which enable certain generic algorithms to evaluate the formulas in significantly less time than by brute force evaluation. By “generic algorithm,” we mean an algorithm constructed from uninterpreted function symbols, quantifier symbols, and monoid operations. The algebraic nature of the model facilitates a formal treatment of “local reductions” based on the “local replacement” of terms. Such local reductions “preserve formula structure” in the sense that structure trees with nice properties transform into structure trees with similar properties. These local reductions can also be used to transform hierarchical specified problems with useful structure into hierarchically specified problems having similar structure.     

Māl, enunciations, and the prehistory of Arabic algebra

Medieval Arabic algebra books intended for practical training generally have in common a first “book” which is divided into two sections: one on the methods of solving simplified equations and manipulating expressions, followed by one consisting of worked-out problems. By paying close attention to the wording of the problems in the books of al-Khwārizmī, Abū Kāmil, and Ibn Badr, we reveal the different ways the word māl was used. In the enunciation of a problem it is a common noun meaning “quantity,” while in the solution it is the proper noun naming the square of “thing” (shay '). We then look into the differences between the wording of enunciations and equations, which clarify certain problems solved without “thing,” and help explain the development of algebra before the time of al-Khwārizmī.     

Analysis in distribution of two randomized algorithms for finding the maximum in a broadcast communication model

The limit laws of three cost measures are derived of two algorithms for finding the maximum in a single-channel broadcast communication model. Both algorithms use coin flips and comparisons. Besides the ubiquitous normal limit law, the Dickman distribution also appears in a natural way. The method of proof proceeds along the line via the method of moments and the “asymptotic transfers,” which roughly bridges the asymptotics of the “conquering cost of the subproblems” and that of the total cost. Such a general approach has proved very fruitful for a number of problems in the analysis of recursive algorithms.     

Coincidence and common fixed points for hybrid strict contractions without the weakly commuting condition

In this work, we establish new coincidence and common fixed point theorems for hybrid strict contraction maps by dropping the assumption “f is T-weakly commuting” for a hybrid pair (f,T) of multivalued maps in Theorem 3.10 of T. Kamran (2004) [8]. As an application, an invariant approximation result is derived.     

非线性测量误差模型的影响分析

本文对非线性测量误差模型给出了统一的诊断方法,并证明了数据删除模型与均值漂移模型的等价性,由此出发得到了Cook距离、残差、杠杆值等诊断统计量.本文还讨论了非线性测量误差模型的局部影响分析,并给出了一个具体应用实例.推广了Zhao & Lee(1995)的结果.     

Case deletion diagnostics in multilevel models

This paper studies case deletion diagnostics for multilevel models. Using subset deletion, diagnostic measures for identifying influential units at any level are developed for both fixed and random parameters. Two approximate update formulae are derived. The first formula uses one-step approximation, while the second formula also includes the impact of estimating the random parameter. Two examples are used to illustrate the methodology developed.     

Automata and logics over finitely varying functions

We extend some of the classical connections between automata and logic due to Büchi (1960) [5] and McNaughton and Papert (1971) [12] to languages of finitely varying functions or “signals”. In particular, we introduce a natural class of automata for generating finitely varying functions called ’s, and show that it coincides in terms of language definability with a natural monadic second-order logic interpreted over finitely varying functions Rabinovich (2002) [15]. We also identify a “counter-free” subclass of ’s which characterise the first-order definable languages of finitely varying functions. Our proofs mainly factor through the classical results for word languages. These results have applications in automata characterisations for continuously interpreted real-time logics like Metric Temporal Logic (MTL) Chevalier et al. (2006, 2007) [6] and [7].     

Linear multi-secret sharing schemes based on multi-party computation

In multi-secret sharing schemes, publishing shares during the process of reconstructing partial secrets may leak some information of the secrets unrecovered yet. By using a multi-party computation (MPC) protocol, we solve this problem for any linear multi-secret sharing scheme (MSSS). We also show that LMSSS usually involve more complicated reconstruction algorithms than “direct sum” schemes, but from the point of reducing share expansion, the former is preferred.     

Strong bias of group generators: an obstacle to the “product replacement algorithm”

Let G be a finite group. Efficient generation of nearly uniformly distributed random elements in G, starting from a given set of generators of G, is a central problem in computational group theory. In this paper we demonstrate a weakness in the popular “product replacement algorithm,” widely used for this purpose. The main results are the following. Let be the set of generating k-tuples of elements of G. Consider the distribution of the first components of the k-tuples in induced by the uniform distribution over  . We show that there exist infinite sequences of groups G such that this distribution is very far from uniform in two different senses: (1) its variation distance from uniform is >1−ε; and (2) there exists a short word (of length (loglog|G|)^O(k)) which separates the two distributions with probability 1−ε. The class of groups we analyze is direct powers of alternating groups. The methods used include statistical analysis of permutation groups, the theory of random walks, the AKS sorting network, and a randomized simulation of monotone Boolean operations by group operations, inspired by Barrington's work on bounded-width branching programs. The problem is motivated by the product replacement algorithm which was introduced in [Comm. Algebra 23 (1995) 4931–4948] and is widely used. Our results show that for certain groups the probability distribution obtained by the product replacement algorithm has a bias which can be detected by a short straight line program.     

The monopolist’s problem: existence, relaxation, and approximation

We study a variational problem arising from a generalization of an economic model introduced by Rochet and Choné in [5]. In this model a monopolist proposes a set Y of products with price list . Each rational consumer chooses which product to buy by solving a personal minimum problem, taking into account his/her tastes and economic possibilities. The monopolist looks for the optimal price list which minimizes costs, hence maximizes the profit. This leads to a minimum problem for functionals (the “pessimistic cost expectation”) and (the “optimistic cost expectation”), which are in turn defined through two nested variational problems. We prove that the minimum of exists and coincides with the infimum of . We also provide a variational approximation of by smooth functionals defined in finite dimensional Euclidean spaces.Received: 2 March 2004, Accepted: 19 October 2004, Published online: 22 December 2004Mathematics Subject Classification (2000): 49J45, 91B     

On Marcinkiewicz Integral Operators with Rough Kernels

This paper is devoted to the study on the L^p-mapping properties of Marcinkiewicz integral operators with rough kernels along “polynomial curves” on The boundedness of the Marcinkiewicz integrals for some fixed 1 < p < ∞ are obtained under some size conditions, which essentially improve or extend some well-known results.     

A viscosity of extragradient approximation method for finding equilibrium problems, variational inequalities and fixed point problems for nonexpansive mappings

In this paper, we investigate the problem for finding the set of solutions for equilibrium problems, the set of solutions of the variational inequalities for k-Lipschitz continuous mappings and fixed point problems for nonexpansive mappings in a Hilbert space. We introduce a new viscosity extragradient approximation method which is based on the so-called viscosity approximation method and extragradient method. We show that the sequence converges strongly to a common element of the above three sets under some parameters controlling conditions. Finally, we utilize our results to study some convergence problems for finding the zeros of maximal monotone operators. Our results are generalization and extension of the results of Kumam [P. Kumam, Strong convergence theorems by an extragradient method for solving variational inequalities and equilibrium problems in a Hilbert space, Turk. J. Math. 33 (2009) 85–98], Wangkeeree [R. Wangkeeree, An extragradient approximation method for equilibrium problems and fixed point problems of a countable family of nonexpansive mappings, Fixed Point Theory and Applications, 2008, Article ID 134148, 17 pages, doi:10.1155/2008/134148], Yao et al. [Y. Yao, Y.C. Liou, R. Chen, A general iterative method for an finite family of nonexpansive mappings, Nonlinear Analysis 69 (5–6) (2008) 1644–1654], Qin et al. [X. Qin, M. Shang, Y. Su, A general iterative method for equilibrium problems and fixed point problems in Hilbert spaces, Nonlinear Analysis (69) (2008) 3897–3909], and many others.     

On Fraïssé’s conjecture for linear orders of finite Hausdorff rank

We prove that the maximal order type of the wqo of linear orders of finite Hausdorff rank under embeddability is φ₂(0), the first fixed point of the ε-function. We then show that Fraïssé’s conjecture restricted to linear orders of finite Hausdorff rank is provable in  +“φ₂(0) is well-ordered” and, over , implies  +“φ₂(0) is well-ordered”.     

Multiway Dependence in Exponential Family Conditional Distributions

Conditionally specified statistical models are frequently constructed from one-parameter exponential family conditional distributions. One way to formulate such a model is to specify the dependence structure among random variables through the use of a Markov random field (MRF). A common assumption on the Gibbsian form of the MRF model is that dependence is expressed only through pairs of random variables, which we refer to as the “pairwise-only dependence” assumption. Based on this assumption, J. Besag (1974, J. Roy. Statist. Soc. Ser. B36, 192–225) formulated exponential family “auto-models” and showed the form that one-parameter exponential family conditional densities must take in such models. We extend these results by relaxing the pairwise-only dependence assumption, and we give a necessary form that one-parameter exponential family conditional densities must take under more general conditions of multiway dependence. Data on the spatial distribution of the European corn borer larvae are fitted using a model with Bernoulli conditional distributions and several dependence structures, including pairwise-only, three-way, and four-way dependencies.     

Computing Eigenvalues of Lommel-Type Equations by the Sampling Method

Using the semiclassical approximation for where and as , we shall show that theeigenvalues are the zeros of a certain function in a Paley–Wienerspace, which allows us to use the Whittaker–Shannon–Kotelnikovsampling theorem to approximate the eigenvalues. We show how thedistribution of the eigenvalues depends on the asymptotics of thecoefficients and as . After abrief discussion on the truncation error, numerical examples are provided.     

Some Asymptotic Formulae for Gaussian Distributions

This paper considers asymptotic expansions of certain expectations which appear in the theory of large deviation for Gaussian random vectors with values in a separable real Hilbert space. A typical application is to calculation of the “tails” of distributions of smooth functionals,p(r)=P{Φ(r⁻¹ξ)0},r→∞, e.g., the probability that a centered Gaussian random vector hits the exterior of a large sphere surrounding the origin. The method provides asymptotic formulae for the probability itself and not for its logarithm in a situation, where it is natural to expect thatp(r)=c′r^D exp{−c″r²}. Calculations are based on a combination of the method of characteristic functionals with the Laplace method used to find asymptotics of integrals containing a fast decaying function with “small” support.     

Stochastic Bounds for the Sparre Andersen Process

In this paper we define two stochastic processes that are smaller and greater in usual stochastic order than the Sparre Andersen process. We derive, as a consequence, upper and lower bounds of its marginal distributions, and of the distributions of its first passage times above fixed thresholds. We also present a generalization of these stochastic bounds for risk processes perturbed by diffusion.AMS 2000 Subject Classification: 60K10, 60E15Partially supported by the italian PRIN-Cofin 2004 “Stochastic models in mathematical finance” (F. Pellerey) and PRIN-Cofin 2003 “Numerical, analytical and simulation methods with reference to reliability in neuronal signal transmission” (C. Zucca).