Randomized and quantum algorithms yield a speed-up for initial-value problems

Quantum algorithms and complexity have recently been studied not only for discrete, but also for some numerical problems. Most attention has been paid so far to the integration and approximation problems, for which a speed-up is shown in many important cases by quantum computers with respect to deterministic and randomized algorithms on a classical computer. In this paper, we deal with the randomized and quantum complexity of initial-value problems. For this nonlinear problem, we show that both randomized and quantum algorithms yield a speed-up over deterministic algorithms. Upper bounds on the complexity in the randomized and quantum settings are shown by constructing algorithms with a suitable cost, where the construction is based on integral information. Lower bounds result from the respective bounds for the integration problem.     

A new parallel chasing algorithm for transforming arrowhead matrices to tridiagonal form

Rutishauser, Gragg and Harrod and finally H.Y. Zha used the same class of chasing algorithms for transforming arrowhead matrices to tridiagonal form. Using a graphical theoretical approach, we propose a new chasing algorithm. Although this algorithm has the same sequential computational complexity and backward error properties as the old algorithms, it is better suited for a pipelined approach. The parallel algorithm for this new chasing method is described, with performance results on the Paragon and nCUBE. Comparison results between the old and the new algorithms are also presented.

     

Minimum-weight cycle covers and their approximability

A cycle cover of a graph is a set of cycles such that every vertex is part of exactly one cycle. An L-cycle cover is a cycle cover in which the length of every cycle is in the set L⊆N.We investigate how well L-cycle covers of minimum weight can be approximated. For undirected graphs, we devise non-constructive polynomial-time approximation algorithms that achieve constant approximation ratios for all sets L. On the other hand, we prove that the problem cannot be approximated with a factor of 2−ε for certain sets L.For directed graphs, we devise non-constructive polynomial-time approximation algorithms that achieve approximation ratios of O(n), where n is the number of vertices. This is asymptotically optimal: We show that the problem cannot be approximated with a factor of o(n) for certain sets L.To contrast the results for cycle covers of minimum weight, we show that the problem of computing L-cycle covers of maximum weight can, at least in principle, be approximated arbitrarily well.     

Space-efficient geometric divide-and-conquer algorithms

We develop a number of space-efficient tools including an approach to simulate divide-and-conquer space-efficiently, stably selecting and unselecting a subset from a sorted set, and computing the kth smallest element in one dimension from a multi-dimensional set that is sorted in another dimension. We then apply these tools to solve several geometric problems that have solutions using some form of divide-and-conquer. Specifically, we present a deterministic algorithm running in time using extra memory given inputs of size n for the closest pair problem and a randomized solution running in expected time and using extra space for the bichromatic closest pair problem. For the orthogonal line segment intersection problem, we solve the problem in time using extra space where n is the number of horizontal and vertical line segments and k is the number of intersections.     

Approximating average parameters of graphs

Inspired by Feige (36th STOC, 2004), we initiate a study of sublinear randomized algorithms for approximating average parameters of a graph. Specifically, we consider the average degree of a graph and the average distance between pairs of vertices in a graph. Since our focus is on sublinear algorithms, these algorithms access the input graph via queries to an adequate oracle. We consider two types of queries. The first type is standard neighborhood queries (i.e., what is the ith neighbor of vertex v?), whereas the second type are queries regarding the quantities that we need to find the average of (i.e., what is the degree of vertex v? and what is the distance between u and v?, respectively). Loosely speaking, our results indicate a difference between the two problems: For approximating the average degree, the standard neighbor queries suffice and in fact are preferable to degree queries. In contrast, for approximating average distances, the standard neighbor queries are of little help whereas distance queries are crucial. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

On the complexity of the car sequencing problem

In this note we give an easier proof of the known result that the car sequencing problem is NP-hard, and point out that it is NP-hard in the strong sense. We show that a previous claim of NP-completeness is incorrect, and instead we give a sufficient condition of membership of NP. We also provide a pseudo-polynomial algorithm for a special case.     

High‐performance direct algorithms for computing the sign function of triangular matrices

Algorithms and implementations for computing the sign function of a triangular matrix are fundamental building blocks for computing the sign of arbitrary square real or complex matrices. We present novel recursive and cache‐efficient algorithms that are based on Higham's stabilized specialization of Parlett's substitution algorithm for computing the sign of a triangular matrix. We show that the new recursive algorithms are asymptotically optimal in terms of the number of cache misses that they generate. One algorithm that we present performs more arithmetic than the nonrecursive version, but this allows it to benefit from calling highly optimized matrix multiplication routines; the other performs the same number of operations as the nonrecursive version, suing custom computational kernels instead. We present implementations of both, as well as a cache‐efficient implementation of a block version of Parlett's algorithm. Our experiments demonstrate that the blocked and recursive versions are much faster than the previous algorithms and that the inertia strongly influences their relative performance, as predicted by our analysis.     

A distance based rule for removing population members in genetic algorithms

