On an expansion of nondeterministic finite automata

We consider a possible generalization of nondeterministic finite automata. The goals of this consideration are: to apply some obtained algorithms for various problems of minimization of classical nondeterministic automata; to use such automata for describing practical anytime algorithms for the same problems of minimization; to simplify some proofs for algorithms of simplification for usual nondeterministic automata.     

Drawing series parallel digraphs symmetrically

In this paper we present algorithms for drawing series parallel digraphs with as much symmetry as possible. The first step is to compute a certain kind of automorphism, called an “upward planar automorphism” for an input series parallel digraph. The next step uses these automorphisms to construct a symmetric drawing of the graph. We present several variations of the second step, with visibility drawings, “bus-orthogonal” drawings, and polyline drawings. All algorithms run in linear time.     

Parallel radial basis function methods for the global optimization of expensive functions

We introduce a master–worker framework for parallel global optimization of computationally expensive functions using response surface models. In particular, we parallelize two radial basis function (RBF) methods for global optimization, namely, the RBF method by Gutmann [Gutmann, H.M., 2001a. A radial basis function method for global optimization. Journal of Global Optimization 19(3), 201–227] (Gutmann-RBF) and the RBF method by Regis and Shoemaker [Regis, R.G., Shoemaker, C.A., 2005. Constrained global optimization of expensive black box functions using radial basis functions, Journal of Global Optimization 31, 153–171] (CORS-RBF). We modify these algorithms so that they can generate multiple points for simultaneous evaluation in parallel. We compare the performance of the two parallel RBF methods with a parallel multistart derivative-based algorithm, a parallel multistart derivative-free trust-region algorithm, and a parallel evolutionary algorithm on eleven test problems and on a 6-dimensional groundwater bioremediation application. The results indicate that the two parallel RBF algorithms are generally better than the other three alternatives on most of the test problems. Moreover, the two parallel RBF algorithms have comparable performances on the test problems considered. Finally, we report good speedups for both parallel RBF algorithms when using a small number of processors.     

Nested Benders decomposition and dynamic programming for reservoir optimisation

This paper presents a computational comparison of nested Benders decomposition and dynamic programming (DP) for stochastic optimisation problems arising from the optimisation of hydro-electric generation from hydraulically linked reservoirs. The examples considered have between 3 and 17 reservoirs, two weather states, three runoff patterns and five periods. The examples are solved exactly by the simplex method and nested Benders decomposition and solved approximately by discrete dynamic programming (DP). A full version of DP is used for examples with 3 and 4 reservoirs, and a decomposition method is used for all examples. The full DP results are within 1% of optimal and the DP decomposition results are within 3.2% of optimal. Timings are given for serial and parallel versions of the algorithms. An analysis is given of how the different methods scale with the number of periods, reservoirs, weather states and runoff patterns, and also how applicable they are to more general problems.     

Interpolation of Sparse Multivariate Polynomials over Large Finite Fields with Applications

We develop a Las Vegas-randomized algorithm which performs interpolation of sparse multivariate polynomials over finite fields. Our algorithm can be viewed as the first successful adaptation of the sparse polynomial interpolation algorithm for the complex field developed by M. Ben-Or and P. Tiwari (1988, in “Proceedings of the 20th ACM Symposium on the Theory of Computing,” pp. 301–309, Assoc. Comput. Mach., New York) to the case of finite fields. It improves upon a previous result by D. Y. Grigoriev, M. Karpinski, and M. F. Singer (1990, SIAM J. Comput.19, 1059–1063) and is by far the most time efficient algorithm (time and processor efficient parallel algorithm) for the problem when the finite field is large. As applications, we obtain Monte Carlo-randomized parallel algorithms for sparse multivariate polynomial factorization and GCD over finite fields. The efficiency of these algorithms improves upon that of the previously known algorithms for the respective problems.     

Efficient Algorithms for Finding the Maximum Number of Disjoint Paths in Grids

