Search

Linear Programming based lower bounds have been considered both for the general as well as for the symmetric quadratic assignment problem several times in the recent years. They have turned out to be quite good in practice. Investigations of the polytopes underlying the corresponding integer linear programming formulations (the non-symmetric and the symmetric quadratic assignment polytope) have been started by Rijal (1995), Padberg and Rijal (1996), and Jünger and Kaibel (1996, 1997). They have lead to basic knowledge on these polytopes concerning questions like their dimensions, affine hulls, and trivial facets. However, no large class of (facet-defining) inequalities that could be used in cutting plane procedures had been found. We present in this paper the first such class of inequalities, the box inequalities, which have an interesting origin in some well-known hypermetric inequalities for the cut polytope. Computational experiments with a cutting plane algorithm based on these inequalities show that they are very useful with respect to the goal of solving quadratic assignment problems to optimality or to compute tight lower bounds. The most effective ones among the new inequalities turn out to be indeed facet-defining for both the non-symmetric as well as for the symmetric quadratic assignment polytope.

Let E be an elliptic curve dened over a number eld F with everywhere good reduction. By dividing F -rational torsion points with respect to the group law of E M. Taylor dened certain Kummer orders and studied their Galois module structure. His results led to the conjecture that these Kummer orders are free over an explicitly given Hopf order. In this paper we prove that the conjecture does not hold for innitely many elliptic curves which are dened over quadratic imaginary number elds k and endowed with a k-rational 2torsion point.

This is a continuation of the paper “Zwei Klassen lokalkompakter maximal fastperiodischer Gruppen”, [6]. In [6], the classes $$\mathfrak{A}$$ and $$\mathfrak{D}$$ were introduced. We give sufficient conditions to conclude thatG is in $$\mathfrak{D}(\mathfrak{A} \cap \mathfrak{D})$$ if one knows thatG/G 0 is in $$\mathfrak{D}(\mathfrak{A} \cap \mathfrak{D})$$ . If a groupG is in $$\mathfrak{A} \cap \mathfrak{D}$$ and ifG satisfies the Chu-duality then all closed subgroups ofG satisfy the Chu-duality. The Chu-quasi-dual of the Heisenberg groupH with integral coefficients is computed. It is shown thatH does not satisfy the Chu-duality, thatH is in $$\mathfrak{A}$$ , and thatH is not in $$\mathfrak{D}$$ .

1. Lorenz, F.: Quadratische Formen uber Korpern. Lecture notes Math. 130. Berlin-Heidelberg-New York: Springer 1970. 2. Scharlau, W.: Quadratic forms. Queen's papers on pure and applied math. No. 22, Queen's University, Kingston, Ontario (1969). 3. Springer, T. A.: Sur les formes quadratiques d'indice zero. C.R.Acad. Sei. 234, 1517-1519(1952). 4. Witt, E.: Verschiedene Bemerkungen zur Theorie der quadratischen Formen uber einem Korper. Colloque d'Algebre Superieure, Bruxelles, 245-250 (1956). Manfred Knebusch Mathematisches Institut der Universitat BRD-6600 Saarbrucken 15 Deutschland