1,132 results
Search Results
202. Efficient random coordinate descent algorithms for large-scale structured nonconvex optimization.
- Author
-
Patrascu, Andrei and Necoara, Ion
- Subjects
STOCHASTIC convergence ,GLOBAL optimization ,MATHEMATICAL optimization ,ALGORITHMS ,NUMERICAL analysis ,MATHEMATICAL analysis - Abstract
In this paper we analyze several new methods for solving nonconvex optimization problems with the objective function consisting of a sum of two terms: one is nonconvex and smooth, and another is convex but simple and its structure is known. Further, we consider both cases: unconstrained and linearly constrained nonconvex problems. For optimization problems of the above structure, we propose random coordinate descent algorithms and analyze their convergence properties. For the general case, when the objective function is nonconvex and composite we prove asymptotic convergence for the sequences generated by our algorithms to stationary points and sublinear rate of convergence in expectation for some optimality measure. Additionally, if the objective function satisfies an error bound condition we derive a local linear rate of convergence for the expected values of the objective function. We also present extensive numerical experiments for evaluating the performance of our algorithms in comparison with state-of-the-art methods. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
203. A parametric solution algorithm for a class of rank-two nonconvex programs.
- Author
-
Cambini, Riccardo and Sodini, Claudio
- Subjects
NONCONVEX programming ,MATHEMATICAL analysis ,MATHEMATICAL programming ,ALGORITHMS ,COMPUTERS - Abstract
The aim of this paper is to propose a solution algorithm for a particular class of rank-two nonconvex programs having a polyhedral feasible region. The algorithm lies within the class of the so called 'optimal level solutions' parametric methods. The subproblems obtained by means of this parametrical approach are quadratic convex ones, but not necessarily neither strictly convex nor linear. For this very reason, in order to solve in an unifying framework all of the considered rank-two nonconvex programs a new approach needs to be proposed. The efficiency of the algorithm is improved by means of the use of underestimation functions. The results of a computational test are provided and discussed. [ABSTRACT FROM AUTHOR]
- Published
- 2014
- Full Text
- View/download PDF
204. Minimum total coloring of planar graph.
- Author
-
Wang, Huijuan, Wu, Lidong, Wu, Weili, Pardalos, Panos, and Wu, Jianliang
- Subjects
GRAPH theory ,PLANAR graphs ,MATHEMATICAL analysis ,ALGORITHMS ,COMPUTER networks - Abstract
Graph coloring is an important tool in the study of optimization, computer science, network design, e.g., file transferring in a computer network, pattern matching, computation of Hessians matrix and so on. In this paper, we consider one important coloring, vertex coloring of a total graph, which is familiar to us by the name of 'total coloring'. Total coloring is a coloring of $$V\cup {E}$$ such that no two adjacent or incident elements receive the same color. In other words, total chromatic number of $$G$$ is the minimum number of disjoint vertex independent sets covering a total graph of $$G$$ . Here, let $$G$$ be a planar graph with $$\varDelta \ge 8$$ . We proved that if for every vertex $$v\in V$$ , there exists two integers $$i_{v},j_{v} \in \{3,4,5,6,7,8\}$$ such that $$v$$ is not incident with intersecting $$i_v$$ -cycles and $$j_v$$ -cycles, then the vertex chromatic number of total graph of $$G$$ is $$\varDelta +1$$ , i.e., the total chromatic number of $$G$$ is $$\varDelta +1$$ . [ABSTRACT FROM AUTHOR]
- Published
- 2014
- Full Text
- View/download PDF
205. Regularized hybrid iterative algorithms for triple hierarchical variational inequalities.
- Author
-
Lu-Chuan Ceng, Ngai-Ching Wong, and Jen-Chih Yao
- Subjects
ITERATIVE methods (Mathematics) ,ALGORITHMS ,MATHEMATICAL inequalities ,NONEXPANSIVE mappings ,FIXED point theory ,MATHEMATICAL analysis - Abstract
In this paper, we introduce and study a triple hierarchical variational inequality (THVI) with constraints of minimization and equilibrium problems. More precisely, let Fix(T) be the fixed point set of a nonexpansive mapping, let MEP(Θ,ϕ) be the solution set of a mixed equilibrium problem (MEP), and let Γ be the solution set of a minimization problem (MP) for a convex and continuously Frechet differential functional in Hilbert spaces. We want to find a solution x* ∈ Fix(T) ∩ MEP(Θ,ϕ) ∩ Γ of a variational inequality with a variational inequality constraint over the intersection of Fix(T), MEP(Θ,ϕ), and Γ . We propose a hybrid iterative algorithm with regularization to compute approximate solutions of the THVI, and we present the convergence analysis of the proposed iterative algorithm. [ABSTRACT FROM AUTHOR]
- Published
- 2014
- Full Text
- View/download PDF
206. Iterative algorithms for finding the zeroes of sums of operators.
- Author
-
Luo Yi Shi, Rudong Chen, and Yujing Wu
- Subjects
ALGORITHMS ,STOCHASTIC partial differential equations ,MATHEMATICAL programming ,ALGORITHMIC randomness ,MATHEMATICAL analysis - Abstract
Let H
1 , H2 be real Hilbert spaces, C ⊆ H1 be a nonempty closed convex set, and 0 ∉ C. Let A : H1 → H2 , B : H1 → H2 be two bounded linear operators. We consider the problem to find x ∈ C such that Ax = -Bx (0 = Ax + Bx). Recently, Eckstein and Svaiter presented some splitting methods for finding a zero of the sum of monotone operator A and B. However, the algorithms are largely dependent on the maximal monotonicity of A and B. In this paper, we describe some algorithms for finding a zero of the sum of A and B which ignore the conditions of the maximal monotonicity of A and B. [ABSTRACT FROM AUTHOR]- Published
- 2014
- Full Text
- View/download PDF
207. Thresholded covering algorithms for robust and max-min optimization.
- Author
-
Gupta, Anupam, Nagarajan, Viswanath, and Ravi, R.
- Subjects
ALGORITHMS ,MATHEMATICAL optimization ,MATHEMATICAL analysis ,ELLIPSOIDS ,APPROXIMATION theory ,MATHEMATICAL functions - Abstract
In a two-stage robust covering problem, one of several possible scenarios will appear tomorrow and require to be covered, but costs are higher tomorrow than today. What should you anticipatorily buy today, so that the worst-case cost (summed over both days) is minimized? We consider the $$k$$ -robust model where the possible scenarios tomorrow are given by all demand-subsets of size $$k$$ . In this paper, we give the following simple and intuitive template for $$k$$ -robust covering problems: having built some anticipatory solution, if there exists a single demand whose augmentation cost is larger than some threshold, augment the anticipatory solution to cover this demand as well, and repeat. We show that this template gives good approximation algorithms for $$k$$ -robust versions of many standard covering problems: set cover, Steiner tree, Steiner forest, minimum-cut and multicut. Our $$k$$ -robust approximation ratios nearly match the best bounds known for their deterministic counterparts. The main technical contribution lies in proving certain net-type properties for these covering problems, which are based on dual-rounding and primal-dual ideas; these properties might be of some independent interest. As a by-product of our techniques, we also get algorithms for max-min problems of the form: ' given a covering problem instance, which $$k$$ of the elements are costliest to cover?' For the problems mentioned above, we show that their $$k$$ -max-min versions have performance guarantees similar to those for the $$k$$ -robust problems. [ABSTRACT FROM AUTHOR]
- Published
- 2014
- Full Text
- View/download PDF
208. Integrated size and topology optimization of skeletal structures with exact frequency constraints.
- Author
-
Ni, Changhui, Yan, Jun, Cheng, Gengdong, and Guo, Xu
- Subjects
MATHEMATICAL optimization ,TOPOLOGY ,ALGORITHMS ,MATHEMATICAL analysis ,STRUCTURAL design - Abstract
The present paper studies the integrated size and topology optimization of skeletal structures under natural frequency constraints. It is found that, unlike the conventional compliance-oriented topology optimization problems, the considered problem may be strongly singular in the sense that the corresponding feasible domain may be disconnected and the global optimal solutions are often located at the tips of some separated low dimensional sub-domains when the cross-sectional areas of the structural components are used as design variables. As in the case of stress-constrained topology optimization, this unpleasant behavior may prevent the gradient-based numerical optimization algorithms from finding the true optimal topologies. To overcome the difficulties posed by the strongly singular optima, some particular forms of area/moment of inertia-density interpolation schemes, which can restore the connectedness of the feasible domain, are proposed. Based on the proposed optimization model, the probability of finding the strongly singular optimum with gradient-based algorithms can be increased. Numerical examples demonstrate the effectiveness of the proposed approach. [ABSTRACT FROM AUTHOR]
- Published
- 2014
- Full Text
- View/download PDF
209. Efficient controller synthesis for a fragment of $$\hbox {MTL}_{0, \infty }$$.
- Author
-
Bulychev, Peter, David, Alexandre, Larsen, Kim, and Li, Guangyuan
- Subjects
SPECTRAL synthesis (Mathematics) ,ALGORITHMS ,MATHEMATICAL formulas ,APPROXIMATION theory ,FUNCTIONAL analysis ,MATHEMATICAL analysis - Abstract
In this paper we offer an efficient controller synthesis algorithm for assume-guarantee specifications of the form $$\varphi _1 \wedge \varphi _2 \wedge \cdots \wedge \varphi _n \rightarrow \psi _1 \wedge \psi _2 \wedge \cdots \wedge \psi _m$$ . Here, $$\{\varphi _i,\psi _j\}$$ are all safety-MTL $$_{0, \infty }$$ properties, where the sub-formulas $$\{\varphi _i\}$$ are supposed to specify assumptions of the environment and the sub-formulas $$\{\psi _j\}$$ are specifying requirements to be guaranteed by the controller. Our synthesis method exploits the engine of Uppaal-Tiga and the novel translation of safety- and co-safety-MTL $$_{0, \infty }$$ properties into under-approximating, deterministic timed automata. Our approach avoids determinization of Büchi automata, which is the main obstacle for the practical applicability of controller synthesis for linear-time specifications. The experiments demonstrate that the chosen specification formalism is expressive enough to specify complex behaviors. The proposed approach is sound but not complete. However, it successfully produced solutions for all the experiments. Additionally we compared our tool with Acacia+ and Unbeast, state-of-the-art LTL synthesis tools; and our tool demonstrated better timing results, when we applied both tools to the analogous specifications. [ABSTRACT FROM AUTHOR]
- Published
- 2014
- Full Text
- View/download PDF
210. Optimizing a multi-stage production/inventory system by DC programming based approaches.
- Author
-
Le Thi, Hoai and Tran, Duc
- Subjects
ALGORITHMS ,NONLINEAR analysis ,MATHEMATICAL analysis ,MATHEMATICAL optimization ,COMPUTATIONAL complexity - Abstract
This paper deals with optimizing the cost of set up, transportation and inventory of a multi-stage production system in presence of bottleneck. The considered optimization model is a mixed integer nonlinear program. We propose two methods based on DC (Difference of Convex) programming and DCA (DC Algorithm)-an innovative approach in nonconvex programming framework. The mixed integer nonlinear problem is first reformulated as a DC program and then DCA is developed to solve the resulting problem. In order to globally solve the problem, we combine DCA with a Branch and Bound algorithm (BB-DCA). A convex minorant of the objective function is introduced. DCA is used to compute upper bounds while lower bounds are calculated from a convex relaxation problem. The numerical results compared with those of COUENNE (), a solver for mixed integer nonconvex programming, show the rapidity and the ϵ-globality of DCA in almost cases, as well as the efficiency of the combined DCA-Branch and Bound algorithm. We also propose a simple heuristic algorithm which is proved by experimental results to be better than an existing heuristic in the literature for this problem. [ABSTRACT FROM AUTHOR]
- Published
- 2014
- Full Text
- View/download PDF
211. A Novel Intra-Class Distance-Based Signature Identification Algorithm Using Weighted Gabor Features and Dynamic Characteristics.
- Author
-
Tahmasebi, Ava and Pourghassem, Hossein
- Subjects
ALGORITHMS ,ALGEBRA ,MATHEMATICAL analysis ,ABSTRACT algebra ,GRAPHIC algebra - Abstract
Copyright of Arabian Journal for Science & Engineering (Springer Science & Business Media B.V. ) is the property of Springer Nature and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
- Published
- 2013
- Full Text
- View/download PDF
212. A Linear-Time Algorithm for Finding Locally Connected Spanning Trees on Circular-Arc Graphs.
- Author
-
Lin, Ching-Chi, Chen, Gen-Huey, and Chang, Gerard
- Subjects
SPANNING trees ,INTERSECTION graph theory ,ALGORITHMS ,MATHEMATICAL optimization ,MATHEMATICAL analysis - Abstract
Suppose that T is a spanning tree of a graph G. T is called a locally connected spanning tree of G if for every vertex of T, the set of all its neighbors in T induces a connected subgraph of G. In this paper, given an intersection model of a circular-arc graph, an O( n)-time algorithm is proposed that can determine whether the circular-arc graph contains a locally connected spanning tree or not, and produce one if it exists. [ABSTRACT FROM AUTHOR]
- Published
- 2013
- Full Text
- View/download PDF
213. To solving problems of algebra for two-parameter matrices. X.
- Author
-
Kublanovskaya, V.
- Subjects
PROBLEM solving ,MATRICES (Mathematics) ,FACTORIZATION ,ALGORITHMS ,POLYNOMIALS ,BASIS (Linear algebra) ,MATHEMATICAL analysis - Abstract
The paper considers conditions under which rank factorizations of a two-parameter polynomial matrix can be affected with the use of unimodular matrices, as in the one-parameter case. Algorithms for computing such factorizations and a minimal basis of the null space of the corresponding matrix are presented. Also an algorithm for inverting unimodular two-parameter polynomial matrices is suggested. Bibliography: 4 titles. [ABSTRACT FROM AUTHOR]
- Published
- 2013
- Full Text
- View/download PDF
214. A modified extreme learning machine with sigmoidal activation functions.
- Author
-
Chen, Zhixiang, Zhu, Houying, and Wang, Yuguang
- Subjects
MACHINE learning ,ALGORITHMS ,FEEDFORWARD neural networks ,EXPERIMENTAL design ,PERFORMANCE evaluation ,MATHEMATICAL analysis ,INVERSE functions - Abstract
This paper proposes a modified ELM algorithm that properly selects the input weights and biases before training the output weights of single-hidden layer feedforward neural networks with sigmoidal activation function and proves mathematically the hidden layer output matrix maintains full column rank. The modified ELM avoids the randomness compared with the ELM. The experimental results of both regression and classification problems show good performance of the modified ELM algorithm. [ABSTRACT FROM AUTHOR]
- Published
- 2013
- Full Text
- View/download PDF
215. On the finite basis problem for certain 2-limited words.
- Author
-
Li, Jian, Zhang, Wen, and Luo, Yan
- Subjects
MONOIDS ,ALPHABETS ,IDEALS (Algebra) ,DISCRETE systems ,ALGORITHMS ,NONLINEAR theories ,MATHEMATICAL analysis - Abstract
Let X* be a free monoid over an alphabet X and W be a finite language over X. Let S( W) be the Rees quotient X*/ I( W), where I( W) is the ideal of X* consisting of all elements of X* that are not subwords of W. Then S( W) is a finite monoid with zero and is called the discrete syntactic monoid of W. W is called finitely based if the monoid S( W) is finitely based. In this paper, we give some sufficient conditions for a monoid to be non-finitely based. Using these conditions and other results, we describe all finitely based 2-limited words over a three-element alphabet. Furthermore, an explicit algorithm is given to decide that whether or not a 2-limited word in which there are exactly two non-linear letters is finitely based. [ABSTRACT FROM AUTHOR]
- Published
- 2013
- Full Text
- View/download PDF
216. Preconditioning and globalizing conjugate gradients in dual space for quadratically penalized nonlinear-least squares problems.
- Author
-
Gratton, Serge, Gürol, Selime, and Toint, Philippe
- Subjects
DUALITY theory (Mathematics) ,ALGEBRA ,MATHEMATICAL analysis ,LEAST squares ,ALGORITHMS - Abstract
When solving nonlinear least-squares problems, it is often useful to regularize the problem using a quadratic term, a practice which is especially common in applications arising in inverse calculations. A solution method derived from a trust-region Gauss-Newton algorithm is analyzed for such applications, where, contrary to the standard algorithm, the least-squares subproblem solved at each iteration of the method is rewritten as a quadratic minimization subject to linear equality constraints. This allows the exploitation of duality properties of the associated linearized problems. This paper considers a recent conjugate-gradient-like method which performs the quadratic minimization in the dual space and produces, in exact arithmetic, the same iterates as those produced by a standard conjugate-gradients method in the primal space. This dual algorithm is computationally interesting whenever the dimension of the dual space is significantly smaller than that of the primal space, yielding gains in terms of both memory usage and computational cost. The relation between this dual space solver and PSAS (Physical-space Statistical Analysis System), another well-known dual space technique used in data assimilation problems, is explained. The use of an effective preconditioning technique is proposed and refined convergence bounds derived, which results in a practical solution method. Finally, stopping rules adequate for a trust-region solver are proposed in the dual space, providing iterates that are equivalent to those obtained with a Steihaug-Toint truncated conjugate-gradient method in the primal space. [ABSTRACT FROM AUTHOR]
- Published
- 2013
- Full Text
- View/download PDF
217. Spatial reasoning with rectangular cardinal relations.
- Author
-
Navarrete, Isabel, Morales, Antonio, Sciavicco, Guido, and Cardenas-Viedma, M.
- Subjects
MATHEMATICAL analysis ,CALCULUS ,ALGEBRA ,ALGORITHMS ,CONFIGURATIONS (Geometry) - Abstract
Qualitative spatial representation and reasoning plays a important role in various spatial applications. In this paper we introduce a new formalism, we name RCD calculus, for qualitative spatial reasoning with cardinal direction relations between regions of the plane approximated by rectangles. We believe this calculus leads to an attractive balance between efficiency, simplicity and expressive power, which makes it adequate for spatial applications. We define a constraint algebra and we identify a convex tractable subalgebra allowing efficient reasoning with definite and imprecise knowledge about spatial configurations specified by qualitative constraint networks. For such tractable fragment, we propose several polynomial algorithms based on constraint satisfaction to solve the consistency and minimality problems. Some of them rely on a translation of qualitative networks of the RCD calculus to qualitative networks of the Interval or Rectangle Algebra, and back. We show that the consistency problem for convex networks can also be solved inside the RCD calculus, by applying a suitable adaptation of the path-consistency algorithm. However, path consistency can not be applied to obtain the minimal network, contrary to what happens in the convex fragment of the Rectangle Algebra. Finally, we partially analyze the complexity of the consistency problem when adding non-convex relations, showing that it becomes NP-complete in the cases considered. This analysis may contribute to find a maximal tractable subclass of the RCD calculus and of the Rectangle Algebra, which remains an open problem. [ABSTRACT FROM AUTHOR]
- Published
- 2013
- Full Text
- View/download PDF
218. Bipartite Graphs with the Maximal Value of the Second Zagreb Index.
- Author
-
RONGLING LANG, XIAOLE DENG, and HUI LU
- Subjects
BIPARTITE graphs ,GRAPHIC methods ,ALGORITHMS ,NUMERICAL analysis ,MATHEMATICAL analysis - Abstract
The second Zagreb index of a graph G is an adjacency-based topological index, which is defined as Σ
uv∊E(G) (d(u)d(v)), where uv is an edge of G, d(u) is the degree of vertex u in G. In this paper, we consider the second Zagreb index for bipartite graphs. Firstly, we present a new definition of ordered bipartite graphs, and then give a necessary condition for a bipartite graph to attain the maximal value of the second Zagreb index. We also present an algorithm for transforming a bipartite graph to an ordered bipartite graph, which can be done in O(n2 +n2 1 ) time for a bipartite graph B with a partition ∣X∣ = n1 and ∣Y∣ = n2 . [ABSTRACT FROM AUTHOR]- Published
- 2013
219. Community detection using global and local structural information.
- Author
-
YAN, HAI-LONG, XIANG, JU, ZHANG, XIAO-YU, FAN, JUN-FENG, CHEN, FANG, FU, GEN-YI, GUO, ER-MIN, HU, XIN-GUANG, HU, KE, and WANG, RU-MIN
- Subjects
INFORMATION theory ,GRAPH theory ,ALGORITHMS ,RANDOM walks ,MEASURE theory ,SIMILARITY (Geometry) ,MATHEMATICAL analysis - Abstract
Community detection is of considerable importance for understanding both the structure and function of complex networks. In this paper, we introduced the general procedure of the community detection algorithms using global and local structural information, where the edge betweenness and the local similarity measures respectively based on local random walk dynamics and local cyclic structures were used. The algorithms were tested on artificial and real-world networks. The results clearly show that all the algorithms have excellent performance in the tests and the local similarity measure based on local random walk dynamics is superior to that based on local cyclic structures. [ABSTRACT FROM AUTHOR]
- Published
- 2013
- Full Text
- View/download PDF
220. Least squares estimation for a class of non-uniformly sampled systems based on the hierarchical identification principle.
- Author
-
Liu, Yanjun, Ding, Feng, and Shi, Yang
- Subjects
LEAST squares ,PARAMETER estimation ,ALGORITHMS ,STOCHASTIC convergence ,VECTOR analysis ,MATHEMATICAL analysis - Abstract
This paper presents a novel hierarchical least squares algorithm for a class of non-uniformly sampled systems. Based on the hierarchical identification principle, the identification model with a high dimensional parameter vector is decomposed into a group of submodels with lower dimensional parameter vectors. By using the least squares method to identify the submodels and taking a coordinated measure to address the associated items between the submodels, all the system parameters can be estimated. The proposed algorithm can save the computation cost. The performance analysis indicates that parameter estimates converge to their true values. The simulation tests confirm the convergence results. [ABSTRACT FROM AUTHOR]
- Published
- 2012
- Full Text
- View/download PDF
221. Recognizing Treelike k-Dissimilarities.
- Author
-
Herrmann, Sven, Huber, Katharina, Moulton, Vincent, and Spillner, Andreas
- Subjects
TREE graphs ,REAL numbers ,MATHEMATICAL analysis ,POLYNOMIALS ,PHYLOGENY ,ALGORITHMS - Abstract
A k-dissimilarity D on a finite set X, | X| ≥ k, is a map from the set of size k subsets of X to the real numbers. Such maps naturally arise from edgeweighted trees T with leaf-set X: Given a subset Y of X of size k, D( Y ) is defined to be the total length of the smallest subtree of T with leaf-set Y . In case k = 2, it is well-known that 2-dissimilarities arising in this way can be characterized by the so-called '4-point condition'. However, in case k > 2 Pachter and Speyer () recently posed the following question: Given an arbitrary k-dissimilarity, how do we test whether this map comes from a tree? In this paper, we provide an answer to this question, showing that for k ≥ 3 a k-dissimilarity on a set X arises from a tree if and only if its restriction to every 2 k-element subset of X arises from some tree, and that 2 k is the least possible subset size to ensure that this is the case. As a corollary, we show that there exists a polynomial-time algorithm to determine when a k-dissimilarity arises from a tree. We also give a 6-point condition for determining when a 3-dissimilarity arises from a tree, that is similar to the aforementioned 4-point condition. [ABSTRACT FROM AUTHOR]
- Published
- 2012
- Full Text
- View/download PDF
222. Using the parametric approach to solve the continuous-time linear fractional max-min problems.
- Author
-
Wen, Ching-Feng and Wu, Hsien-Chung
- Subjects
ALGORITHMS ,LINEAR programming ,INTEGER programming ,APPROXIMATION theory ,MATHEMATICAL analysis ,MATRICES (Mathematics) - Abstract
A numerical algorithm based on parametric approach is proposed in this paper to solve a class of continuous-time linear fractional max-min programming problems. We shall transform this original problem into a continuous-time non-fractional programming problem, which unfortunately happens to be a continuous-time nonlinear programming problem. In order to tackle this nonlinear problem, we propose the auxiliary problem that will be formulated as a parametric continuous-time linear programming problem. We also introduce a dual problem of this parametric continuous-time linear programming problem in which the weak duality theorem also holds true. We introduce the discrete approximation method to solve the primal and dual pair of parametric continuous-time linear programming problems by using the recurrence method. Finally, we provide two numerical examples to demonstrate the usefulness of this algorithm. [ABSTRACT FROM AUTHOR]
- Published
- 2012
- Full Text
- View/download PDF
223. An alternating variable method for the maximal correlation problem.
- Author
-
Zhang, Lei-Hong and Liao, Li-Zhi
- Subjects
MATHEMATICAL variables ,STATISTICAL correlation ,MATHEMATICAL analysis ,ALGORITHMS ,MATRICES (Mathematics) ,MULTIVARIATE analysis - Abstract
The maximal correlation problem (MCP) aiming at optimizing correlations between sets of variables plays an important role in many areas of statistical applications. Up to date, algorithms for the general MCP stop at solutions of the multivariate eigenvalue problem (MEP), which serves only as a necessary condition for the global maxima of the MCP. For statistical applications, the global maximizer is quite desirable. In searching the global solution of the MCP, in this paper, we propose an alternating variable method (AVM), which contains a core engine in seeking a global maximizer. We prove that (i) the algorithm converges globally and monotonically to a solution of the MEP, (ii) any convergent point satisfies a global optimal condition of the MCP, and (iii) whenever the involved matrix A is nonnegative irreducible, it converges globally to the global maximizer. These properties imply that the AVM is an effective approach to obtain a global maximizer of the MCP. Numerical testings are carried out and suggest a superior performance to the others, especially in finding a global solution of the MCP. [ABSTRACT FROM AUTHOR]
- Published
- 2012
- Full Text
- View/download PDF
224. A linear eigenvalue algorithm for the nonlinear eigenvalue problem.
- Author
-
Jarlebring, Elias, Michiels, Wim, and Meerbergen, Karl
- Subjects
EIGENVALUES ,ALGORITHMS ,MATHEMATICAL analysis ,POLYNOMIALS ,ALGEBRA ,MATHEMATICS - Abstract
The Arnoldi method for standard eigenvalue problems possesses several attractive properties making it robust, reliable and efficient for many problems. The first result of this paper is a characterization of the solutions to an arbitrary (analytic) nonlinear eigenvalue problem (NEP) as the reciprocal eigenvalues of an infinite dimensional operator denoted $${\mathcal {B}}$$ . We consider the Arnoldi method for the operator $${\mathcal {B}}$$ and show that with a particular choice of starting function and a particular choice of scalar product, the structure of the operator can be exploited in a very effective way. The structure of the operator is such that when the Arnoldi method is started with a constant function, the iterates will be polynomials. For a large class of NEPs, we show that we can carry out the infinite dimensional Arnoldi algorithm for the operator $${\mathcal {B}}$$ in arithmetic based on standard linear algebra operations on vectors and matrices of finite size. This is achieved by representing the polynomials by vector coefficients. The resulting algorithm is by construction such that it is completely equivalent to the standard Arnoldi method and also inherits many of its attractive properties, which are illustrated with examples. [ABSTRACT FROM AUTHOR]
- Published
- 2012
- Full Text
- View/download PDF
225. On laplace and Dini transformations for multidimensional equations with a decomposable principal symbol.
- Author
-
Ganzha, E.
- Subjects
ALGORITHMS ,DIFFERENTIAL equations ,HARMONIC functions ,ALGEBRA software ,MATHEMATICAL analysis ,BESSEL functions - Abstract
Algorithms for solving linear PDEs implemented in modern computer algebra systems are usually limited to equations with two independent variables. In this paper, we propose a generalization of the theory of Laplace transformations to second-order partial differential operators in ℝ (and, generally, ℝ) with a principal symbol decomposable into the product of two linear (with respect to derivatives) factors. We consider two algorithms of generalized Laplace transformations and describe classes of operators in ℝ to which these algorithms are applicable. We correct a mistake in [8] and show that Dini-type transformations are in fact generalized Laplace transformations for operators with coefficients in a skew (noncommutative) Ore field. Keywords: computer algebra, partial differential equations, algorithms for solution. [ABSTRACT FROM AUTHOR]
- Published
- 2012
- Full Text
- View/download PDF
226. Linear-Time Algorithm for the Paired-Domination Problem in Convex Bipartite Graphs.
- Author
-
Hung, Ruo-Wei
- Subjects
LINEAR systems ,ALGORITHMS ,BIPARTITE graphs ,CONVEX functions ,GRAPH theory ,NUMERICAL solutions to boundary value problems ,MATHEMATICAL analysis - Abstract
A bipartite graph G=( U, W, E) with vertex set V= U∪ W is convex if there exists an ordering of the vertices of W such that for each u∈ U, the neighbors of u are consecutive in W. A compact representation of a convex bipartite graph for specifying such an ordering can be computed in O(| V|+| E|) time. The paired-domination problem on bipartite graphs has been shown to be NP-complete. The complexity of the paired-domination problem on convex bipartite graphs has remained unknown. In this paper, we present an O(| V|) time algorithm to solve the paired-domination problem on convex bipartite graphs given a compact representation. As a byproduct, we show that our algorithm can be directly applied to solve the total domination problem on convex bipartite graphs in the same time bound. [ABSTRACT FROM AUTHOR]
- Published
- 2012
- Full Text
- View/download PDF
227. Cycle detection algorithms and their applications.
- Author
-
Nesterenko, A.
- Subjects
ALGORITHMS ,NUMBER theory ,FACTORIZATION ,COMPUTATIONAL complexity ,MATHEMATICAL analysis ,PROOF theory - Abstract
This paper considers several cycle detection algorithms. Proofs of their correctness are given, bounds for complexity are obtained, some number theory applications like the factorization of integers and the discrete log problem are examined. [ABSTRACT FROM AUTHOR]
- Published
- 2012
- Full Text
- View/download PDF
228. How landscape ruggedness influences the performance of real-coded algorithms: a comparative study.
- Author
-
Marín, Jesús
- Subjects
MATHEMATICAL analysis ,COMPARATIVE studies ,ALGORITHMS ,MATHEMATICAL optimization ,SET theory - Abstract
Ruggedness has a strong influence on the performance of algorithms, but it has been barely studied in real-coded optimization, mainly because of the difficulty of isolating it from a number of involved topological properties. In this paper, we propose a framework consisting of increasing ruggedness function sets built by a mechanism which generates multiple funnels. This mechanism introduces different levels of sinusoidal distortion which can be controlled to isolate the singular influence of some related features. Some commonly used measures of ruggedness have been applied to analyze these sets of functions, and a numerical study to compare the performance of some representative algorithms has been carried out. The results confirm that ruggedness has an influence on the performance of the algorithm, proving that it depends on the multi-funnel structure and peak features, such as height and relative size of the global peak, and not on the number of peaks. [ABSTRACT FROM AUTHOR]
- Published
- 2012
- Full Text
- View/download PDF
229. OFP_CLASS: a hybrid method to generate optimized fuzzy partitions for classification.
- Author
-
Cadenas, Jose, Garrido, M., Martínez, Raquel, and Bonissone, Piero
- Subjects
MATHEMATICAL analysis ,ALGORITHMS ,DATA mining ,FUZZY sets ,OLAP technology ,INFORMATION resources management - Abstract
The discretization of values plays a critical role in data mining and knowledge discovery. The representation of information through intervals is more concise and easier to understand at certain levels of knowledge than the representation by mean continuous values. In this paper, we propose a method for discretizing continuous attributes by means of fuzzy sets, which constitute a fuzzy partition of the domains of these attributes. This method carries out a fuzzy discretization of continuous attributes in two stages. A fuzzy decision tree is used in the first stage to propose an initial set of crisp intervals, while a genetic algorithm is used in the second stage to define the membership functions and the cardinality of the partitions. After defining the fuzzy partitions, we evaluate and compare them with previously existing ones in the literature. [ABSTRACT FROM AUTHOR]
- Published
- 2012
- Full Text
- View/download PDF
230. Fast algorithms for implementation of the Green's function.
- Author
-
Yunakovsky, A.
- Subjects
GREEN'S functions ,ALGORITHMS ,HELMHOLTZ equation ,OPERATOR theory ,PERIODIC functions ,MATHEMATICAL analysis - Abstract
This paper is devoted to new fast algorithms for implementation of the Green's function for the Helmholtz operator in high-frequency regions in periodic and helical structures. [ABSTRACT FROM AUTHOR]
- Published
- 2012
- Full Text
- View/download PDF
231. An efficient algorithm for maximal margin clustering.
- Author
-
Peng, Jiming, Mukherjee, Lopamudra, Singh, Vikas, Schuurmans, Dale, and Xu, Linli
- Subjects
ALGORITHMS ,MATHEMATICAL optimization ,MATHEMATICAL analysis ,COMPUTATIONAL complexity ,MACHINE theory - Abstract
Maximal margin based frameworks have emerged as a powerful tool for supervised learning. The extension of these ideas to the unsupervised case, however, is problematic since the underlying optimization entails a discrete component. In this paper, we first study the computational complexity of maximal hard margin clustering and show that the hard margin clustering problem can be precisely solved in O( n) time where n is the number of the data points and d is the dimensionality of the input data. However, since it is well known that many datasets commonly 'express' themselves primarily in far fewer dimensions, our interest is in evaluating if a careful use of dimensionality reduction can lead to practical and effective algorithms. We build upon these observations and propose a new algorithm that gradually increases the number of features used in the separation model in each iteration, and analyze the convergence properties of this scheme. We report on promising numerical experiments based on a 'truncated' version of this approach. Our experiments indicate that for a variety of datasets, good solutions equivalent to those from other existing techniques can be obtained in significantly less time. [ABSTRACT FROM AUTHOR]
- Published
- 2012
- Full Text
- View/download PDF
232. Augmented Lagrangian functions for constrained optimization problems.
- Author
-
Zhou, Y. and Yang, X.
- Subjects
LAGRANGIAN functions ,MATHEMATICAL optimization ,CALCULUS of variations ,ALGORITHMS ,MATHEMATICAL analysis - Abstract
In this paper, in order to obtain some existence results about solutions of the augmented Lagrangian problem for a constrained problem in which the objective function and constraint functions are noncoercive, we construct a new augmented Lagrangian function by using an auxiliary function. We establish a zero duality gap result and a sufficient condition of an exact penalization representation for the constrained problem without the coercive or level-bounded assumption on the objective function and constraint functions. By assuming that the sequence of multipliers is bounded, we obtain the existence of a global minimum and an asymptotically minimizing sequence for the constrained optimization problem. [ABSTRACT FROM AUTHOR]
- Published
- 2012
- Full Text
- View/download PDF
233. Permutation binomials and their groups.
- Author
-
Vasilev, N. and Rybalkin, M.
- Subjects
PERMUTATION groups ,FINITE fields ,ALGORITHMS ,GENERALIZATION ,PROBLEM solving ,MATHEMATICAL functions ,MATHEMATICAL analysis - Abstract
This paper is devoted to studying the properties of permutation binomials over finite fields and the possibility to use permutation binomials as encryption functions. We present an algorithm for enumeration of permutation binomials. Using this algorithm, all permutation binomials for finite fields up to order 15000 were generated. Using this data, we investigate the groups generated by the permutation binomials and discover that over some finite fields $$ {{\mathbb F}_q} $$, every bijective function on [1.. q − 1] can be represented as a composition of binomials. We study the problem of generating permutation binomials over large prime fields. We also prove that a generalization of RSA using permutation binomials is not secure. Bibliography: 9 titles. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
234. A computationally efficient method for delineating irregularly shaped spatial clusters.
- Author
-
Duque, Juan, Aldstadt, Jared, Velasquez, Ermilson, Franco, Jose, and Betancourt, Alejandro
- Subjects
ALGORITHMS ,AMOEBA ,AUTOCORRELATION (Statistics) ,STATISTICS ,ECOLOGICAL landscape design ,EMPIRICAL research ,MATHEMATICAL analysis - Abstract
In this paper, we present an efficiency improvement for the algorithm called AMOEBA, A Multidirectional Optimum Ecotope-Based Algorithm, devised by Aldstadt and Getis (Geogr Anal 38(4):327-343, ). AMOEBA embeds a local spatial autocorrelation statistic in an iterative procedure in order to identify spatial clusters (ecotopes) of related spatial units. We provide an analysis of the computational complexity of the original AMOEBA and develop an alternative formulation that reduces computational time without losing optimality. Empirical evidence is provided using georeferenced socio-demographic data in Accra, Ghana. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
235. Data array multiprocessing by difference slices.
- Author
-
Martyniuk, T. and Khomyuk, V.
- Subjects
ALGORITHMS ,PARALLEL algorithms ,MULTIPROCESSORS ,SIMULATION methods & models ,MATHEMATICAL analysis - Abstract
The paper analyzes the features of the presentation of parallel algorithms for the multiprocessing of vector data arrays by difference slices in the basis of a modified Glushkov SAA. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
236. Optimality of the Neighbor Joining Algorithm and Faces of the Balanced Minimum Evolution Polytope.
- Author
-
Haws, David, Hodge, Terrell, and Yoshida, Ruriko
- Subjects
COMBINATORICS ,CLADISTIC analysis ,ALGORITHMS ,MATHEMATICAL optimization ,TREE graphs ,POLYTOPES ,MATHEMATICAL analysis - Abstract
Balanced minimum evolution (BME) is a statistically consistent distance-based method to reconstruct a phylogenetic tree from an alignment of molecular data. In 2000, Pauplin showed that the BME method is equivalent to optimizing a linear functional over the BME polytope, the convex hull of the BME vectors obtained from Pauplin's formula applied to all binary trees. The BME method is related to the Neighbor Joining (NJ) Algorithm, now known to be a greedy optimization of the BME principle. Further, the NJ and BME algorithms have been studied previously to understand when the NJ Algorithm returns a BME tree for small numbers of taxa. In this paper we aim to elucidate the structure of the BME polytope and strengthen knowledge of the connection between the BME method and NJ Algorithm. We first prove that any subtree-prune-regraft move from a binary tree to another binary tree corresponds to an edge of the BME polytope. Moreover, we describe an entire family of faces parameterized by disjoint clades. We show that these clade-faces are smaller dimensional BME polytopes themselves. Finally, we show that for any order of joining nodes to form a tree, there exists an associated distance matrix (i.e., dissimilarity map) for which the NJ Algorithm returns the BME tree. More strongly, we show that the BME cone and every NJ cone associated to a tree T have an intersection of positive measure. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
237. Sets of Double and Triple Weights of Trees.
- Author
-
Rubei, Elena
- Subjects
MATHEMATICAL analysis ,SET theory ,NUMERICAL analysis ,TREES ,REAL numbers ,WEIGHTS & measures ,ALGORITHMS ,COMPLEX numbers - Abstract
Let T be a weighted tree with n leaves numbered by the set {1, . . . , n}. Let D( T) be the distance between the leaves i and j. Let $${{D_{i,j,k}(T) = \frac{1}{2}(D_{i,j}(T)+D_{j,k}(T)+D_{i,k}(T))}}$$ . We will call such numbers 'triple weights' of the tree. In this paper, we give a characterization, different from the previous ones, for sets indexed by 2-subsets of a n-set to be double weights of a tree. By using the same ideas, we find also necessary and sufficient conditions for a set of real numbers indexed by 3-subsets of an n-set to be the set of the triple weights of a tree with n leaves. Besides we propose a slight modification of Saitou-Nei's Neighbour-Joining algorithm to reconstruct trees from the data D. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
238. A Property Tester for Tree-Likeness of Quartet Topologies.
- Author
-
Chang, Maw-Shang, Lin, Chuang-Chieh, and Rossmanith, Peter
- Subjects
ALGORITHMS ,TOPOLOGY ,MATHEMATICAL analysis ,SET theory ,COMPUTER science ,MATHEMATICS - Abstract
Property testing is a rapid growing field in theoretical computer science. It considers the following task: given a function f over a domain D, a property ℘ and a parameter 0< ε<1, by examining function values of f over o(| D|) elements in D, determine whether f satisfies ℘ or differs from any one which satisfies ℘ in at least ε| D| elements. An algorithm that fulfills this task is called a property tester. We focus on tree-likeness of quartet topologies, which is a combinatorial property originating from evolutionary tree construction. The input function is f, which assigns one of the three possible topologies for every quartet over an n-taxon set S. We say that f satisfies tree-likeness if there exists an evolutionary tree T whose induced quartet topologies coincide with f. In this paper, we prove the existence of a set of quartet topologies of error number at least $c{n\choose 4}$ for some constant c>0, and present the first property tester for tree-likeness of quartet topologies. Our property tester makes at most O( n/ ε) queries, and is of one-sided error and non-adaptive. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
239. A survey: hybrid evolutionary algorithms for cluster analysis.
- Author
-
Abul Hasan, Mohamed and Ramakrishnan, Sivakumar
- Subjects
ALGORITHMS ,EVOLUTIONARY computation ,CLUSTER analysis (Statistics) ,MATHEMATICAL optimization ,MATHEMATICAL analysis - Abstract
Clustering is a popular data analysis and data mining technique. It is the unsupervised classification of patterns into groups. Many algorithms for large data sets have been proposed in the literature using different techniques. However, conventional algorithms have some shortcomings such as slowness of the convergence, sensitive to initial value and preset classed in large scale data set etc. and they still require much investigation to improve performance and efficiency. Over the last decade, clustering with ant-based and swarm-based algorithms are emerging as an alternative to more traditional clustering techniques. Many complex optimization problems still exist, and it is often very difficult to obtain the desired result with one of these algorithms alone. Thus, robust and flexible techniques of optimization are needed to generate good results for clustering data. Some algorithms that imitate certain natural principles, known as evolutionary algorithms have been used in a wide variety of real-world applications. Recently, much research has been proposed using hybrid evolutionary algorithms to solve the clustering problem. This paper provides a survey of hybrid evolutionary algorithms for cluster analysis. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
240. A Mathematical Approach to the Analysis of Multiplex DNA Profiles.
- Author
-
Goor, Robert, Forman Neall, Lisa, Hoffman, Douglas, and Sherry, Stephen
- Subjects
DNA ,BIOMATHEMATICS ,MATHEMATICAL analysis ,BIOLOGICAL mathematical modeling ,ALGORITHMS ,ELECTROPHORESIS ,GAUSSIAN processes ,FORENSIC sciences - Abstract
Multiplex DNA profiles are used extensively for biomedical and forensic purposes. However, while DNA profile data generation is automated, human analysis of those data is not, and the need for speed combined with accuracy demands a computer-automated approach to sample interpretation and quality assessment. In this paper, we describe an integrated mathematical approach to modeling the data and extracting the relevant information, while rejecting noise and sample artifacts. We conclude with examples showing the effectiveness of our algorithms. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
241. A Simple Linear-Time Recognition Algorithm for Weakly Quasi-Threshold Graphs.
- Author
-
Nikolopoulos, Stavros and Papadopoulos, Charis
- Subjects
LINEAR systems ,PATTERN recognition systems ,ALGORITHMS ,GRAPH theory ,COINCIDENCE theory ,COMBINATORICS ,MATHEMATICAL analysis - Abstract
Weakly quasi-threshold graphs form a proper subclass of the well-known class of cographs by restricting the join operation. In this paper we characterize weakly quasi-threshold graphs by a finite set of forbidden subgraphs: the class of weakly quasi-threshold graphs coincides with the class of { P, co-(2 P)}-free graphs. Moreover we give the first linear-time algorithm to decide whether a given graph belongs to the class of weakly quasi-threshold graphs, improving the previously known running time. Based on the simplicity of our recognition algorithm, we can provide certificates of membership (a structure that characterizes weakly quasi-threshold graphs) or non-membership (forbidden induced subgraphs) in additional $${{\mathcal O}(n)}$$ time. Furthermore we give a linear-time algorithm for finding the largest induced weakly quasi-threshold subgraph in a cograph. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
242. Cluster scheduling for real-time systems: utilization bounds and run-time overhead.
- Author
-
Qi, Xuan, Zhu, Dakai, and Aydin, Hakan
- Subjects
MULTIPROCESSORS ,ALGORITHMS ,MATHEMATICAL analysis ,MATHEMATICAL models ,CLUSTER analysis (Statistics) ,SCHEDULING ,HEURISTIC ,SYSTEM analysis ,SYSTEMS design - Abstract
Cluster scheduling, where processors are grouped into clusters and the tasks that are allocated to one cluster are scheduled by a global scheduler, has attracted attention in multiprocessor real-time systems research recently. In this paper, assuming that an optimal global scheduler is adopted within each cluster, we investigate the worst-case utilization bounds for cluster scheduling with different task allocation/partitioning heuristics. First, we develop a lower limit on the utilization bounds for cluster scheduling with any reasonable task allocation scheme. Then, the lower limit is shown to be the exact utilization bound for cluster scheduling with the worst-fit task allocation scheme. For other task allocation heuristics (such as first-fit, best-fit, first-fit decreasing, best-fit decreasing and worst-fit decreasing), higher utilization bounds are derived for systems with both homogeneous clusters (where each cluster has the same number of processors) and heterogeneous clusters (where clusters have different number of processors). In addition, focusing on an efficient optimal global scheduler, namely the boundary-fair (Bfair) algorithm, we propose a period-aware task allocation heuristic with the goal of reducing the scheduling overhead (e.g., the number of scheduling points, context switches and task migrations). Simulation results indicate that the percentage of task sets that can be scheduled is significantly improved under cluster scheduling even for small-size clusters, compared to that of the partitioned scheduling. Moreover, when comparing to the simple generic task allocation scheme (e.g., first-fit), the proposed period-aware task allocation heuristic markedly reduces the scheduling overhead of cluster scheduling with the Bfair scheduler. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
243. The Continuities of Nonadditive Functions on Effect Algebras.
- Author
-
Lin, Qingshui and Li, Ronglu
- Subjects
MATHEMATICAL analysis ,ALGEBRA ,MATHEMATICAL functions ,MONOTONE operators ,OPERATOR theory ,ALGORITHMS - Abstract
In this paper, we study the strongly continuities, monotone autocontinuities of functions defined on effect algebras from above and below, respectively, we also present some examples to show that the autocontinuity, order continuity and monotone autocontinuity of functions defined on effect algebras are different each other. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
244. Two-Tape Finite Automata with Quantum and Classical States.
- Author
-
Zheng, Shenggen, Li, Lvzhou, and Qiu, Daowen
- Subjects
SEQUENTIAL machine theory ,QUANTUM theory ,ALGORITHMS ,MATHEMATICAL models ,DETERMINISTIC chaos ,MATHEMATICAL analysis - Abstract
Two-way finite automata with quantum and classical states (2QCFA) were introduced by Ambainis and Watrous, and two-way two-tape deterministic finite automata (2TFA) were introduced by Rabin and Scott. In this paper we study 2TFA and propose a new computing model called two-way two-tape finite automata with quantum and classical states (2TQCFA). First, we give efficient 2TFA algorithms for identifying languages which can be recognized by 2QCFA. Second, we give efficient 2TQCFA algorithms to recognize several languages whose status vis-a-vis 2QCFA have been posed as open questions, such as $L_{\mathit{square}}=\{a^{n}b^{n^{2}}\mid n\in \mathbf{N}\}$. Third, we show that $\{a^{n}b^{n^{k}}\mid n\in \mathbf{N}\}$ can be recognized by ( k+1)- tape deterministic finite automata (( k+1)TFA). Finally, we introduce k- tape automata with quantum and classical states ( kTQCFA) and prove that $\{a^{n}b^{n^{k}}\mid n\in \mathbf{N}\}$ can be recognized by kTQCFA. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
245. Mutual Information Analysis: a Comprehensive Study.
- Author
-
Batina, Lejla, Gierlichs, Benedikt, Prouff, Emmanuel, Rivain, Matthieu, Standaert, François-Xavier, and Veyrat-Charvillon, Nicolas
- Subjects
PROBABILITY theory ,MICROCONTROLLERS ,CRYPTOGRAPHY ,ALGORITHMS ,ELECTROMAGNETISM ,MATHEMATICAL analysis ,ESTIMATION theory - Abstract
Mutual Information Analysis is a generic side-channel distinguisher that has been introduced at CHES 2008. It aims to allow successful attacks requiring minimum assumptions and knowledge of the target device by the adversary. In this paper, we compile recent contributions and applications of MIA in a comprehensive study. From a theoretical point of view, we carefully discuss its statistical properties and relationship with probability density estimation tools. From a practical point of view, we apply MIA in two of the most investigated contexts for side-channel attacks. Namely, we consider first-order attacks against an unprotected implementation of the DES in a full custom IC and second-order attacks against a masked implementation of the DES in an 8-bit microcontroller. These experiments allow to put forward the strengths and weaknesses of this new distinguisher and to compare it with standard power analysis attacks using the correlation coefficient. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
246. Some observations on HC-128.
- Author
-
Maitra, Subhamoy, Paul, Goutam, Raizada, Shashwat, Sen, Subhabrata, and Sengupta, Rudradev
- Subjects
CRYPTOGRAPHY ,DISTRIBUTION (Probability theory) ,CIPHERS ,NUMERICAL solutions to equations ,MATHEMATICAL notation ,SIGNS & symbols ,DATA protection ,ALGORITHMS ,MATHEMATICAL analysis - Abstract
In this paper, we study HC-128 in detail from cryptanalytic point of view. First, we use linear approximation of the addition modulo 2 of three n-bit integers to identify linear approximations of g, g, the feedback functions of HC-128. This, in turn, shows that the process of keystream output generation of HC-128 can be well approximated by linear functions. In this direction, we show that the 'least significant bit' based distinguisher (presented by the designer himself) of HC-128 works for the complete 32-bit word. Using the above linear approximations of g, g, we present a new distinguisher for HC-128 which is slightly weaker than Wu's distinguisher. Finally, in the line of Dunkelman's observation, we also study how HC-128 keystream words leak secret state information of the cipher due to the properties of the functions h, h and present improved results. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
247. Efficient branch-and-bound algorithms for weighted MAX-2-SAT.
- Author
-
Ibaraki, Toshihide, Imamichi, Takashi, Koga, Yuichi, Nagamochi, Hiroshi, Nonobe, Koji, and Yagiura, Mutsunori
- Subjects
ALGORITHMS ,COMBINATORICS ,MATHEMATICAL variables ,ALGEBRA ,MATHEMATICAL analysis ,MATHEMATICS - Abstract
MAX-2-SAT is one of the representative combinatorial problems and is known to be NP-hard. Given a set of m clauses on n propositional variables, where each clause contains at most two literals and is weighted by a positive real, MAX-2-SAT asks to find a truth assignment that maximizes the total weight of satisfied clauses. In this paper, we propose branch-and-bound exact algorithms for MAX-2-SAT utilizing three kinds of lower bounds. All lower bounds are based on a directed graph that represents conflicts among clauses, and two of them use a set covering representation of MAX-2-SAT. Computational comparisons on benchmark instances disclose that these algorithms are highly effective in reducing the number of search tree nodes as well as the computation time. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
248. Log-Linear Convergence and Divergence of the Scale-Invariant (1+1)-ES in Noisy Environments.
- Author
-
Jebalia, Mohamed, Auger, Anne, and Hansen, Nikolaus
- Subjects
MATHEMATICAL optimization ,MATHEMATICAL analysis ,ALGORITHMS ,STOCHASTIC convergence ,LOG-linear models - Abstract
Noise is present in many real-world continuous optimization problems. Stochastic search algorithms such as Evolution Strategies (ESs) have been proposed as effective search methods in such contexts. In this paper, we provide a mathematical analysis of the convergence of a (1+1)-ES on unimodal spherical objective functions in the presence of noise. We prove for a multiplicative noise model that for a positive expected value of the noisy objective function, convergence or divergence happens depending on the infimum of the support of the noise. Moreover, we investigate convergence rates and show that log-linear convergence is preserved in presence of noise. This result is a strong theoretical foundation of the robustness of ESs with respect to noise. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
249. Weak Derandomization of Weak Algorithms: Explicit Versions of Yao's Lemma.
- Author
-
Shaltiel, Ronen
- Subjects
ALGORITHMS ,PROBABILITY theory ,COMPUTATIONAL complexity ,MACHINE theory ,MATHEMATICAL functions ,MATHEMATICAL analysis - Abstract
simple averaging argument shows that given a randomized algorithm A and a function f such that for every input x, Pr[ A( x) = f( x)] ≥ 1 − ρ (where the probability is over the coin tosses of A), there exists a non-uniform deterministic algorithm B 'of roughly the same complexity' such that Pr[ B( x) = f( x)] ≥ 1 − ρ (where the probability is over a uniformly chosen input x). This implication is often referred to as 'the easy direction of Yao's lemma' and can be thought of as 'weak derandomization' in the sense that B is deterministic but only succeeds on most inputs. The implication follows as there exists a fixed value r′ for the random coins of A such that 'hardwiring r′ into A' produces a deterministic algorithm B. However, this argument does not give a way to explicitly construct B. In this paper, we consider the task of proving uniform versions of the implication above. That is, how to explicitly construct a deterministic algorithm B when given a randomized algorithm A. We prove such derandomization results for several classes of randomized algorithms. These include randomized communication protocols, randomized decision trees (here we improve a previous result by Zimand), randomized streaming algorithms, and randomized algorithms computed by polynomial-size constant-depth circuits. Our proof uses an approach suggested by Goldreich and Wigderson and 'extracts randomness from the input'. We introduce a new type of (seedless) extractors that extract randomness from distributions that are 'recognizable' by the given randomized algorithm. We show that such extractors produce randomness that is in some sense not correlated with the input. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
250. Algorithms for Producing and Ordering Lexical and Nonlexical Sequences out of One Element.
- Author
-
Abboud, Elias
- Subjects
MATHEMATICAL sequences ,ALGORITHMS ,TOPOLOGICAL degree ,MATHEMATICAL analysis ,PRIME numbers ,DIFFERENTIABLE dynamical systems ,COMBINATORICS - Abstract
This paper deals with algorithms for producing and ordering lexical and nonlexical sequences of a given degree. The notion of 'elementary operations' on positive α-sequences is introduced. Our main theorem answers the question of when two lexical sequences are adjacent. Given any lexical sequence, α ∈ L, we can produce its adjacent successor as follows; apply one elementary operation on the tail of the longest left sequence, of even length, which gives a lexical successor α′ ∈ L, then compute the fundamental sequence $${f = \alpha \wedge \alpha\prime \in L_{m}}$$ and conclude for $${m \nmid n}$$ that α is adjacent to α′ in L. Whereas for m | n, the sequence α is adjacent to a sequence by f and the least element of L, where $${{d = \frac{n}{m}}}$$. Thus, while right sequences control the lexicality property of an α-sequence, it turns out that left sequences control the adjacency property of lexical and nonlexical sequences. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.