In this paper we propose a new rule for removal of population members. We tested the new approach for solving the Quadratic Assignment Problem with excellent results.Received: January 2005, AMS classification: 68T20, 90C59     

Approximating Huffman codes in parallel

In this paper we present new results on the approximate parallel construction of Huffman codes. Our algorithm achieves linear work and logarithmic time, provided that the initial set of elements is sorted. This is the first parallel algorithm for that problem with the optimal time and work. Combining our approach with the best known parallel sorting algorithms we can construct an almost optimal Huffman tree with optimal time and work. This also leads to the first parallel algorithm that constructs exact Huffman codes with maximum codeword length H in time O(H) with n/logn processors, if the elements are sorted.     

Approximation algorithms for constrained generalized tree alignment problem

In generalized tree alignment problem, we are given a set S of k biologically related sequences and we are interested in a minimum cost evolutionary tree for S. In many instances of this problem partial phylogenetic tree for S is known. In such instances, we would like to make use of this knowledge to restrict the tree topologies that we consider and construct a biologically relevant minimum cost evolutionary tree. So, we propose the following natural generalization of the generalized tree alignment problem, a problem known to be MAX-SNP Hard, stated as follows:

Constrained Generalized Tree Alignment Problem [S. Divakaran, Algorithms and heuristics for constrained generalized alignment problem, DIMACS Technical Report 2007-21, 2007]: Given a set S of k related sequences and a phylogenetic forest comprising of node-disjoint phylogenetic trees that specify the topological constraints that an evolutionary tree of S needs to satisfy, construct a minimum cost evolutionary tree for S.

In this paper, we present constant approximation algorithms for the constrained generalized tree alignment problem. For the generalized tree alignment problem, a special case of this problem, our algorithms provide a guaranteed error bound of 2−2/k.     

Dynamic multi-dimensional bin packing

A natural generalization of the classical online bin packing problem is the dynamic bin packing problem introduced by Coffman et al. (1983) [7]. In this formulation, items arrive and depart and the objective is to minimize the maximal number of bins ever used over all times. We study the oriented multi-dimensional dynamic bin packing problem for two dimensions, three dimensions and multiple dimensions. Specifically, we consider dynamic packing of squares and rectangles into unit squares and dynamic packing of three-dimensional cubes and boxes into unit cubes. We also study dynamic d-dimensional hypercube and hyperbox packing. For dynamic d-dimensional box packing we define and analyze the algorithm NFDH for the offline problem and present a dynamic version. This algorithm was studied before for rectangle packing and for square packing and was generalized only for multi-dimensional cubes. We present upper and lower bounds for each of these cases.     

Testing the diameter of graphs

We propose a general model for testing graph properties, which extends and simplifies the bounded degree model of Goldreich and Ron [Property Testing in Bounded Degree Graphs, Proc. 31st Annual ACM Symposium on the Theory of Computing, 1997, pp. 406–415.] In this model, we present a family of algorithms that test whether the diameter of a graph is bounded by a given parameter D, or is ?‐far from any graph with diameter at most β(D). The function β(D) ranges between D+4 and 4D+2, depending on the algorithm. All our algorithms run in time polynomial in 1/?. © 2002 Wiley Periodicals, Inc. Random Struct. Alg. 20: 165–183, 2002     

Searching for a subset of counterfeit coins: Randomization vs determinism and adaptiveness vs non‐adaptiveness

We are given n coins of which k are heavy (defective), while the remaining n ‐ k are light (good). We know both the weight of the good coins and the weight of the defective ones. Therefore, if we weigh a subset Q ? S with a spring scale, then the outcome will tell us exactly the number of defectives contained in Q. The problem, known as Counterfeit Coins problem, is to identify the set of defective coins by minimizing the number of weighings, also called queries. It is well known that Θ(klog _{k +1}(n/k)) queries are enough, even for non‐adaptive algorithms, in case k ≤ cn for some constant 0 < c < 1. A natural interesting generalization arises when we are required to identify any subset of m ≤ k defectives. We show that while for randomized algorithms \begin{align*}\tilde{\Theta}(m)\end{align*} queries are sufficient, the deterministic non‐adaptive counterpart still requires Θ(klog _{k +1}(n/k)) queries, in case k ≤ n/2⁸; therefore, finding any subset of defectives is not easier than finding all of them by a non‐adaptive deterministic algorithm. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

Computational acceleration of projection algorithms for the linear best approximation problem

This is an experimental computational account of projection algorithms for the linear best approximation problem. We focus on the sequential and simultaneous versions of Dykstra’s algorithm and the Halpern-Lions-Wittmann-Bauschke algorithm for the best approximation problem from a point to the intersection of closed convex sets in the Euclidean space. These algorithms employ different iterative approaches to reach the same goal but no mathematical connection has yet been found between their algorithmic schemes. We compare these algorithms on linear best approximation test problems that we generate so that the solution will be known a priori and enable us to assess the relative computational merits of these algorithms. For the simultaneous versions we present a new component-averaging variant that substantially accelerates their initial behavior for sparse systems.     

