Computing power indices: Multilinear extensions and new characterizations

Johnston [Johnston, R.J., 1978. On the measurement of power: some reactions to Laver. Environment and Planning A 10, 907–914], Deegan and Packel [Deegan, J., Packel, E.W., 1979. A new index of power for simple n-person games. International Journal of Game Theory 7, 113–123], and Holler [Holler, M.J., 1982. Forming coalitions and measuring voting power. Political Studies 30, 262–271] proposed three power indices for simple games: Johnston index, Deegan–Packel index, and the Public Good Index. In this paper, methods to compute these indices by means of the multilinear extension of the game are presented. Furthermore, a new characterization of the Public Good Index is given. Our methods are applied to two real-world examples taken from the political field.     

An algorithm for generating minimal cutsets of undirected graphs

In this paper, we propose an algorithm for generating minimal cutsets of undirected graphs. The algorithm is based on a blocking mechanism for generating every minimal cutset exactly once. The algorithm has an advantage of not requiring any preliminary steps to find minimal cutsets. The algorithm generates minimal cutsets atO(e · n) {wheree,n = number of (edges, vertices) in the graph} computational effort per cutset. Formal proofs of the algorithm are presented.     

An electromagnetism metaheuristic for the unicost set covering problem

In this paper we propose a new heuristic algorithm to solve the unicost version of the well-known set covering problem. The method is based on the electromagnetism metaheuristic approach which, after generating a pool of solutions to create the initial population, applies a fixed number of local search and movement iterations based on the “electromagnetism” theory. In addition to some random aspects, used in the construction and local search phases, we also apply mutation in order to further escape from local optima.     

An O(n log m) algorithm for the Josephus Problem

The Josephus Problem can be described as follows: There are n objects arranged in a circle. Beginning with the first object, we move around the circle and remove every m th object. As each object is removed, the circle closes in. Eventually, all n objects will have been removed from the circle. The order in which the objects are removed induces a permutation on the integers 1 through n. Knuth has described two O(n log n) algorithms for generating this permuation. The problem of determining a more efficient algorithm for generating the permutation is left open. In this paper we give an O(n log m) algorithm.     

Quality mesh generation for molecular skin surfaces using restricted union of balls

Quality surface meshes for molecular models are desirable in the studies of protein shapes and functionalities. However, there is still no robust software that is capable to generate such meshes with good quality. In this paper, we present a Delaunay-based surface triangulation algorithm generating quality surface meshes for the molecular skin model. We expand the restricted union of balls along the surface and generate an ε-sampling of the skin surface incrementally. At the same time, a quality surface mesh is extracted from the Delaunay triangulation of the sample points. The algorithm supports robust and efficient implementation and guarantees the mesh quality and topology as well. Our results facilitate molecular visualization and have made a contribution towards generating quality volumetric tetrahedral meshes for the macromolecules.     

Gray code for permutations with a fixed number of cycles

We give the first Gray code for the set of n-length permutations with a given number of cycles. In this code, each permutation is transformed into its successor by a product with a cycle of length three, which is optimal. If we represent each permutation by its transposition array then the obtained list still remains a Gray code and this allows us to construct a constant amortized time (CAT) algorithm for generating these codes. Also, Gray code and generating algorithm for n-length permutations with fixed number of left-to-right minima are discussed.     

Generating partitions of a graph into a fixed number of minimum weight cuts

In this paper, we present an algorithm for the generation of all partitions of a graph G with positive edge weights into k mincuts. The algorithm is an enumeration procedure based on the cactus representation of the mincuts of G. We report computational results demonstrating the efficiency of the algorithm in practice and describe in more detail a specific application for generating cuts in branch-and-cut algorithms for the traveling salesman problem.     

Lexicographic compositions and deBruijn sequences

