Extended neighborhood: Definition and characterization

We consider neighborhood search defined on combinatorial optimization problems. Suppose that N is a Neighborhood for combinatorial optimization problem X. We say that N is LO-equivalent (locally optimal) to N if for any instance of X, the set of locally optimal solutions with respect to N and N are the same. The union of two LO-equivalent neighborhoods is itself LO-equivalent to the neighborhoods. The largest neighborhood that is LO-equivalent to N is called the extended neighborhood of N, and denoted as N^*. We analyze some basic properties of the extended neighborhood. We provide a geometric characterization of the extended neighborhood N^* when the instances have linear costs defined over a cone. For the TSP, we consider 2-opt^*, the extended neighborhood for the 2-opt (i.e., 2-exchange) neighborhood structure. We show that number of neighbors of each tour T in 2-opt^* is at least (n /2 -2)!. We show that finding the best tour in the 2-opt^* neighborhood is NP-hard. We also show that the extended neighborhood for the graph partition problem is the same as the original neighborhood, regardless of the neighborhood defined. This result extends to the quadratic assignment problem as well. This result on extended neighborhoods relies on a proof that the convex hull of solutions for the graph partition problem has a diameter of 1, that is, every two corner points of this polytope are adjacent.Acknowledgement We thank Ravi Ahuja, Andreas Schulz, and Ozlem Ergun for useful discussions. This research was supported through NSF contract DMI-9820998.     

Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs

We consider both facial reduction, FR, and symmetry reduction, SR, techniques for semidefinite programming, SDP. We show that the two together fit surprisingly well in an alternating direction method of multipliers, ADMM, approach. In fact, this approach allows for simply adding on nonnegativity constraints, and solving the doubly nonnegative, DNN , relaxation of many classes of hard combinatorial problems. We also show that the singularity degree remains the same after SR, and that the DNN relaxations considered here have singularity degree one, that is reduced to zero after FR. The combination of FR and SR leads to a significant improvement in both numerical stability and running time for both the ADMM and interior point approaches. We test our method on various DNN relaxations of hard combinatorial problems including quadratic assignment problems with sizes of more than \(n=500\). This translates to a semidefinite constraint of order 250, 000 and \(625\times 10^8\) nonnegative constrained variables, before applying the reduction techniques.

     

On the group extension of the transformation associated to non-archimedean continued fractions

Summary Let F_q be a finite field with q elements. We consider formal Laurent series of F_q -coefficients with their continued fraction expansions by F_q -polynomials. We prove some arithmetic properties for almost every formal Laurent series with respect to the Haar measure. We construct a group extension of the non-archimedean continued fraction transformation and show its ergodicity. Then we get some results as an application of the individual ergodic theorem. We also discuss the convergence rate for limit behaviors.     

Spectral properties of k p schrödinger operators in one space dimension

In the physics of layered semiconductor devices the k · p method in combination with the envelope function approach is a well established tool for band structure calculations. We perform a rigorous mathematical analysis of spectral properties for the corresponding spatially one dimensional k · p Schrödinger operators;thereby encompassing a wide class of such operators. This class covers many of the k · p operators prevalent in solid state physics. It includes k · p Schrödinger operators with piecewise constant coefficients, a prerequisite for dealing with the important case of semiconductor hetero-structures. In particular, we address the question of persistence of a spectral gap over the wave vector range. We also introduce a regularization of the problem which gives rise to a consistent discretization of k · p operators with jumping coefficients and describe design patterns for the numerical treatment of k · p operators.     

Convergence of inexact inverse iteration with application to preconditioned iterative solves

In this paper we study inexact inverse iteration for solving the generalised eigenvalue problem A x=λM x. We show that inexact inverse iteration is a modified Newton method and hence obtain convergence rates for various versions of inexact inverse iteration for the calculation of an algebraically simple eigenvalue. In particular, if the inexact solves are carried out with a tolerance chosen proportional to the eigenvalue residual then quadratic convergence is achieved. We also show how modifying the right hand side in inverse iteration still provides a convergent method, but the rate of convergence will be quadratic only under certain conditions on the right hand side. We discuss the implications of this for the preconditioned iterative solution of the linear systems. Finally we introduce a new ILU preconditioner which is a simple modification to the usual preconditioner, but which has advantages both for the standard form of inverse iteration and for the version with a modified right hand side. Numerical examples are given to illustrate the theoretical results. AMS subject classification (2000)  65F15, 65F10     

