An Arbitrary Starting Variable Dimension Algorithm for Computing an Integer Point of a Simplex

An arbitrary starting variable dimension algorithm is proposed to compute an integer point of an n-dimensional simplex. It is based on an integer labeling rule and a triangulation of Rⁿ. The algorithm consists of two interchanging phases. The first phase of the algorithm is a variable dimension algorithm, which generates simplices of varying dimensions,and the second phase of the algorithm forms a full-dimensional pivoting procedure, which generates n-dimensional simplices. The algorithm varies from one phase to the other. When the matrix defining the simplex is in the so-called canonical form, starting at an arbitrary integer point, the algorithm within a finite number of iterations either yields an integer point of the simplex or proves that no such point exists.     

Computing an Integer Point of a Class of Convex Sets

A simplicial algorithm is proposed for computing an integer point of a convex set ^CRn satisfying

TheD 2-triangulation for simplicial homotopy algorithms for computing solutions of nonlinear equations

A triangulation of arbitrary refinement of grid sizes of (0, 1] × ⁿ is proposed for simplicial homotopy algorithms for computing solutions of nonlinear equations. On each level the new triangulation, called theD ₂-triangulation, subdivides ⁿ into simplices according to theD ₁-triangulation. We prove that theD ₂-triangulation is superior to theK ₂-triangulation andJ ₂-triangulation in the number of simplices. Numerical tests show that the simplicial homotopy algorithm based on theD ₂-triangulation indeed is much more efficient.     

A new simplicial variable dimension algorithm to find equilibria on the product space of unit simplices

A new simplicial variable dimension restart algorithm is introduced to solve the nonlinear complementarity problem on the product spaceS of unit simplices. The triangulation which underlies the algorithm differs from the triangulations ofS used thus far. Moreover, the number of rays along which the algorithm can leave the arbitrarily chosen starting point is much larger. More precisely, there is a ray leading from the starting point to each vertex ofS. In caseS is the product ofn one-dimensional unit simplices the alogrithm is similar to the octahedral algorithm onR ⁿ having 2 ⁿ rays. Also, the accuracy of an approximate solution in the terminal simplex of the algorithm is in general better than for the other algorithms onS. Computational results will show that the number of iterations for the new algorithm is much less. The examples concern the computation of equilibria in noncooperative games, exchange economies and trade models. This author is financially supported by the Netherlands Organisation for the Advancement of Pure Research (ZWO), Grant 46-98. This research is part of the VF-program “Equilibrium and Disequilibrium in Demand and Supply” which has been approved by the Netherlands ministry of education and sciences.     

A simple and relatively efficient triangulation of then-cube

The only previously published triangulation of then-cube usingo(n!) simplices, due to Sallee, usesO(n ⁻² n!) simplices. We point out a very simple method of achievingO(ρ ⁿ n!) simplices, where ρ<1 is a constant. This research was supported in part by N.S.F. Grant No. DMS-8717795.     

Triangulating point sets in space

A setP ofn points inR ^d is called simplicial if it has dimensiond and contains exactlyd + 1 extreme points. We show that whenP containsn interior points, there is always one point, called a splitter, that partitionsP intod + 1 simplices, none of which contain more thandn/(d + 1) points. A splitter can be found inO(d ⁴ +nd ²) time. Using this result, we give anO(nd ⁴ log_1+1/d n) algorithm for triangulating simplicial point sets that are in general position. InR ³ we give anO(n logn +k) algorithm for triangulating arbitrary point sets, wherek is the number of simplices produced. We exhibit sets of 2n + 1 points inR ³ for which the number of simplices produced may vary between (n – 1)² + 1 and 2n – 2. We also exhibit point sets for which every triangulation contains a quadratic number of simplices.Research supported by the Natural Science and Engineering Research Council grant A3013 and the F.C.A.R. grant EQ1678.     

Weighted projective spaces and reflexive simplices

 We derive a classification algorithm for reflexive simplices in arbitrary fixed dimension. It is based on the assignment of a weight Q ? ℕ ⁿ⁺¹ to an integral n-simplex, the construction, up to an isomorphism, of all simplices with given weight Q, and the characterization in terms of the weight as to when a simplex with reduced weight is reflexive. This also yields a convex-geometric reproof of the characterization in terms of weights for weighted projective spaces to have at most Gorenstein singularities. Received: 30 March 1999 / Revised version: 18 October 2001     

Bounds on the convex label number of trees

