Algorithms over partially ordered sets

We here study some problems concerned with the computational analysis of finite partially ordered sets. We begin (in § 1) by showing that the matrix representation of a binary relationR may always be taken in triangular form ifR is a partial ordering. We consider (in § 2) the chain structure in partially ordered sets, answer the combinatorial question of how many maximal chains might exist in a partially ordered set withn elements, and we give an algorithm for enumerating all maximal chains. We give (in § 3) algorithms which decide whether a partially ordered set is a (lower or upper) semi-lattice, and whether a lattice has distributive, modular, and Boolean properties. Finally (in § 4) we give Algol realizations of the various algorithms.     

An inverse model for the most uniform problem

In this paper, we consider a kind of inverse model for the most uniform problem. This model has some practical background. It is shown that the model can be solved in polynomial time whenever an associated min-sum problem can be solved in polynomial time.     

A note on the generalized min-sum set cover problem

In this paper, we consider the generalized min-sum set cover problem, introduced by Azar, Gamzu, and Yin (STOC 2009). Bansal, Gupta, and Krishnaswamy (SODA 2010) give a 485-approximation algorithm for the problem. We are able to alter their algorithm and analysis to obtain a 28-approximation algorithm, improving the performance guarantee by an order of magnitude. We use concepts from α-point scheduling to obtain our improvements.     

A comparison of algorithms for the multivariate L 1-median

The L ₁-median is a robust estimator of multivariate location with good statistical properties. Several algorithms for computing the L ₁-median are available. Problem specific algorithms can be used, but also general optimization routines. The aim is to compare different algorithms with respect to their precision and runtime. This is possible because all considered algorithms have been implemented in a standardized manner in the open source environment R. In most situations, the algorithm based on the optimization routine NLM (non-linear minimization) clearly outperforms other approaches. Its low computation time makes applications for large and high-dimensional data feasible.     

Laplace eigenvalues and bandwidth-type invariants of graphs

For (weighted) graphs several labeling properties and their relation to the eigenvalues of the Laplacian matrix of a graph are considered. Several upper and lower bounds on the bandwidth and other min-sum problems are derived. Most of these bounds depend on Laplace eigenvalues of the graphs. The results are applied in the study of bandwidth and the min-sums of random graphs, random regular graphs, and Kneser graphs. © John Wiley & Sons, Inc.     

Hybridizing local search algorithms for global optimization

In this paper, we combine two types of local search algorithms for global optimization of continuous functions. In the literature, most of the hybrid algorithms are produced by combination of a global optimization algorithm with a local search algorithm and the local search is used to improve the solution quality, not to explore the search space to find independently the global optimum. The focus of this research is on some simple and efficient hybrid algorithms by combining the Nelder–Mead simplex (NM) variants and the bidirectional random optimization (BRO) methods for optimization of continuous functions. The NM explores the whole search space to find some promising areas and then the BRO local search is entered to exploit optimal solution as accurately as possible. Also a new strategy for shrinkage stage borrowed from differential evolution (DE) is incorporated in the NM variants. To examine the efficiency of proposed algorithms, those are evaluated by 25 benchmark functions designed for the special session on real-parameter optimization of CEC2005. A comparison study between the hybrid algorithms and some DE algorithms and non-parametric analysis of obtained results demonstrate that the proposed algorithms outperform most of other algorithms and their difference in most cases is statistically considerable. In a later part of the comparative experiments, a comparison of the proposed algorithms with some other evolutionary algorithms reported in the CEC2005 confirms a better performance of our proposed algorithms.     

Iterative scheduling algorithms based on the subdivision of the solution space into domains

Iterative multiprocessor scheduling algorithms are considered. The iterative algorithms make it possible to solve scheduling problems for a wide class of computer architectures but are very intricate from the computational point of view. To simplify the iterative algorithms, we propose an approach to their construction based on the subdivision of the space of correct schedules into disjoint domains, namely, an algorithm for constructing domains is proposed, the operations of the schedule transformations closed within the domains are introduced, and a technique for cutting off domains is developed. The approach developed also makes it possible to construct parallel algorithms with a low traffic of the exchange between parallel processes.     

