Efficient Algorithms for Variants of Weighted Matching and Assignment Problems

Obtaining a matching in a graph satisfying a certain objective is an important class of graph problems. Matching algorithms have received attention for several decades. However, while there are efficient algorithms to obtain a maximum weight matching, not much is known about the maximum weight maximum cardinality, and maximum cardinality maximum weight matching problems for general graphs. Our contribution in this work is to show that for bounded weight input graphs one can obtain an algorithm for both maximum weight maximum cardinality (for real weights), and maximum cardinality maximum weight matching (for integer weights) by modifying the input and running the existing maximum weight matching algorithm. Also, given the current state of the art in maximum weight matching algorithms, we show that, for bounded weight input graphs, both maximum weight maximum cardinality, and maximum cardinality maximum weight matching have algorithms of similar complexities to that of maximum weight matching. Subsequently, we also obtain approximation algorithms for maximum weight maximum cardinality, and maximum cardinality maximum weight matching.      

The Computation of Invariant Fields and a Constructive Version of a Theorem by Rosenlicht

Let G be an algebraic group acting on an irreducible variety X. We present an algorithm for computing the invariant field k(X)^G. Moreover, we give a constructive version of a theorem of Rosenlicht, which says that almost all orbits can be separated by rational invariants. More precisely, we give an algorithm for computing a nonempty open subset of X with a geometric quotient.     

On the complexity of the resolvent representation of some prime differential ideals

We prove upper bounds on the order and degree of the polynomials involved in a resolvent representation of the prime differential ideal associated with a polynomial differential system for a particular class of ordinary first order algebraic-differential equations arising in control theory. We also exhibit a probabilistic algorithm which computes this resolvent representation within time polynomial in the natural syntactic parameters and the degree of a certain algebraic variety related to the input system. In addition, we give a probabilistic polynomial-time algorithm for the computation of the differential Hilbert function of the ideal.     

A complete characterization of irreducible cyclic orbit codes and their Plücker embedding

Constant dimension codes are subsets of the finite Grassmann variety. The study of these codes is a central topic in random linear network coding theory. Orbit codes represent a subclass of constant dimension codes. They are defined as orbits of a subgroup of the general linear group on the Grassmannian. This paper gives a complete characterization of orbit codes that are generated by an irreducible cyclic group, i.e. a group having one generator that has no non-trivial invariant subspace. We show how some of the basic properties of these codes, the cardinality and the minimum distance, can be derived using the isomorphism of the vector space and the extension field. Furthermore, we investigate the Plücker embedding of these codes and show how the orbit structure is preserved in the embedding.     

Toeplitz minimal flows which are not uniquely ergodic

Summary We study minimal symbolic dynamical systems which are orbit closures of Toeplitz sequences. We construct 0–1 subshifts of this type for which the set of ergodic invariant measures has any given finite cardinality, is countably infinite or has cardinality of the continuum.     

The Computational Complexity of the Chow Form

We present a bounded probability algorithm for the computation of the Chowforms of the equidimensional components of an algebraic variety. In particular, this gives an alternative procedure for the effective equidimensional decomposition of the variety, since each equidimensional component is characterized by its Chow form. The expected complexity of the algorithm is polynomial in the size and the geometric degree of the input equation system defining the variety. Hence it improves (or meets in some special cases) the complexity of all previous algorithms for computing Chow forms. In addition to this, we clarify the probability and uniformity aspects, which constitutes a further contribution of the paper. The algorithm is based on elimination theory techniques, in line with the geometric resolution algorithm due to M. Giusti, J. Heintz, L. M. Pardo, and their collaborators. In fact, ours can be considered as an extension of their algorithm for zero-dimensional systems to the case of positive-dimensional varieties. The key element for dealing with positive-dimensional varieties is a new Poisson-type product formula. This formula allows us to compute the Chow form of an equidimensional variety from a suitable zero-dimensional fiber. As an application, we obtain an algorithm to compute a subclass of sparse resultants, whose complexity is polynomial in the dimension and the volume of the input set of exponents. As another application, we derive an algorithm for the computation of the (unique) solution of a generic overdetermined polynomial equation system.     

Deformation Techniques for Sparse Systems

We exhibit a probabilistic symbolic algorithm for solving zero-dimensional sparse systems. Our algorithm combines a symbolic homotopy procedure, based on a flat deformation of a certain morphism of affine varieties, with the polyhedral deformation of Huber and Sturmfels. The complexity of our algorithm is cubic in the size of the combinatorial structure of the input system. This size is mainly represented by the cardinality and mixed volume of Newton polytopes of the input polynomials and an arithmetic analogue of the mixed volume associated to the deformations under consideration. Research was partially supported by the following grants: UBACyT X112 (2004–2007), UBACyT X847 (2006–2009), PIP CONICET 2461, PIP CONICET 5852/05, ANPCyT PICT 2005 17-33018, UNGS 30/3005, MTM2004-01167 (2004–2007), MTM2007-62799 and CIC 2007–2008.     

