An approximation ratio for biclustering

The problem of biclustering consists of the simultaneous clustering of rows and columns of a matrix such that each of the submatrices induced by a pair of row and column clusters is as uniform as possible. In this paper we approximate the optimal biclustering by applying one-way clustering algorithms independently on the rows and on the columns of the input matrix. We show that such a solution yields a worst-case approximation ratio of under L₁-norm for 0-1 valued matrices, and of 2 under L₂-norm for real valued matrices.     

Conditional fault hamiltonian connectivity of the complete graph

A path in G is a hamiltonian path if it contains all vertices of G. A graph G is hamiltonian connected if there exists a hamiltonian path between any two distinct vertices of G. The degree of a vertex u in G is the number of vertices of G adjacent to u. We denote by δ(G) the minimum degree of vertices of G. A graph G is conditional k edge-fault tolerant hamiltonian connected if G−F is hamiltonian connected for every F⊂E(G) with |F|?k and δ(G−F)?3. The conditional edge-fault tolerant hamiltonian connectivity is defined as the maximum integer k such that G is k edge-fault tolerant conditional hamiltonian connected if G is hamiltonian connected and is undefined otherwise. Let n?4. We use Kn to denote the complete graph with n vertices. In this paper, we show that for n∉{4,5,8,10}, , , , and .     

An upper bound on the sample complexity of PAC-learning halfspaces with respect to the uniform distribution

We show that halfspaces in n dimensions can be PAC-learned with respect to the uniform distribution with accuracy ε and confidence δ using examples.     

Package for calculations and simplifications of expressions with Dirac matrices (MatrixExp)

This paper describes a package for calculations of expressions with Dirac matrices. Advantages over existing similar packages are described. MatrixExp package is intended for simplification of complex expressions involving γ-matrices, providing such tools as automatic Feynman parameterization, integration in d-dimensional space, sorting and grouping of results in a given order. Also, in comparison with the existing similar package Tracer, the presented package MatrixExp has more enhanced input possibility. User-available functions of MatrixExp package are described in detail. Also an example of calculation of Feynman diagram for process b→sγg with application of functions of MatrixExp package is presented.

Program summary

Title of program:MatrixExpCatalogue identifier:ADWBProgram summary URL:http://cpc.cs.qub.ac.uk/summaries/ADWBProgram obtainable from:CPC Program Library, Queen's University of Belfast, N. IrelandLicensing provisions:noneProgramming language:MATHEMATICAComputer:PC PentiumOperating system:WindowsNo. of lines in distributed program, including test data, etc.: 1551No. of bytes in distributed program, including test data, etc.: 16 040Distribution format:tar.gzRAM:loading the package uses approx. 3 500 000 bytes of RAM. However memory required for calculations depends heavily on the expressions in the view, as the package uses recursive functions, and MATHEMATICA dynamically allocates memory. Package has been tested to work on PC Pentium II 233 MHz with 128 Mb of memory calculating typical diagrams of contemporary calculations.Nature of problem:Feynman diagram calculation, simplification of expressions with γ-matricesSolution method:Analytic transformations, dimensional regularization, Feynman parameterizationRestrictions:MatrixExp package works only with single line of expressions (G[l1,]), in contrast to the Tracer package that works with multiple lines, i.e., the following is possible in Tracer, but not in MatrixExp: G[l1,]**G[l2,]**G[l3,], which will return the result of G[l1,]**G[l1,]**G[l1,]….Unusual features:noneRunning time:Seconds for expressions with several different γ-matrices on Pentium IV 1.8 GHz and of the order of a minute on Pentium II 233 MHz. Calculation times rise with the number of matrices.     

GeD spline estimation of multivariate Archimedean copulas

A new multivariate Archimedean copula estimation method is proposed in a non-parametric setting. The method uses the so-called Geometrically Designed splines (GeD splines) to represent the cdf of a random variable W_θ, obtained through the probability integral transform of an Archimedean copula with parameter θ. Sufficient conditions for the GeD spline estimator to possess the properties of the underlying theoretical cdf, K(θ,t), of W_θ, are given. The latter conditions allow for defining a three-step estimation procedure for solving the resulting non-linear regression problem with linear inequality constraints. In the proposed procedure, finding the number and location of the knots and the coefficients of the unconstrained GeD spline estimator and solving the constraint least-squares optimisation problem are separated. Thus, the resulting spline estimator is used to recover the generator and the related Archimedean copula by solving an ordinary differential equation. The proposed method is truly multivariate, it brings about numerical efficiency and as a result can be applied with large volumes of data and for dimensions d≥2, as illustrated by the numerical examples presented.     

Uniform metrical task systems with a limited number of states

We give a randomized algorithm (the “Wedge Algorithm”) of competitiveness for any metrical task system on a uniform space of k points, for any k?2, where , the kth harmonic number. This algorithm has better competitiveness than the Irani-Seiden algorithm if k is smaller than 10⁸. The algorithm is better by a factor of 2 if k<47.     

Rigidity of a simple extended lower triangular matrix

For the all-ones lower triangular matrices, the upper and lower bounds on rigidity are known to match [P. Pudlak, Z. Vavrin, Computation of rigidity of order n²/r for one simple matrix, Comment Math. Univ. Carolin. 32 (2) (1991) 213-218]. In this short note, we apply these techniques to the all-ones extended lower triangular matrices, to obtain upper and lower bounds with a small gap between the two; we show that the rigidity is .     

