An algorithm for computing Bingham flows

A three-parameter iterative method for computing Bingham flows is examined. The method is a generalization of the well-known Arrow-Hurwicz algorithm. The local convergence of the method is proved.     

An algorithm for decomposing a polynomial system into normal ascending sets

We present an algorithm to decompose a polynomial system into a finite set of normal ascending sets such that the set of the zeros of the polynomial system is the union of the sets of the regular zeros of the normal ascending sets.If the polynomial system is zero dimensional,the set of the zeros of the polynomials is the union of the sets of the zeros of the normal ascending sets.     

A new arc algorithm for unconstrained optimization

The gradient path of a real valued differentiable function is given by the solution of a system of differential equations. For a quadratic function the above equations are linear, resulting in a closed form solution. A quasi-Newton type algorithm for minimizing ann-dimensional differentiable function is presented. Each stage of the algorithm consists of a search along an arc corresponding to some local quadratic approximation of the function being minimized. The algorithm uses a matrix approximating the Hessian in order to represent the arc. This matrix is updated each stage and is stored in its Cholesky product form. This simplifies the representation of the arc and the updating process. Quadratic termination properties of the algorithm are discussed as well as its global convergence for a general continuously differentiable function. Numerical experiments indicating the efficiency of the algorithm are presented.     

A practical algorithm for decomposing polygonal domains into convex polygons by diagonals

We present algorithms for decomposing a polygon (with holes) into convex polygons by diagonals. The methods are computationally quick, and although the partitions that they produce may not have minimal cardinality they usually have a low number of convex pieces. Thus, the methods are suitable for being used when achieving a modest load on the CPU time is more important than finding optimal decompositions as, for instance, in location problems. Part of the results in this paper are from Fernández (1999), and were presented in Fernández et al. (1998). This work has been supported by the Ministry of Science and Technology of Spain under the research projects BEC2002-01026, SEJ2005-06273/ECON (J. Fernández, B. Tóth and B. Pelegrín) and TIC2003-05982-C05-03 (L. Cánovas), in part financed by the European Regional Development Fund (ERDF).     

Real-valued flows in a network with fuzzy arc capacities

The problem of the maximal (minimal) flow in a network with fuzzy capacity constraints is considered. A theorem being a natural direct generalization of the Ford-Fulkerson theorem relating the flow value with cut capacities in the network is proved. A simple algorithm, based on the mentioned theorem, for the determination of optimal real-valued flows is developed.     

A capacity scaling algorithm for convex cost submodular flows

This paper presents a scaling scheme for submodular functions. A small but strictly submodular function is added before scaling so that the resulting functions should be submodular. This scaling scheme leads to a weakly polynomial algorithm to solve minimum cost integral submodular flow problems with separable convex cost functions, provided that an oracle for exchange capacities is available.     

An improved block-interchange algorithm

In a block-interchange permutation, the positions of two nonoverlapping blocks of contiguous elements of a sequence are interchanged. We consider the problem of performing such a permutation by executing a series of transpositions, which exchange the positions of any two elements. A simple, elegant algorithm is known for doing this in time proportional to the number of elements that are either in the two blocks to be interchanged, or between them. We present a new algorithm which is always as fast and can be much faster than this known algorithm. We prove that our new algorithm performs the minimal number of transpositions.     

An improved rewriting-number algorithm

We discuss several improvements to an algorithm for computing the rewriting number of a group. Our improvements speed up the computation by a couple of orders of magnitude. With the faster algorithm, we have shown that the rewriting number of the symmetric groupS ₅ is 8.Supported by a fellowship from the Shell Oil Company Foundation.     

An improved algorithm for online machine minimization

The online machine minimization problem seeks to design a preemptive scheduling algorithm on multiple machines — each job $j$ arrives at its release time $r_j$, has to be processed for $p_j$ time units, and must be completed by its deadline $d_j$. The goal is to minimize the number of machines the algorithm uses. We improve the $O(logm)$-competitive algorithm by Chen, Megow and Schewior (SODA 2016) and provide an $O\left(\frac{logm}{loglogm}\right)$-competitive algorithm.     

An improved approximation algorithm for requirement cut

This note presents improved approximation guarantees for the requirement cut problem: given an n-vertex edge-weighted graph G=(V,E), and g groups of vertices X₁,…,X_g⊆V with each group X_i having a requirement r_i between 0 and |X_i|, the goal is to find a minimum cost set of edges whose removal separates each group X_i into at least r_i disconnected components. We give a tight Θ(logg) approximation ratio for this problem when the underlying graph is a tree, and show how this implies an O(logk⋅logg) approximation ratio for general graphs, where .     

An improved algorithm for detecting potential games

This note presents a simple necessary and sufficient condition for a game to be a potential game. My condition improves on the well-known condition in Monderer and Shapley (Games Econ Behav 14:124–143, 1996) in the sense that it leads to a significant reduction in the computational burden in determining whether a given game is a potential game. It also provides a logical connection between finite and continuous potential games, as it can be understood as a faithful translation of one type of characterization for a continuous potential game.     