A survey on the continuous nonlinear resource allocation problem

Our problem of interest consists of minimizing a separable, convex and differentiable function over a convex set, defined by bounds on the variables and an explicit constraint described by a separable convex function. Applications are abundant, and vary from equilibrium problems in the engineering and economic sciences, through resource allocation and balancing problems in manufacturing, statistics, military operations research and production and financial economics, to subproblems in algorithms for a variety of more complex optimization models. This paper surveys the history and applications of the problem, as well as algorithmic approaches to its solution. The most common techniques are based on finding the optimal value of the Lagrange multiplier for the explicit constraint, most often through the use of a type of line search procedure. We analyze the most relevant references, especially regarding their originality and numerical findings, summarizing with remarks on possible extensions and future research.     

An incremental clustering algorithm based on hyperbolic smoothing

Clustering is an important problem in data mining. It can be formulated as a nonsmooth, nonconvex optimization problem. For the most global optimization techniques this problem is challenging even in medium size data sets. In this paper, we propose an approach that allows one to apply local methods of smooth optimization to solve the clustering problems. We apply an incremental approach to generate starting points for cluster centers which enables us to deal with nonconvexity of the problem. The hyperbolic smoothing technique is applied to handle nonsmoothness of the clustering problems and to make it possible application of smooth optimization algorithms to solve them. Results of numerical experiments with eleven real-world data sets and the comparison with state-of-the-art incremental clustering algorithms demonstrate that the smooth optimization algorithms in combination with the incremental approach are powerful alternative to existing clustering algorithms.     

Monte Carlo methods in statistical physics: Mathematical foundations and strategies

Monte Carlo is a versatile and frequently used tool in statistical physics and beyond. Correspondingly, the number of algorithms and variants reported in the literature is vast, and an overview is not easy to achieve. In this pedagogical review, we start by presenting the probabilistic concepts which are at the basis of the Monte Carlo method. From these concepts the relevant free parameters—which still may be adjusted—are identified. Having identified these parameters, most of the tangled mass of methods and algorithms in statistical physics Monte Carlo can be regarded as realizations of merely a handful of basic strategies which are employed in order to improve convergence of a Monte Carlo computation. Once the notations introduced are available, many of the most widely used Monte Carlo methods and algorithms can be formulated in a few lines. In such a formulation, the core ideas are exposed and possible generalizations of the methods are less obscured by the details of a particular algorithm.     

Perturbation d'une matrice hermitienne ou normale

Summary Given a hermitian (normal) matrixA with known eigenelements, we study the behavior of these elements under a hermitian perturbationH. With a symmetric 2×2 matrix, the problem is explicit (algebraic equation of 2nd degree), and we try, in the case of ann×n hermitian matrix, to obtain upper bounds which are as close as possible of exact results forn=2. The results are collected in § I. They state in a unified manner some results of Davis [2], Gavurin [4], Golub [5], Kato-Temple [7], Ortega [3], Wilkinson [8] and others.In § II, we apply this theory to produce error bounds for eigenelements computed by theQR and Jacobi methods. The given error bounds are realistic and easy to compute during the algorithms. When the separation distance between eigenvalues ofA approaches zero, the problem of computing eigenelements ofA+H is ill-conditionned with respect to the eigenvalues, the eigenvectors being orthogonal. The precision then obtained is given.

---

Perturbation d'une matrice hermitienne ou normale

     

Order and type of basic sets of polynomials associated with functions of algebraic semi block matrices

§ 1 is an introduction to basic sets of polynomials and to algebraic infinite matrices. In § 2 we investigate the order of basic sets associated with functions of algebraic semi block matrices whose elements are of a certain order of magnitude. In § 3 we investigate the type of such basic sets.     

Incorrect problems in topological spaces

Conclusions 15. According to the methods of § 3 and § 4, we are considering the solution on a bicompact set M, taking as approximate solutions the elements of this set, i.e., we restrict X to a bicompact space M.By virtue of the corollary of Theorem 5, this re-establishes the stability of the problem. Thus by using bicompact sets and the related additional information about the solution, it is possible to go over from an incorrect problem to a problem which is correct in the sense of Tikhonov (see [19], p. 4).Translated from Sibirskii Matematicheskii Zhurnal, Vol. 10, No. 5, pp. 1065–1074, September–October, 1969.     