In a rectangular grid, given two sets of nodes, (sources) and (sinks), of size each, the disjoint paths (DP) problem is to connect as many nodes in to the nodes in using a set of “disjoint” paths. (Both edge-disjoint and vertex-disjoint cases are considered in this paper.) Note that in this DP problem, a node in can be connected to any node in . Although in general the sizes of and do not have to be the same, algorithms presented in this paper can also find the maximum number of disjoint paths pairing nodes in and . We use the network flow approach to solve this DP problem. By exploiting all the properties of the network, such as planarity and regularity of a grid, integral flow, and unit capacity source/sink/flow, we can optimally compress the size of the working grid (to be defined) from O(N²) to O(N^1.5) and solve the problem in O(N^2.5) time for both the edge-disjoint and vertex-disjoint cases, an improvement over the straightforward approach which takes O(N³) time.     

Generalizing the modeling of fuzzy logic controllers by parameterized aggregation operators

We describe the type of reasoning used in the typical fuzzy logic controller, the Mamdani reasoning method. We point out the basic assumptions in this model. We discuss the S-OWA operators which provide families of parameterized “andlike” and “orlike” operators. We generalize the Mamdani model by introducing these operators. We introduce a method, which we call Direct Fuzzy Reasoning (DFR), which results from one choice of the parameters. We develop some learning algorithms for the new method. We show how the Takagi-Sugeno-Kang (TSK) method of reasoning is an example of this DFR method.     

A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem

Dynamic programming (DP) algorithms for the traveling salesman problem (TSP) can easily incorporate time dependent travel times, time windows, and precedence relationships which present difficulties for algorithms based on linear or nonlinear programming formulations and for many TSP heuristics. However, exact DP algorithms for the TSP have exponential storage and computational time requirements and can solve only very small problems. We present a restricted DP heuristic (a generalization of the nearest neighbor heuristic) that can include all the above considerations but solves much larger problems. The heuristic cannot guarantee optimality because only a userspecified specified number of partial tours is retained at each stage. In this paper, the heuristic is implemented for the time dependent traveling salesman problem and is tested on a personal computer on randomly generated problems. The quality of the solution improves, on average, as more computational time is permitted.     

Polygonal chains cannot lock in 4D

We prove that, in all dimensions d4, every simple open polygonal chain and every tree may be straightened, and every simple closed polygonal chain may be convexified. These reconfigurations can be achieved by algorithms that use polynomial time in the number of vertices, and result in a polynomial number of “moves”. These results contrast to those known for d=2, where trees can “lock”, and for d=3, where open and closed chains can lock.     

Modeling and analysis using hybrid Petri nets

This paper is devoted to the use of hybrid Petri nets (PNs) for modeling and control of hybrid dynamic systems (HDS). Modeling, analysis and control of HDS attract ever more of researchers’ attention and several works have been devoted to these topics. We consider in this paper the extensions of the PN formalism (initially conceived for modeling and analysis of discrete event systems) in the direction of hybrid modeling. We present, first, the continuous PN models. These models are obtained from discrete PNs by the fluidification of the markings. They constitute the first steps in the extension of PNs toward hybrid modeling. Then, we present two hybrid PN models, which differ in the class of HDS they can deal with. The first one is used for deterministic HDS modeling, whereas the second one can deal with HDS with nondeterministic behavior.     

On parallel local search for permutations

We investigate some ways in which massively parallel computing devices can be exploited in local search algorithms. We show that the substantial speedups that can be gained from parallel neighbourhood evaluation enables an efficient best improvement local search, and that this in turn enables further speedups through selection and parallel application of a set of independent, improving moves. Our experiments demonstrate a total speedup of up to several hundred times compared to a classical, sequential best improvement search. We also demonstrate how an exchange of good partial solutions between the incumbent and best found solutions improves the efficiency of the Iterated Local Search algorithm.     

Incremental versus non-incremental dynamic programming

Many dynamic programming algorithms for discrete optimization problems are pure in that they only use min/max and addition operations in their recursions. Some of them, in particular those for various shortest path problems, are even incremental in that one of the inputs to the addition operations is a variable. We present an explicit optimization problem such that it can be solved by a pure DP algorithm using a polynomial number of operations, but any incremental DP algorithm for this problem requires a super-polynomial number of operations.     

The Interval Geometric Machine Model