A convex labelling of a tree is an assignment of distinct non-negative integer labels to vertices such that wheneverx, y andz are the labels of vertices on a path of length 2 theny≦(x+z)/2. In addition if the tree is rooted, a convex labelling must assign 0 to the root. The convex label number of a treeT is the smallest integerm such thatT has a convex labelling with no label greater thanm. We prove that every rooted tree (and hence every tree) withn vertices has convex label number less than 4n. We also exhibitn-vertex trees with convex label number 4n/3+o(n), andn-vertex rooted trees with convex label number 2n +o(n). The research by M. B. and A. W. was partly supported by NSF grant MCS—8311422.     

Some Inequalities for Two Simplices

In this paper, we establish some inequalities for two n-dimensional simplices in the n-dimensional Euclidean space E ⁿ .     

A polynomial dual simplex algorithm for the generalized circulation problem

This paper presents a polynomial-time dual simplex algorithm for the generalized circulation problem. An efficient implementation of this algorithm is given that has a worst-case running time of O(m ²(m+nlogn)logB), where n is the number of nodes, m is the number of arcs and B is the largest integer used to represent the rational gain factors and integral capacities in the network. This running time is as fast as the running time of any combinatorial algorithm that has been proposed thus far for solving the generalized circulation problem. Received: June 1998 / Accepted: June 27, 2001?Published online September 17, 2001     

Small Grid Embeddings of 3-Polytopes

We introduce an algorithm that embeds a given 3-connected planar graph as a convex 3-polytope with integer coordinates. The size of the coordinates is bounded by O(2^7.55n )=O(188 ⁿ ). If the graph contains a triangle we can bound the integer coordinates by O(2^4.82n ). If the graph contains a quadrilateral we can bound the integer coordinates by O(2^5.46n ). The crucial part of the algorithm is to find a convex plane embedding whose edges can be weighted such that the sum of the weighted edges, seen as vectors, cancel at every point. It is well known that this can be guaranteed for the interior vertices by applying a technique of Tutte. We show how to extend Tutte’s ideas to construct a plane embedding where the weighted vector sums cancel also on the vertices of the boundary face.     

On the matricial version of Fermat–Euler congruences

The congruences modulo the primary numbers n=p ^a are studied for the traces of the matrices A ⁿ and A ^n-φ(n), where A is an integer matrix and φ(n) is the number of residues modulo n, relatively prime to n. We present an algorithm to decide whether these congruences hold for all the integer matrices A, when the prime number p is fixed. The algorithm is explicitly applied for many values of p, and the congruences are thus proved, for instance, for all the primes p ≤ 7 (being untrue for the non-primary modulus n=6). We prove many auxiliary congruences and formulate many conjectures and problems, which can be used independently. Partially supported by RFBR, grant 05-01-00104. An erratum to this article is available at .     

Cutting hyperplanes for divide-and-conquer

Givenn hyperplanes inE ^d, a (1/r)-cutting is a collection of simplices with disjoint interiors, which together coverE ^d and such that the interior of each simplex intersects at mostn/r hyperplanes. We present a deterministic algorithm for computing a (1/r)-cutting ofO(r ^d) size inO(nr ^d–1) time. If we require the incidences between the hyperplanes and the simplices of the cutting to be provided, then the algorithm is optimal. Our method is based on a hierarchical construction of cuttings, which also provides a simple optimal data structure for locating a point in an arrangement of hyperplanes. We mention several other applications of our result, e.g., counting segment intersections, Hopcroft's line/point incidence problem, linear programming in fixed dimension.This research was supported in part by the National Science Foundation under Grant CCR-9002352.     

Solving discrete systems of nonlinear equations

We study the existence problem of a zero point of a function defined on a finite set of elements of the integer lattice Zⁿ of the n-dimensional Euclidean space Rⁿ. It is assumed that the set is integrally convex, which implies that the convex hull of the set can be subdivided in simplices such that every vertex is an element of Zⁿ and each simplex of the triangulation lies in an n-dimensional cube of size one. With respect to this triangulation we assume that the function satisfies some property that replaces continuity. Under this property and some boundary condition the function has a zero point. To prove this we use a simplicial algorithm that terminates with a zero point within a finite number of iterations. The standard technique of applying a fixed point theorem to a piecewise linear approximation cannot be applied, because the ‘continuity property’ is too weak to assure that a zero point of the piecewise linear approximation induces a zero point of the function itself. We apply the main existence result to prove the existence of a pure Cournot-Nash equilibrium in a Cournot oligopoly model. We further obtain a discrete analogue of the well-known Borsuk-Ulam theorem and a theorem for the existence of a solution for the discrete nonlinear complementarity problem.     