Distributed algorithms for weighted problems in sparse graphs

We study distributed algorithms for three graph-theoretic problems in weighted trees and weighted planar graphs. For trees, we present an efficient deterministic distributed algorithm which finds an almost exact approximation of a maximum-weight matching. In addition, in the case of trees, we show how to approximately solve the minimum-weight dominating set problem. For planar graphs, we present an almost exact approximation for the maximum-weight independent set problem.     

Minimization Algorithms Based on Supervisor and Searcher Cooperation

In the present work, we explore a general framework for the design of new minimization algorithms with desirable characteristics, namely, supervisor-searcher cooperation. We propose a class of algorithms within this framework and examine a gradient algorithm in the class. Global convergence is established for the deterministic case in the absence of noise and the convergence rate is studied. Both theoretical analysis and numerical tests show that the algorithm is efficient for the deterministic case. Furthermore, the fact that there is no line search procedure incorporated in the algorithm seems to strengthen its robustness so that it tackles effectively test problems with stronger stochastic noises. The numerical results for both deterministic and stochastic test problems illustrate the appealing attributes of the algorithm.     

An O(n 3 L) adaptive path following algorithm for a linear complementarity problem

In this paper we propose an O(n ³ L) algorithm which is a modification of the path following algorithm [8] for a linear complementarity problem. The path following algorithm has to take a short step size in each iteration in order to bound the number of overall arithmetic operations by O(n ³ L). In practical computation, we can determine the step size adaptively. Mizuno, Yoshise, and Kikuchi [11] reported that such an adaptive algorithm required about O(L) iterations for some test problems. Here we show that we can use a rank one update technique in the adaptive algorithm so that the number of overall arithmetic operations is theoretically bounded by O(n ³ L).Research supported in part by the U.S. Army Research Office through the Mathematical Sciences Institute of Cornell University.Research supported in part by NSF grants ECS-8602534 and DMS-8904406 and ONR contract N-00014-87-K0212.     

New Self-Concordant Barrier for the Hypercube

We introduce a new barrier function to build new interior-point algorithms to solve optimization problems with bounded variables. First, we show that this function is a (3/2)n-self-concordant barrier for the unitary hypercube [0,1] ⁿ , assuring thus the polynomial property of related algorithms. Second, using the Hessian metric of that barrier, we present new explicit algorithms from the point of view of Riemannian geometry applications. Third, we prove that the central path defined by the new barrier to solve a certain class of linearly constrained convex problems maintains most of the properties of the central path defined by the usual logarithmic barrier. We present also a primal long-step path-following algorithm with similar complexity to the classical barrier. Finally, we introduce a new proximal-point Bregman type algorithm to solve linear problems in [0,1] ⁿ and prove its convergence. P.R. Oliveira was partially supported by CNPq/Brazil.     

Memetic Algorithms: The Polynomial Local Search Complexity Theory Perspective

In previous work (Krasnogor, . In: Studies on the Theory and Design Space of Memetic Algorithms. Ph.D. thesis, University of the West of England, Bristol, UK, 2002; Krasnogor and Smith, IEEE Trans Evol Algorithms 9(6):474–488, 2005) we develop a syntax-only classification of evolutionary algorithms, in particular so-called memetic algorithms (MAs). When “syntactic sugar” is added to our model, we are able to investigate the polynomial local search (PLS) complexity of memetic algorithms. In this paper we show the PLS-completeness of whole classes of problems that occur when memetic algorithms are applied to the travelling salesman problem using a range of mutation, crossover and local search operators. Our PLS-completeness results shed light on the worst case behaviour that can be expected of a memetic algorithm under these circumstances. Moreover, we point out in this paper that memetic algorithms for graph partitioning and maximum network flow (both with important practical applications) also give rise to PLS-complete problems.

---

Electronic Supplementary Material The online version of this article (doi:) contains supplementary material, which is available to authorized users.      

LP-based online scheduling: from single to parallel machines

We study classic machine sequencing problems in an online setting. Specifically, we look at deterministic and randomized algorithms for the problem of scheduling jobs with release dates on identical parallel machines, to minimize the sum of weighted completion times: Both preemptive and non-preemptive versions of the problem are analyzed. Using linear programming techniques, borrowed from the single machine case, we are able to design a 2.62-competitive deterministic algorithm for the non-preemptive version of the problem, improving upon the 3.28-competitive algorithm of Megow and Schulz. Additionally, we show how to combine randomization techniques with the linear programming approach to obtain randomized algorithms for both versions of the problem with competitive ratio strictly smaller than 2 for any number of machines (but approaching two as the number of machines grows). Our algorithms naturally extend several approaches for single and parallel machine scheduling. We also present a brief computational study, for randomly generated problem instances, which suggests that our algorithms perform very well in practice. A preliminary version of this work appears in the Proceedings of the 11th conference on integer programming and combinatorial optimization (IPCO), Berlin, 8–10 June 2005.