A polynomial cycle canceling algorithm for submodular flows

Submodular flow problems, introduced by Edmonds and Giles [2], generalize network flow problems. Many algorithms for solving network flow problems have been generalized to submodular flow problems (cf. references in Fujishige [4]), e.g. the cycle canceling method of Klein [9]. For network flow problems, the choice of minimum-mean cycles in Goldberg and Tarjan [6], and the choice of minimum-ratio cycles in Wallacher [12] lead to polynomial cycle canceling methods. For submodular flow problems, Cui and Fujishige [1] show finiteness for the minimum-mean cycle method while Zimmermann [16] develops a pseudo-polynomial minimum ratio cycle method. Here, we prove pseudo-polynomiality of a larger class of the minimum-ratio variants and, by combining both methods, we develop a polynomial cycle canceling algorithm for submodular flow problems. Received July 22, 1994 / Revised version received July 18, 1997? Published online May 28, 1999     

Extrapolation methods for approximating arc length and surface area

A well-known method of estimating the length of a parametric curve in is to sample some points from it and compute the length of the polygon passing through them. In this paper we show that for uniform sampling of regular smooth curves, Richardson extrapolation can be applied repeatedly giving a sequence of derivative-free length estimates of arbitrarily high orders of accuracy. A similar result is derived for the approximation of the area of parametric surfaces.      

Integer version of the multipath flow network synthesis problem

We consider the following integer multipath flow network synthesis problem. We are given two positive integers q, n, (1<q<n), and a non-negative, integer, symmetric, n×n matrix R, each non-diagonal element r_ij of which represents the minimum requirement of q-path flow value between nodes i and j in an undirected network on the node set N={1,2,…,n}. We want to construct a simple, undirected network G=[N,E] with integer edge capacities {u_e:e∈E} such that each of these flow requirements can be realized (one at a time) and the sum of all the edge capacities is minimum. We present an O(n³) combinatorial algorithm for the problem and we show that the problem has integer rounding property.     

An improved adaptive trust-region algorithm

This paper gives a variant trust-region method, where its radius is automatically adjusted by using the model information gathered at the current and preceding iterations. The primary aim is to decrease the number of function evaluations and solving subproblems, which increases the efficiency of the trust-region method. The next aim is to update the new radius for large-scale problems without imposing too much computational cost to the scheme. Global convergence to first-order stationary points is proved under classical assumptions. Preliminary numerical experiments on a set of test problems from the CUTEst collection show that the presented method is promising for solving unconstrained optimization problems.     

An improved vertex enumeration algorithm

The main computational burden in pivoting methods for determining all vertices of a convex polytope appears to be in testing pairs of vertices for adjacency. We show how, in the Dyer-Proll algorithm, this burden can be reduced by a new labelling of the search tree and by a mechanism for removing redundant branches. We also introduce an implementation strategy, the barred pivot strategy, which further improves the algorithm's performance.     

An improved SQP algorithm for inequality constrained optimization

In this paper, the feasible type SQP method is improved. A new algorithm is proposed to solve nonlinear inequality constrained problem, in which a new modified method is presented to decrease the computational complexity. It is required to solve only one QP subproblem with only a subset of the constraints estimated as active per single iteration. Moreover, a direction is generated to avoid the Maratos effect by solving a system of linear equations. The theoretical analysis shows that the algorithm has global and superlinear convergence under some suitable conditions. In the end, numerical experiments are given to show that the method in this paper is effective.This work is supported by the National Natural Science Foundation (No. 10261001) and Guangxi Science Foundation (No. 0236001 and 0249003) of China. Acknowledgement.We would like to thank one anonymous referee for his valuable comments and suggestions, which greatly improved the quality of this paper.     

An improved simulated annealing algorithm for bandwidth minimization

In this paper, a simulated annealing algorithm is presented for the bandwidth minimization problem for graphs. This algorithm is based on three distinguished features including an original internal representation of solutions, a highly discriminating evaluation function and an effective neighborhood. The algorithm is evaluated on a set of 113 well-known benchmark instances of the literature and compared with several state-of-the-art algorithms, showing improvements of some previous best results.     

An improved algorithm for generalized comparison of minisatellites

One of the most important objects in genetic mapping and forensic studies are minisatellites. They consist of a heterogeneous tandem array of short repeat units called variants. The evolution of minisatellites is realized by tandem duplication and tandem deletion of variants. Jeffrey et al. proposed a method to obtain the sequence of variants, called maps. Bérard and Rivals designed the first algorithm of comparison of two minisatellite maps under an evolutionary model including deletion, insertion, mutation, amplification and contraction. The complexity of this first algorithm was O(n⁴) in time and O(n³) in space where n is the size of the maps. In this paper we propose a more efficient algorithm using the same generic evolutionary model which is O(n³) in time and O(n²) in space. Our algorithm with this better efficiency can even solve generalized and more refined models.