In this paper we give an algorithm to generate a new deBruijn sequence. The amount of storage required is only linear in n, the span of the sequence. We make use of the lexicographic compositions of a positive integer which we relate to binary necklaces of beads in two colors. We give a fast algorithm for generating the necklaces. Finally we relate the deBruijn sequence we generate to another sequence.     

A semi-iterative method for real spectrum singular linear systems with an arbitrary index

In this paper we develop a semi-iterative method for computing the Drazin-inverse solution of a singular linear system Ax = b, where the spectrum of A is real, but its index (i.e., the size of its largest Jordan block corresponding to the eigenvalue zero) is arbitrary. The method employs a set of polynomials that satisfy certain normalization conditions and minimize some well-defined least-squares norm. We develop an efficient recursive algorithm for implementing this method that has a fixed length independent of the index of A. Following that, we give a complete theory of convergence, in which we provide rates of convergence as well. We conclude with a numerical application to determine eigenprojections onto generalized eigenspaces. Our treatment extends the work of Hanke and Hochbruck (1993) that considers the case in which the index of A is 1.     

Computation of the Highest Coefficients of Weighted Ehrhart Quasi-polynomials of Rational Polyhedra

This article concerns the computational problem of counting the lattice points inside convex polytopes, when each point must be counted with a weight associated to it. We describe an efficient algorithm for computing the highest degree coefficients of the weighted Ehrhart quasi-polynomial for a rational simple polytope in varying dimension, when the weights of the lattice points are given by a polynomial function h. Our technique is based on a refinement of an algorithm of A.?Barvinok in the unweighted case (i.e., h≡1). In contrast to Barvinok’s method, our method is local, obtains an approximation on the level of generating functions, handles the general weighted case, and provides the coefficients in closed form as step polynomials of the dilation. To demonstrate the practicality of our approach, we report on computational experiments which show that even our simple implementation can compete with state-of-the-art software.     

Two-sided taboo limits for Markov processes and associated perfect simulation

In this paper, we study the two-sided taboo limit processes that arise when a Markov chain or process is conditioned on staying in some set A for a long period of time. The taboo limit is time-homogeneous after time 0 and time-inhomogeneous before time 0. The time-reversed limit has this same qualitative structure. The precise transition structure at the taboo limit is identified in the context of discrete- and continuous-time Markov chains, as well as diffusions. In addition, we present a perfect simulation algorithm for generating exact samples from the quasi-stationary distribution of a finite-state Markov chain.     

Voting power in the European Union enlargement

The Shapley–Shubik power index in a voting situation depends on the number of orderings in which each player is pivotal. The Banzhaf power index depends on the number of ways in which each voter can effect a swing. If there are n players in a voting situation, then the function which measures the worst case running time for computing these indices is in O(n2ⁿ). We present a combinatorial method based in generating functions to compute these power indices efficiently in weighted double or triple majority games and we study the time complexity of the algorithms. Moreover, we calculate these power indices for the countries in the Council of Ministers of the European Union under the new decision rules prescribed by the Treaty of Nice.     

Fast perfect sampling from linear extensions

In this paper, we study the problem of sampling (exactly) uniformly from the set of linear extensions of an arbitrary partial order. Previous Markov chain techniques have yielded algorithms that generate approximately uniform samples. Here, we create a bounding chain for one such Markov chain, and by using a non-Markovian coupling together with a modified form of coupling from the past, we build an algorithm for perfectly generating samples. The expected running time of the procedure is O(n³lnn), making the technique as fast as the mixing time of the Karzanov/Khachiyan chain upon which it is based.     

An efficient algorithm for the multivariable Adomian polynomials