This paper introduces the interval version of the Geometric Machine (GM) model, to model the semantics of algorithms of interval mathematics. Based on coherence spaces, the set of values storable in the GM memory is represented by the bi-structured coherence space of rational intervals, a constructive computational representation of the set of real intervals. Over the inductive ordered structure called the coherence space of processes, the representation of parallel and nondeterministic processes operating on the array structures of the GM memory is obtained. The infinite GM memory, supporting a coherence space of states, is conceived as the set of points of a geometric space. Using this framework, a domain-theoretic semantics of interval algorithms is presented.     

Cut-threshold graphs

We study the structure of the networks in which connectedness and disconnectedness can be expressed by a threshold system. This means that the elements of the network have a certain “destruction cost” and that the enemy can disconnect the network if and only if they pay a large enough price. We give polynomial algorithms for the recognition of such networks, and for the determination of the appropriate costs and threshold value.     

What Monte Carlo models can do and cannot do efficiently?

The question “what Monte Carlo models can do and cannot do efficiently” is discussed for some functional spaces that define the regularity of the input data. Data classes important for practical computations are considered: classes of functions with bounded derivatives and Hölder type conditions, as well as Korobov-like spaces.

Theoretical performance analysis of some algorithms with unimprovable rate of convergence is given. Estimates of computational complexity of two classes of algorithms – deterministic and randomized for both problems – numerical multidimensional integration and calculation of linear functionals of the solution of a class of integral equations are presented.     

Structural filtering: a paradigm for efficient and exact geometric programs

We introduce a new and simple filtering technique that can be used in the implementation of geometric algorithms called “structural filtering”. Using this filtering technique we gain about 20% when compared to predicate-filtered implementations. Of theoretical interest are some results regarding the robustness of sorting algorithms against erroneous comparisons.

There is software support for the concept of structural filtering in LEDA (Library of Efficient Data Types and Algorithms, http://www.mpi-sb.mpg.de/LEDA/leda.html) and CGAL (Computational Geometry Algorithms Library, http://www.cgal.org).     

Algorithms for the Laplace–Stieltjes Transforms of First Return Times for Stochastic Fluid Flows

We derive several algorithms, including quadratically convergent algorithms, which can be used to calculate the Laplace–Stieltjes transforms of the time taken to return to the initial level in the Markovian stochastic fluid flow model. We give physical interpretations of the algorithms and consider their numerical analysis. The numerical performance of the algorithms, which depends on the physical properties of the process, is discussed and illustrated with simple examples. Besides the powerful algorithms, this paper contributes interesting theoretical results. In particular, the methodology for constructing these algorithms is a valuable contribution to the theory of fluid flow models. Moreover, useful physical interpretations of the algorithms, and related expressions, given in terms of the fluid flow model, can assist in further analysis and help in a better understanding of the model. The authors would like to thank the Australian Research Council for funding this research through Discovery Project DP0770388.     

Novel modifications of parallel Jacobi algorithms

We describe two main classes of one-sided trigonometric and hyperbolic Jacobi-type algorithms for computing eigenvalues and eigenvectors of Hermitian matrices. These types of algorithms exhibit significant advantages over many other eigenvalue algorithms. If the matrices permit, both types of algorithms compute the eigenvalues and eigenvectors with high relative accuracy. We present novel parallelization techniques for both trigonometric and hyperbolic classes of algorithms, as well as some new ideas on how pivoting in each cycle of the algorithm can improve the speed of the parallel one-sided algorithms. These parallelization approaches are applicable to both distributed-memory and shared-memory machines. The numerical testing performed indicates that the hyperbolic algorithms may be superior to the trigonometric ones, although, in theory, the latter seem more natural.     

A binary decision diagram based algorithm for solving a class of binary two-stage stochastic programs

We consider a special class of two-stage stochastic integer programming problems with binary variables appearing in both stages. The class of problems we consider constrains the second-stage variables to belong to the intersection of sets corresponding to first-stage binary variables that equal one. Our approach seeks to uncover strong dual formulations to the second-stage problems by transforming them into dynamic programming (DP) problems parameterized by first-stage variables. We demonstrate how these DPs can be formed by use of binary decision diagrams, which then yield traditional Benders inequalities that can be strengthened based on observations regarding the structure of the underlying DPs. We demonstrate the efficacy of our approach on a set of stochastic traveling salesman problems.