Eigen-distribution on random assignments for game trees

In this Letter, we investigate a special distribution, called eigen-distribution, on random assignments for a class of game trees . There are two cases, where the assignments to leaves are independently distributed (ID) and correlated distributed (CD). In the ID case, we prove that the distributional probability ? belongs to , and ? is a strictly increasing function on rounds k∈[1,∞). In the CD case, we propose a reverse assigning technique (RAT) to form two particular sets of assignments, 1-set and 0-set, then show that the E¹-distribution (namely, a particular distribution on the assignments of 1-set such that all the deterministic algorithms have the same complexity) is the unique eigen-distribution for in the global distribution.     

Upper bounds on the queuenumber of k-ary n-cubes

A queue layout of a graph consists of a linear order of its vertices, and a partition of its edges into queues, such that no two edges in the same queue are nested. The minimum number of queues in a queue layout of a graph G, denoted by qn(G), is called the queuenumber of G. Heath and Rosenberg [SIAM J. Comput. 21 (1992) 927-958] showed that boolean n-cube (i.e., the n-dimensional hypercube) can be laid out using at most n−1 queues. Heath et al. [SIAM J. Discrete Math. 5 (1992) 398-412] showed that the ternary n-cube can be laid out using at most 2n−2 queues. Recently, Hasunuma and Hirota [Inform. Process. Lett. 104 (2007) 41-44] improved the upper bound on queuenumber to n−2 for hypercubes. In this paper, we deal with the upper bound on queuenumber of a wider class of graphs called k-ary n-cubes, which contains hypercubes and ternary n-cubes as subclasses. Our result improves the previous bound in the case of ternary n-cubes. Let denote the n-dimensional k-ary cube. This paper contributes three main results as follows:

(1)

if n?3.

(2)

if n?2 and 4?k?8.

(3)

if n?1 and k?9.

     

A new approximation algorithm for labeling points with circle pairs

We study the NP-hard problem of labeling points with maximum-radius circle pairs: given n point sites in the plane, find a placement for 2n interior-disjoint uniform circles, such that each site touches two circles and the circle radius is maximized. We present a new approximation algorithm for this problem that runs in time and O(n) space and achieves an approximation factor of (≈1.486+ε), which improves the previous best bound of 1.491+ε.     

Modelling series of studies with a common structure

Consider the situation where the Structuration des Tableaux à Trois Indices de la Statistique (STATIS) methodology is applied to a series of studies, each study being represented by data and weight matrices. Relations between studies may be captured by the Hilbert-Schmidt product of these matrices. Specifically, the eigenvalues and eigenvectors of the Hilbert-Schmidt matrix S may be used to obtain a geometrical representation of the studies. The studies in a series may further be considered to have a common structure whenever their corresponding points lie along the first axis. The matrix S can be expressed as the sum of a rank 1 matrix λuu^T with an error matrix E. Therefore, the components of the vector are sufficient to locate the points associated to the studies. Former models for S where vec(E) are mathematically tractable and yet do not take into account the symmetry of the matrix S. Thus a new symmetric model is proposed as well as the corresponding tests for a common structure. It is further shown how to assess the goodness of fit of such models. An application to the human immunodeficiency virus (HIV) infection is used for assessing the proposed model.     

Regularization parameter estimation for large-scale Tikhonov regularization using a priori information

Solutions of numerically ill-posed least squares problems for A∈R^m×n by Tikhonov regularization are considered. For D∈R^p×n, the Tikhonov regularized least squares functional is given by where matrix W is a weighting matrix and is given. Given a priori estimates on the covariance structure of errors in the measurement data , the weighting matrix may be taken as which is the inverse covariance matrix of the mean 0 normally distributed measurement errors in . If in addition is an estimate of the mean value of , and σ is a suitable statistically-chosen value, J evaluated at its minimizer approximately follows a χ² distribution with degrees of freedom. Using the generalized singular value decomposition of the matrix pair , σ can then be found such that the resulting J follows this χ² distribution. But the use of an algorithm which explicitly relies on the direct solution of the problem obtained using the generalized singular value decomposition is not practical for large-scale problems. Instead an approach using the Golub-Kahan iterative bidiagonalization of the regularized problem is presented. The original algorithm is extended for cases in which is not available, but instead a set of measurement data provides an estimate of the mean value of . The sensitivity of the Newton algorithm to the number of steps used in the Golub-Kahan iterative bidiagonalization, and the relation between the size of the projected subproblem and σ are discussed. Experiments presented contrast the efficiency and robustness with other standard methods for finding the regularization parameter for a set of test problems and for the restoration of a relatively large real seismic signal. An application for image deblurring also validates the approach for large-scale problems. It is concluded that the presented approach is robust for both small and large-scale discretely ill-posed least squares problems.     

Reliable supervisory control for general architecture of decentralized discrete event systems

In this paper, we investigate the reliable decentralized supervisory control of discrete event systems (DESs) under the general architecture, where the decision for controllable events is a combination of the conjunctive and disjunctive fusion rules. By reliable control, we mean that the performance of closed-loop systems will not be degraded even in the face of possible failures of some local supervisors. The main contributions are twofold. First, a necessary and sufficient condition for the existence of a k-reliable decentralized supervisor under the general architecture is presented after introducing notions of -controllability and k-reliable -coobservability. Second, a polynomial-time algorithm to verify the reliable -coobservability of a specification is proposed.