The purpose of our paper is to give a purely combinatorial and algorithmic proof of the Hex theorem with multiple labels. Moreover we extend this result for a new class of complexes, called n-essential. We also presen...
详细信息
The purpose of our paper is to give a purely combinatorial and algorithmic proof of the Hex theorem with multiple labels. Moreover we extend this result for a new class of complexes, called n-essential. We also present a topological version of the Hex theorem and explain its relation to the fixed point property, the Poincare-Miranda theorem and the covering (Lebesgue) dimension. (C) 2023 Elsevier B.V. All rights reserved.
Tucker's well-known combinatorial lemma states that, for any given symmetric triangulation of the n-dimensional unit cube and for any integer labeling that assigns to each vertex of the triangulation a label from ...
详细信息
Tucker's well-known combinatorial lemma states that, for any given symmetric triangulation of the n-dimensional unit cube and for any integer labeling that assigns to each vertex of the triangulation a label from the set {+/- 1,+/- 2,aEuro broken vertical bar,+/- n} with the property that antipodal vertices on the boundary of the cube are assigned opposite labels, the triangulation admits a 1-dimensional simplex whose two vertices have opposite labels. In this paper, we are concerned with an arbitrary finite set D of integral vectors in the n-dimensional Euclidean space and an integer labeling that assigns to each element of D a label from the set {+/- 1,+/- 2,aEuro broken vertical bar,+/- n}. Using a constructive approach, we prove two combinatorial theorems of Tucker type. The theorems state that, under some mild conditions, there exists two integral vectors in D having opposite labels and being cell-connected in the sense that both belong to the set {0,1} (n) +q for some integral vector q. These theorems are used to show in a constructive way the existence of an integral solution to a system of nonlinear equations under certain natural conditions. An economic application is provided.
We present a tractable class of integer feasibility problems. This class of max-closed IP problems was studied in somewhat restricted form by Glover, Pnueli, Hochbaum and Chandrasekaran and has a logic counterpart kno...
详细信息
We present a tractable class of integer feasibility problems. This class of max-closed IP problems was studied in somewhat restricted form by Glover, Pnueli, Hochbaum and Chandrasekaran and has a logic counterpart known as the class of Horn formulas. First we modify the existing algorithms in order to avoid the related recognition problem. Then we show that in order to solve these max-closed IP problems, simplicial path following methods can be used. This is important because these methods are flexible with respect to starting conditions, which make them more suitable than the top-down truncation algorithms that have been suggested.
We prove the following conjecture of Atanassov (Studia Sci. Math. Hungar. 32 (1996), 71-74). Let T be a triangulation of a d-dimensional polytope P with n vertices v(1),v(2) ,. . . , v(n). Label the vertices of T by 1...
详细信息
We prove the following conjecture of Atanassov (Studia Sci. Math. Hungar. 32 (1996), 71-74). Let T be a triangulation of a d-dimensional polytope P with n vertices v(1),v(2) ,. . . , v(n). Label the vertices of T by 1,2, . . . , n in such a way that a vertex of T belonging to the interior of a face F of P can only be labelled by j if v(j) is on F. Then there are at least n - d full dimensional simplices of T, each labelled with d + 1 different labels. We provide two proofs of this result: a non-constructive proof introducing the notion of a pebble set of a polytope, and a constructive proof using a path-following argument. Our non-constructive proof has interesting relations to minimal simplicial covers of convex polyhedra and their chamber complexes, as in Alekseyevskaya (Discrete Math. 157 (1996), 15-37) and Billera et al. (J. Combin. Theory Ser. B 57 (1993), 258-268). (C) 2002 Elsevier Scietice (USA).
The so called simplicial algorithms are put into use to compute the stationary probability distributions of stochastic matrices. This is a typical example of application of simplicial algorithms to compute the fixed p...
详细信息
The so called simplicial algorithms are put into use to compute the stationary probability distributions of stochastic matrices. This is a typical example of application of simplicial algorithms to compute the fixed points of a continuous map (Brouwer's theorem). We further demonstrate the variable grid refinement approach involved in the simplicial algorithms. The variable grid refinement scheme gives good accuracy and acceptable average computational complexity. (C) 1998 Elsevier Science Inc. All rights reserved.
This paper describes a new method for generating an H-infinity controller for a nonlinear system whose nonlinearities are modeled as describing functions. It is a three-step approach: modeling (using the describing fu...
详细信息
This paper describes a new method for generating an H-infinity controller for a nonlinear system whose nonlinearities are modeled as describing functions. It is a three-step approach: modeling (using the describing function approach), synthesis (using the H-infinity loop shifting technique), and robustness analysis (using the labeling technique of simplicial algorithms). The method is first demonstrated by designing an optimal H-infinity controller for a first-order linear unstable system driven by a Bang-Bang actuator. A more complex example is used next to demonstrate loop shifting and simplicial algorithms as applied to a suboptimal problem. This system was implemented on a digital computer and in analog circuit form to demonstrate the practicality of the method.
In this paper we prove the following result: Given any full-dimensional simple polytope P = {x is an element of R-n \a(lT)x less than or equal to b(i), i = 1,..., m}without redundant constraints and any vector c E R-n...
详细信息
In this paper we prove the following result: Given any full-dimensional simple polytope P = {x is an element of R-n \a(lT)x less than or equal to b(i), i = 1,..., m}without redundant constraints and any vector c E R-n, there exists a unique vertex x* of P such that the matrix [GRAPHICS] ( ) exists and is lexicographic positive, where x* is the solution of the n linear equations a(itT)x = b(it), t = 1 ,..., n. This theorem generalizes a result on the n-dimensional cube and can be used to resolve the degeneracy problem for simplicial fixed point algorithms. We also discuss several applications for this result. (C) 1998 Published by Elsevier Science Inc. All rights reserved.
The equilibria of a model of an exchange economy with price rigidities are called constrained equilibria. A simplicial algorithm on the unit cube is proposed to compute an approximation of a continuum of zero points o...
详细信息
The equilibria of a model of an exchange economy with price rigidities are called constrained equilibria. A simplicial algorithm on the unit cube is proposed to compute an approximation of a continuum of zero points of the excess demand correspondence of such an economy. This continuum of zero points corresponds to a continuum of constrained equilibria of the economy, linking the two so-called trivial equilibria. Moreover, the convergence properties of the algorithm and the accuracy of the approximate constrained equilibria obtained by the algorithm are discussed. Finally, an example is given as an illustration.
This paper presents a new method for designing H ∞ optimal or suboptimal controllers for nonlinear systems. A stability analysis is conducted using simplicial algorithms. In this example gains are used as the H ∞ we...
详细信息
This paper presents a new method for designing H ∞ optimal or suboptimal controllers for nonlinear systems. A stability analysis is conducted using simplicial algorithms. In this example gains are used as the H ∞ weighting functions. The system is a unstable first order plant, driven by a Bang-Bang actuator. A describing function model of the actuator is used in this analysis.
In this paper, a new variable-dimension simplicial algorithm is developed to compute economic equilibria on the Cartesian product of the n-dimensional unit price simplex S-n and the m-dimensional production activity s...
详细信息
In this paper, a new variable-dimension simplicial algorithm is developed to compute economic equilibria on the Cartesian product of the n-dimensional unit price simplex S-n and the m-dimensional production activity space R(+)(m). The algorithm differs from other algorithms in the number of directions in which the algorithm may leave the starting point. More precisely, the algorithm has 2(n+m+1)-2 rays to leave the starting point, whereas the other algorithms have at most 2(m)(n+1) rays. The path of points generated by the algorithm can be interpreted as a globally and universally convergent price and production adjustment process. The process as well as the convergence condition are much more natural and economically meaningful than the adjustment processes obtained by other simplicial algorithms. Furthermore, we apply the algorithm to economies with linear production, economies with constant returns to scale, and economies with increasing returns to scale.
暂无评论