Semi-self-decomposable distributions on Z<Subscript>+</Subscript>

We present a notion of semi-self-decomposability for distributions with support in Z ₊. We show that discrete semi-self-decomposable distributions are infinitely divisible and are characterized by the absolute monotonicity of a specific function. The class of discrete semi-self-decomposable distributions is shown to contain the discrete semistable distributions and the discrete geometric semistable distributions. We identify a proper subclass of semi-self-decomposable distributions that arise as weak limits of subsequences of binomially thinned sums of independent Z ₊-valued random variables. Multiple semi-self-decomposability on Z ₊ is also discussed.     

Symmetric Generalized Galois Logics

Symmetric generalized Galois logics (i.e., symmetric gGls) are distributive gGls that include weak distributivity laws between some operations such as fusion and fission. Motivations for considering distribution between such operations include the provability of cut for binary consequence relations, abstract algebraic considerations and modeling linguistic phenomena in categorial grammars. We represent symmetric gGls by models on topological relational structures. On the other hand, topological relational structures are realized by structures of symmetric gGls. We generalize the weak distributivity laws between fusion and fission to interactions of certain monotone operations within distributive super gGls. We are able to prove appropriate generalizations of the previously obtained theorems—including a functorial duality result connecting classes of gGls and classes of structures for them.      

The Tits–Kantor–Koecher Construction and Birepresentations of the Jordan Superpair SH(1, n)

Abstract

We introduce the concept of bimodule over a Jordan superpair and the Tits– Kantor–Koecher construction for bimodules. Using the construction we obtain the classification of irreducible bimodules over the Jordan superpair SH(1, n). We also prove semisimplicity for a class of finite dimensional SH(1, n)-bimodules for n ≥ 3.     

Two complexity results on c-optimality in experimental design

Finding a c-optimal design of a regression model is a basic optimization problem in statistics. We study the computational complexity of the problem in the case of a finite experimental domain. We formulate a decision version of the problem and prove its NP\boldsymbol{\mathit{NP}}-completeness. We provide examples of computationally complex instances of the design problem, motivated by cryptography. The problem, being NP\boldsymbol{\mathit{NP}}-complete, is then relaxed; we prove that a decision version of the relaxation, called approximate c-optimality, is P-complete. We derive an equivalence theorem for linear programming: we show that the relaxed c-optimality is equivalent (in the sense of many-one LOGSPACE-reducibility) to general linear programming.     

Lattices of Games

We show that, for any set S of combinatorial games, the set of games all of whose immediate options belong to S forms a complete lattice. If every option of a game in S also lies in S, then this lattice is completely distributive.     

Interpolation properties for provability logics GL and GLP

We study interpolation properties of provability logics. We prove the Lyndon interpolation for GL and the uniform interpolation for GLP.     

Membership of A ∨ G for classes of finite weakly abundant semigroups

We consider the question of membership of A ∨ G, where A and G are the pseudovarieties of finite aperiodic semigroups, and finite groups, respectively. We find a straightforward criterion for a semigroup S lying in a class of finite semigroups that are weakly abundant, to be in A ∨ G. The class of weakly abundant semigroups contains the class of regular semigroups, but is much more extensive; we remark that any finite monoid with semilattice of idempotents is weakly abundant. To study such semigroups we develop a number of techniques that may be of interest in their own right.     

The Boundary Regularity of a Weak Solution of the Navier-Stokes Equation and its Connection to the Interior Regularity of Pressure

We assume that v is a weak solution to the non-steady Navier-Stokes initial-boundary value problem that satisfies the strong energy inequality in its domain and the Prodi-Serrin integrability condition in the neighborhood of the boundary. We show the consequences for the regularity of v near the boundary and the connection with the interior regularity of an associated pressure and the time derivative of v.     