A refinement of multivariate value set bounds

Over finite fields, if the image of a polynomial map is not the entire field, then its cardinality can be bounded above by a significantly smaller value. Earlier results bound the cardinality of the value set using the degree of the polynomial, but more recent results make use of the powers of all monomials.In this paper, we explore the geometric properties of the Newton polytope and show how they allow for tighter upper bounds on the cardinality of the multivariate value set. We then explore a method which allows for even stronger upper bounds, regardless of whether one uses the multivariate degree or the Newton polytope to bound the value set. Effectively, this provides improvement of a degree matrix-based result given by Zan and Cao, making our new bound the strongest upper bound thus far.     

非线性系统双模鲁棒预测控制: 不变集切换方法

提出了一种基于不变集切换的非线性系统鲁棒预测控制算法.采用分段蕴含方法将非线性系统动态用一组线性变参数(LPV)系统动态包裹;计算出非线性系统的平衡面,对于每个LPV蕴含模型,针对相应的平衡点构造多面体不变集,得到覆盖非线性系统平衡面的一组相互重叠的不变集;在线根据系统当前状态所处的不变集和LPV区间切换控制律,最终保证闭环系统的稳定性.与传统的非线性预测控制相比,这种方法在构造不变集和确定控制律的计算都是离线进行,而在线只需根据当前状态切换控制律即可,从而避免了求解复杂的非凸非线性规划,在很大程度上降低了在线计算量.     

Families of locally separated Hamilton paths

We improve by an exponential factor the lower bound of Körner and Muzi for the cardinality of the largest family of Hamilton paths in a complete graph of n vertices in which the union of any two paths has maximum degree 4. The improvement is through an explicit construction while the previous bound was obtained by a greedy algorithm. We solve a similar problem for permutations up to an exponential factor.     

Polynomial-Time Computation of the Degree of Algebraic Varieties in Zero Characteristic and Its Applications

Let k be a ground field of zero characteristic, and let V be an algebraic variety over k given as the locus of a family of polynomials of degree less than d in n variables. In the paper, we construct algorithms that have working time that is polynomial in the size of the input and d ⁿ and compute the following: the degree of the variety V, the dimension of V in a neighborhood of a given point, the multiplicity of a given point of V, and a representative system of smooth points with their tangent spaces on each component of V. Also, we construct an algorithm for deciding whether a given morphism between two given algebraic varieties V and V' is dominant. Bibliography: 17 titles.     

Rough isometry and energy finite solutions of elliptic equations on Riemannian manifolds

We prove that if the s-harmonic boundary of a complete Riemannian manifold consists of finitely many points, then the set of bounded energy finite solutions for certain nonlinear elliptic operators on the manifold is one to one corresponding to , where l is the cardinality of thes-harmonic boundary. We also prove that the finiteness of cardinality of s-harmonic boundary is a rough isometric invariant, moreover, in this case, the cardinality is preserved under rough isometries between complete Riemannian manifolds. This result generalizes those of Yau, of Donnelly, of Grigor'yan, of Li and Tam, of Kim and the present author, of Holopainen, and of the present author, but with different techniques which are demanded by the peculiarity of nonlinearity. Received October 13, 1999 / Revised November 23, 1999 / Published online July 20, 2000     

Polar Varieties,Real Equation Solving,and Data Structures: The Hypersurface Case

In this paper we apply for the first time a new method for multivariate equation solving which was developed for complex root determination to therealcase. Our main result concerns the problem of finding at least one representative point for each connected component of a real compact and smooth hypersurface. The basic algorithm yields a new method for symbolically solving zero-dimensional polynomial equation systems over the complex numbers. One feature of central importance of this algorithm is the use of a problem-adapted data type represented by the data structures arithmetic network and straight-line program (arithmetic circuit). The algorithm finds the complex solutions of any affine zero-dimensional equation system in nonuniform sequential time that ispolynomialin the length of the input (given in straight-line program representation) and an adequately definedgeometric degree of the equation system.Replacing the notion of geometric degree of the given polynomial equation system by a suitably definedreal (or complex) degreeof certain polar varieties associated to the input equation of the real hypersurface under consideration, we are able to find for each connected component of the hypersurface a representative point (this point will be given in a suitable encoding). The input equation is supposed to be given by a straight-line program and the (sequential time) complexity of the algorithm is polynomial in the input length and the degree of the polar varieties mentioned above.     

KAM theorem of symplectic algorithms for Hamiltonian systems