In this article the sum of the series of multivariable Adomian polynomials is demonstrated to be identical to a rearrangement of the multivariable Taylor expansion of an analytic function of the decomposition series of solutions u₁, u₂, … , u_m about the initial solution components u_1,0, u_2,0, … , u_m,0; of course the multivariable Adomian polynomials were developed and are eminently practical for the solution of coupled nonlinear differential equations. The index matrices and their simplified forms of the multivariable Adomian polynomials are introduced. We obtain the recurrence relations for the simplified index matrices, which provide a convenient algorithm for rapid generation of the multivariable Adomian polynomials. Another alternative algorithm for term recurrence is established. In these algorithms recurrence processes do not require complicated operations such as parametrization, expanding and regrouping, derivatives, etc. as practiced in prior art. The MATHEMATICA program generating the Adomian polynomials based on the algorithm in this article is designed.     

Pattern avoidance in binary trees

This paper considers the enumeration of trees avoiding a contiguous pattern. We provide an algorithm for computing the generating function that counts n-leaf binary trees avoiding a given binary tree pattern t. Equipped with this counting mechanism, we study the analogue of Wilf equivalence in which two tree patterns are equivalent if the respective n-leaf trees that avoid them are equinumerous. We investigate the equivalence classes combinatorially. Toward establishing bijective proofs of tree pattern equivalence, we develop a general method of restructuring trees that conjecturally succeeds to produce an explicit bijection for each pair of equivalent tree patterns.     

Generating pairing-friendly parameters for the CM construction of genus 2 curves over prime fields

We present two contributions in this paper. First, we give a quantitative analysis of the scarcity of pairing-friendly genus 2 curves. This result is an improvement relative to prior work which estimated the density of pairing-friendly genus 2 curves heuristically. Second, we present a method for generating pairing-friendly parameters for which ${\rho\approx 8}$ , where ρ is a measure of efficiency in pairing-based cryptography. This method works by solving a system of equations given in terms of coefficients of the Frobenius element. The algorithm is easy to understand and implement.     

The generalized order-k Fibonacci–Pell sequence by matrix methods

In this paper, we consider the usual and generalized order-k Fibonacci and Pell recurrences, then we define a new recurrence, which we call generalized order-k F–P sequence. Also we present a systematic investigation of the generalized order-k F–P sequence. We give the generalized Binet formula, some identities and an explicit formula for sums of the generalized order-k F–P sequence by matrix methods. Further, we give the generating function and combinatorial representations of these numbers. Also we present an algorithm for computing the sums of the generalized order-k Pell numbers, as well as the Pell numbers themselves.     

Some generating functions of Jacobi polynomials

In this paper, Weisner’s group-theoretic method of obtaining generating functions is utilized in the study of Jacobi polynomialsP> _n ^(a,ß)(x) by giving suitable interpretations to the index (n) and the parameter (β) to find out the elements for constructing a six-dimensional Lie algebra.     

Representations of orthogonal polynomials

Zeilberger's algorithm provides a method to compute recurrence and differential equations from given hypergeometric series representations, and an adaption of Almquist and Zeilberger computers recurrence and differential equations for hyperexponential integrals. Further versions of this algorithm allow the computation of recurrence and differential equations from Rodrigues type formulas and from generating functions. In particular, these algorithms can be used to compute the differential/difference and recurrence equations for the classical continuous and discrete orthogonal polynomials from their hypergeometric representations, and from their Rodrigues representations and generating functions.In recent work, we used an explicit formula for the recurrence equation of families of classical continuous and discrete orthogonal polynomials, in terms of the coefficients of their differential/difference equations, to give an algorithm to identify the polynomial system from a given recurrence equation.In this article we extend these results by presenting a collection of algorithms with which any of the conversions between the differential/difference equation, the hypergeometric representation, and the recurrence equation is possible.The main technique is again to use explicit formulas for structural identities of the given polynomial systems.     

An alternative to the Ritz pairs with the EN subspace method

In this note we define EN subspaces by using the Eirola-Nevanlinna algorithm for solving a linear system. We compare this construction with the Arnoldi method for generating Krylov subspaces and computing eigenvalue approximations. Further, we compute Ritz pairs by restricting the updated preconditionerH _k of the EN algorithm to the generated EN subspaces.