A class of simplicial restart fixed point algorithms without an extra dimension

In an earlier paper we introduced an algorithm for approximating a fixed point of a mapping on the product space of unit simplices. Ideas of that paper are used to construct a class of triangulations ofR ⁿ. More precisely, for somek, 1 k n, and positive integersm ₁ , m_k with sumn, a triangulation ofR ⁿ is obtained by triangulating the cells which are formed by taking the product of given triangulations ofR ^mj, j = 1, ,k. The triangulation of each cell will be defined in relation to an arbitrarily chosen pointv inR ⁿ, being the starting point of the algorithm. Fork = n we obtain theK triangulation originally due to Todd. Each element of the class can be used to find a simplex which approximates a fixed point of a mapping onR ⁿ by generating a unique path of adjacent simplices of variable dimension starting with the pointv. We also give convergence conditions. It is indicated how in casek = n a connected set of fixed points can be generated. Moreover, we give some computational experience.     

Comparative studies on dynamic programming and integer programming approaches for concave cost production/inventory control problems

This paper is concerned with classical concave cost multi-echelon production/inventory control problems studied by W. Zangwill and others. It is well known that the problem with m production steps and n time periods can be solved by a dynamic programming algorithm in O(n ⁴ m) steps, which is considered as the fastest algorithm for solving this class of problems. In this paper, we will show that an alternative 0–1 integer programming approach can solve the same problem much faster particularly when n is large and the number of 0–1 integer variables is relatively few. This class of problems include, among others problem with set-up cost function and piecewise linear cost function with fewer linear pieces. The new approach can solve problems with mixed concave/convex cost functions, which cannot be solved by dynamic programming algorithms.     

A modular integer GCD algorithm

This paper describes the first algorithm to compute the greatest common divisor (GCD) of two n-bit integers using a modular representation for intermediate values U, V and also for the result. It is based on a reduction step, similar to one used in the accelerated algorithm [T. Jebelean, A generalization of the binary GCD algorithm, in: ISSAC '93: International Symposium on Symbolic and Algebraic Computation, Kiev, Ukraine, 1993, pp. 111–116; K. Weber, The accelerated integer GCD algorithm, ACM Trans. Math. Softw. 21 (1995) 111–122] when U and V are close to the same size, that replaces U by (U−bV)/p, where p is one of the prime moduli and b is the unique integer in the interval (−p/2,p/2) such that . When the algorithm is executed on a bit common CRCW PRAM with O(nlognlogloglogn) processors, it takes O(n) time in the worst case. A heuristic model of the average case yields O(n/logn) time on the same number of processors.     

Improved algorithms for the multicut and multiflow problems in rooted trees

Costa et al. (Oper. Res. Lett. 31:21–27, 2003) presented a quadratic O(min (Kn,n ²)) greedy algorithm to solve the integer multicut and multiflow problems in a rooted tree. (n is the number of nodes of the tree, and K is the number of commodities). Their algorithm is a special case of the greedy type algorithm of Kolen (Location problems on trees and in the rectilinear plane. Ph.D. dissertation, 1982) to solve weighted covering and packing problems defined by general totally balanced (greedy) matrices. In this communication we improve the complexity bound in Costa et al. (Oper. Res. Lett. 31:21–27, 2003) and show that in the case of the integer multicut and multiflow problems in a rooted tree the greedy algorithm of Kolen can be implemented in subquadratic O(K+n+min (K,n)log n) time. The improvement is obtained by identifying additional properties of this model which lead to a subquadratic transformation to greedy form and using more sophisticated data structures.      

Fast algorithms for determining the linear complexities of sequences over GF(pm) with the period 3n

In this paper, for the the primes p such that 3 is a divisor of p − 1, we prove a result which reduces the computation of the linear complexity of a sequence over GF(p ^m) (any positive integer m) with the period 3n (n and p ^m − 1 are coprime) to the computation of the linear complexities of three sequences with the period n. Combined with some known algorithms such as generalized Games-Chan algorithm, Berlekamp-Massey algorithm and Xiao-Wei-Lam-Imamura algorithm, we can determine the linear complexity of any sequence over GF(p ^m) with the period 3n (n and p ^m − 1 are coprime) more efficiently.