Summary. In this paper we prove that an analog of the celebrated KAM theorem holds for symplectic algorithms, which Channel and Scovel (1990), Feng Kang (1991) and Sanz-Serna and Calvo (1994) suggested a few years ago. The main results consist of the existence of invariant tori, with a smooth foliation structure, of a symplectic numerical algorithm when it applies to a generic integrable Hamiltonian system if the system is analytic and the time-step size of the algorithm is s ufficiently small. This existence result also implies that the algorithm, when it is applied to a generic integrable system, possesses n independent smooth invariant functions which are in involution and well-defined on the set filled by the invariant tori in the sense of Whitney. The invariant tori are just the level sets of these functions. Some quantitative results about the numerical invariant tori of the algorithm approximating the exact ones of the system are also given. Received December 27, 1997 / Revised version received July 15, 1998 / Published online: July 7, 1999     

Separable polynomials over finite dimensional algebras

In [5] it was shown that for a polynomial P of precise degree n with coefficients in an arbitrary m-ary algebra of dimension d as a vector space over an algebraically closed fields, the zeros of P together with the homogeneous zeros of the dominant part of P form a set of cardinality n^d or the cardinality of the base field. We investigate polynomials with coefficients in a d dimensional algebra A without assuming the base field k to be algebraically closed. Separable polynomials are defined to be those which have exactly n^d distinct zeros in [Ktilde] ?_k A [Ktilde] where [Ktilde] denotes an algebraic closure of k. The main result states that given a separable polynomial of degree n, the field extension L of minimal degree over k for which L ?_k A contains all nd zeros is finite Galois over k. It is shown that there is a non empty Zariski open subset in the affine space of all d-dimensional k algebras whose elements A have the following property: In the affine space of polynomials of precise degree n with coefficients in A there is a non empty Zariski open subset consisting of separable polynomials; in other polynomials with coefficients in a finite dimensional algebra are “generically” separable.     

Semi-planar Steiner loops of cardinality 2n

It is well known that there is a planar sloop of cardinality n for each n≡2 or 4 (mod 6) (Math. Z. 111 (1969) 289–300). A semi-planar sloop is a simple sloop in which each triangle either generates the whole sloop or the 8-element sloop. In fact, Quackenbush (Canad. J. Math. 28 (1976) 1187–1198) has stated that there should be such semi-planar sloops. In this paper, we construct a semi-planar sloop of cardinality 2n for each n≡2 or 4 (mod 6). Consequently, we may say that there is a semi-planar sloop that is not planar of cardinality m for each m>16 and m≡4 or 8 (mod 12). Moreover, Quackenbush (Canad. J. Math. 28 (1976) 1187–1198) has proved that each finite simple planar sloop generates a variety, which covers the smallest non-trivial subvariety (the variety of all Boolean sloops) of the lattice of the subvarieties of all sloops. Similarly, it is easy to show that each finite semi-planar sloop generates another variety, which also covers the variety of all Boolean sloops. Furthermore, for any finite simple sloop of cardinality n, the author (Beiträge Algebra Geom. 43 (2) (2002) 325–331) has constructed a subdirectly irreducible sloop of cardinality 2n and containing as the only proper normal subsloop. Accordingly, if is a semi-planar sloop, then the variety generated by properly contains the subvariety .     

Invariant submanifolds for systems of vector fields of constant rank

Given a system of vector fields on a smooth manifold that spans a plane field of constant rank, we present a systematic method and an algorithm to find submanifolds that are invariant under the flows of the vector fields. We present examples of partition into invariant submanifolds, which further gives partition into orbits. We use the method of generalized Frobenius theorem by means of exterior differential systems.     

On the asymptotic magnitude of subsets of Euclidean space

Magnitude is a canonical invariant of finite metric spaces which has its origins in category theory; it is analogous to cardinality of finite sets. Here, by approximating certain compact subsets of Euclidean space with finite subsets, the magnitudes of line segments, circles and Cantor sets are defined and calculated. It is observed that asymptotically these satisfy the inclusion-exclusion principle, relating them to intrinsic volumes of polyconvex sets.     

Distributive lattices of numberings

We study into a semilattice of numberings generated by a given fixed numbering via operations of completion and taking least upper bounds. It is proved that, except for the trivial cases, this semilattice is an infinite distributive lattice every principal ideal in which is finite. The least upper and the greatest lower bounds in the semilattice are invariant under extensions in the semilattice of all numberings. Isomorphism types for the semilattices in question are in one-to-one correspondence with pairs of cardinals the first component of which is equal to the cardinality of a set of non-special elements, and the second — to the cardinality of a set of special elements, of the initial numbering. Supported by INTAS grant No. 00-429. __________ Translated from Algebra i Logika, Vol. 46, No. 1, pp. 83–102, January–February, 2007.     

The euclidean distance degree of orthogonally invariant matrix varieties

The Euclidean distance degree of a real variety is an important invariant arising in distance minimization problems. We show that the Euclidean distance degree of an orthogonally invariant matrix variety equals the Euclidean distance degree of its restriction to diagonal matrices. We illustrate how this result can greatly simplify calculations in concrete circumstances.