Chaotic convergence of the decision-directed blind equalization algorithm

Classically, adaptive equalization algorithms are analyzed in terms of two possible steady state behaviors: convergence to a fixed point and divergence to infinity. This twofold scenario suits well the modus operandi of linear supervised algorithms, but can be rather restrictive when unsupervised methods are considered, as their intrinsic use of higher-order statistics gives rise to nonlinear update expressions. In this work, we show, using different analytical tools belonging to dynamic system theory, that one of the most emblematic and studied unsupervised approaches – the decision-directed algorithm – is potentially capable of presenting behaviors, like convergence to limit-cycles and chaos, that transcend the aforementioned dichotomy. These results also indicate theoretical possibilities concerning step-size selection and initialization.     

Integration linearer Differentialgleichungen durch Laplacesche Integrale. II

Ohne ZusammenfassungFortsetzung der Arbeit auf S. 339–350 dieses Bandes. §3 und §4 knüpfen an §1 an, §5 ist von §1 unabhängig; §6 verallgemeinert §2.     

Learning about multiplication by comparing algorithms: “One times one,but actually they are ten times ten”

Multiplication algorithms in primary school are still frequently introduced with little attention to meaning. We present a case study focusing on a third grade class that engaged in comparing two algorithms and discussing “why they both work”. The objectives of the didactical intervention were to foster students' development of mathematical meanings concerning multiplication algorithms, and their development of an attitude to judge and compare the value and efficiency of different algorithms. Underlying hypotheses were that it is possible to promote the simultaneous unfolding of the semiotic potential of two algorithms, considered as cultural artifacts, with respect to the objectives of the didactical intervention, and to establish a fruitful synergy between the two algorithms. As results, this study sheds light onto the new theoretical construct of “bridging sign”, illuminating students’ meaning-making processes involving more than one artifact; and it provides important insight into the actual unfolding of the hypothesized potential of the algorithms.     

Combinatorial and experimental results for randomized point matching algorithms

The subject of this paper is the design and analysis of Monte Carlo algorithms for two basic matching techniques used in model-based recognition: alignment, and geometric hashing. We first give analyses of our Monte Carlo algorithms, showing that they are asymptotically faster than their deterministic counterparts while allowing failure probabilities that are provably very small. We then describe experimental results that bear out this speed-up, suggesting that randomization results in significant improvements in running time. Our theoretical analyses are not the best possible; as a step to remedying this we define a combinatorial measure of self-similarity for point sets, and give an example of its power.     

Linear Time Algorithms for Parallel Machine Scheduling

This paper addresses linear time algorithms for parallel machine scheduling problems. We introduce a kind of threshold algorithms and discuss their main features. Three linear time threshold algorithm classes DT, PT and DTm are studied thoroughly. For all classes, we study their best possible algorithms among each class. We also present their application to several scheduling problems, The new algorithms are better than classical algorithms in time complexity and/or worst-case ratio. Computer-aided proof technique is used in the proof of main results, which greatly simplifies the proof and decreases case by case analysis.     

Exact solutions of the simplified Keller–Segel model

Lie symmetries of a simplified Keller–Segel system are found and applied for construction of exact solutions. The algorithms for constructing all possible traveling wave and self-similar solutions of the system in question are presented. Several families of such solutions in an explicit form are found, their properties examined and possible applicability for chemotaxis modeling is discussed.     

The dial-a-ride problem: models and algorithms

The Dial-a-Ride Problem (DARP) consists of designing vehicle routes and schedules for n users who specify pickup and delivery requests between origins and destinations. The aim is to plan a set of m minimum cost vehicle routes capable of accommodating as many users as possible, under a set of constraints. The most common example arises in door-to-door transportation for elderly or disabled people. The purpose of this article is to review the scientific literature on the DARP. The main features of the problem are described and a summary of the most important models and algorithms is provided. This is an updated version of a paper that appeared in 4OR 1:89–101, 2003.