The Abelian/Nonabelian correspondence and Frobenius manifolds

We propose an approach via Frobenius manifolds to the study (began in [BCK2] of the relation between rational Gromov–Witten invariants of nonabelian quotients X//G and those of the corresponding “abelianized” quotients X//T, for T a maximal torus in G. The ensuing conjecture expresses the Gromov–Witten potential of X//G in terms of the potential of X//T. We prove this conjecture when the nonabelian quotients are partial flag manifolds.     

Graded Modules Over the q-Analog Virasoro-Like Algebra

In this paper, we deal with the classification of the irreducible Z-graded and Z ²-graded modules with finite dimensional homogeneous subspaces for the q analog Virasoro-like algebra L. We first prove that a Z-graded L-module must be a uniformly bounded module or a generalized highest weight module. Then we show that an irreducible generalized highest weight Z-graded module with finite dimensional homogeneous subspaces must be a highest (or lowest) weight module and give a necessary and sufficient condition for such a module with finite dimensional homogeneous subspaces. We use the Z-graded modules to construct a class of Z ²-graded irreducible generalized highest weight modules with finite dimensional homogeneous subspaces. Finally, we classify the Z ²-graded L-modules. We first prove that a Z ²-graded module must be either a uniformly bounded module or a generalized highest weight module. Then we prove that an irreducible nontrivial Z ²-graded module with finite dimensional homogeneous subspaces must be isomorphic to a module constructed as above. As a consequence, we also classify the irreducible Z-graded modules and the irreducible Z ²-graded modules with finite dimensional homogeneous subspaces and center acting nontrivial. Supported by the National Science Foundation of China (No 10671160), the China Postdoctoral Science Foundation (No. 20060390693), the Specialized Research fund for the Doctoral Program of Higher Education (No.20060384002), and the New Century Talents Supported Program from the Education Department of Fujian Province.     

Endoprimal implication algebras

An algebra A is endoprimal if, for all , the only maps which preserve the endomorphisms of A are the n-ary term functions of A. The theory of natural dualities has been a very effective tool for finding finite endoprimal algebras. We study endoprimality within the variety of implication algebras, which does not contain any non-trivial dualisable algebras. We show that there are no non-trivial finite endoprimal implication algebras. We also give some examples of infinite implication algebras which are endoprimal. Received July 28, 1998; accepted in final form January 18, 1999.     

Solving Chisini’s functional equation

We investigate the n-variable real functions G that are solutions of the Chisini functional equation F(x) = F(G(x), . . . , G(x)), where F is a given function of n real variables. We provide necessary and sufficient conditions on F for the existence and uniqueness of solutions. When F is nondecreasing in each variable, we show in a constructive way that if a solution exists then a nondecreasing and idempotent solution always exists. We also provide necessary and sufficient conditions on F for the existence of continuous solutions and we show how to construct such a solution. We finally discuss a few applications of these results.     

Apery Sets of Numerical Semigroups #

Let S be a numerical semigroup. We examine a particular subset of the Apery set of S and establish a correspondence between this subset and the holes of S . This correspondence allows us to establish conditions for S to be almost symmetric.     

Topological Complexity of Motion Planning

   Abstract. In this paper we study a notion of topological complexity TC (X) for the motion planning problem. TC (X) is a number which measures discontinuity of the process of motion planning in the configuration space X . More precisely, TC (X) is the minimal number k such that there are k different "motion planning rules," each defined on an open subset of X× X , so that each rule is continuous in the source and target configurations. We use methods of algebraic topology (the Lusternik—Schnirelman theory) to study the topological complexity TC (X) . We give an upper bound for TC (X) (in terms of the dimension of the configuration space X ) and also a lower bound (in terms of the structure of the cohomology algebra of X ). We explicitly compute the topological complexity of motion planning for a number of configuration spaces: spheres, two-dimensional surfaces, products of spheres. In particular, we completely calculate the topological complexity of the problem of motion planning for a robot arm in the absence of obstacles.