Solution of large-scale symmetric travelling salesman problems

In this paper we report on a cutting plane procedure with which we solved symmetric travelling salesman problems of up to 1000 cities to optimality. Our implementation is based on a fast LP-solver (IBM's MPSX) and makes effective use of polyhedral results on the symmetric travelling salesman polytope. We describe the important ingredients of our code and give an extensive documentation of its computational performance.Supported by DFG-Schwerpunkt Anwendungsbezogene Optimierung und Steuerung Universität Augsburg, Germany.Supported by SFB 303 (DFG), Forschungsinstitut für Diskrete Mathematik, Institut für Operations Research, Universität Bonn, Germany.     

Gruppen,die von ihren endlichen lokalen Subnormalteilern überdeckt sind

Ohne ZusammenfassungDiese Arbeit ist ein erweiterter Auszug aus meiner Dissertation Verallgemeinerungen periodischerFC-Gruppen, die von der Fakultät für Mathematik der Julius-Maximilians-Universität Würzburg angenommen wurde.     

Convergence of sequential and asynchronous nonlinear paracontractions

Summary We establish the convergence of sequential and asynchronous iteration schemes for nonlinear paracontracting operators acting in finite dimensional spaces. Applications to the solution of linear systems of equations with convex constraints are outlined. A first generalization of one of our convergence results to an infinite pool of asymptotically paracontracting operators is also presented.Research supported in part by Sonderforschungsbereich 343 Diskrete Strukturen in der MathematikResearch supported in part by NSF Grant DMS-9007030 and by Sonderforschungsbereich 343 Diskrete Strukturen in der Mathematik, Fakultät für Mathematik at the Universität BielefeldResearch supported in part by U.S. Air Force Grant AFOSR-88-0047, by NSF Grants DMS-8901860 and DMS-9007030, and by Sonderforschungsbereich 343 Diskrete Strukturen in der Mathematik, Fakultät für Mathematik at the Universität Bielefeld     

An infeasible-interior-point algorithm using projections onto a convex set

We present a new class of primal-dual infeasible-interior-point methods for solving linear programs. Unlike other infeasible-interior-point algorithms, the iterates generated by our methods lie in general position in the positive orthant of ² and are not restricted to some linear manifold. Our methods comprise the following features: At each step, a projection is used to recenter the variables to the domainx _i s _i . The projections are separable into two-dimensional orthogonal projections on a convex set, and thus they are seasy to implement. The use of orthogonal projections allows that a full Newton step can be taken at each iteration, even if the result violates the nonnegativity condition. We prove that a short step version of our method converges in polynomial time.Research performed while visiting the Institut für Angewandte Mathematik, University of Würzburg, D-87074 Würzburg, Germany, as a Research Fellow of the Alexander von Humboldt Foundation.     

On Shikata's distance between differentiable structures

Shikata proved: there is a number (n) with the following property: If two compact homeomorphic n-dimensional manifolds have a distance less than (n), then they are diffeomorphic. We improve the known lower bound (n!)^–n for (n) to 1/3n ^–2.This work was done under the program Sonderforschungsbereich Theoretische Mathematik (SFB 40) at Bonn University while Shikata was SFB-guest at Bonn.     

Randregularität des\bar \partial -Problems für die Halbkugel in ℂn

Let f be a -closed (0, q+1)-form defined on the half ball B₊ in ⁿ, which is of class C^k on ¯B. We prove the existence with C^k-estimates of a solution u of the equation .

---

---

Die Anregung zu dieser Arbeit verdanke ich auch Herrn Piotr Jakóbczak aus Krakau, der sich eine gewisse Zeit am Max-Planck-Institut für Mathematik in Bonn aufhielt. Während dieser Zeit untersuchten wir die C⁰-Abschätzungen für die Halbkugel in ⁿ     

Energy stability of channel flows

Zusammenfassung Die Energiemethode wird zur Untersuchung der Stabilität einer beliebigen Kanalströmung angewandt. Es wird eine auf Eigenwertabschätzungen basierte qualitative Beschreibung der Fläche (, ) gegeben, welche die Schranke für den Instabilitätsbereich in Abhängigkeit von Längs- bzw. Querwellenzahl der Störungen darstellt. Eine allgemeine untere Grenze für die minimalisierende Querwellenzahl und den zugehörigen Eigenwert (0, ) wird angegeben. Das Problem der Energiestabilität wird dann für eine Klasse von Geschwindigkeitsprofilen mit Wendepunkt gelöst. Die durch numerische Integration erhaltenen Ergebnisse werden mit den Ergebnissen der linearen Stabilitätstheorie verglichen.     

Fehlerabschätzungen für Koeffizienten von Exponentialsummen und Polynomen

Zusammenfassung Für Polynome und Exponentialsummen mit festen Frequenzen werden die Normäquivalenzkonstanten zwischen Parameterraum und Funktionenraum untersucht. Dies führt im Exponentialsummenfall auf Tschebyscheff-Exponentialsummen als Verallgemeinerung der Tschebyscheff-Polynome, wenn man nach numerisch praktikablen Strategien zur Fehlerabschätzung im Parameterraum sucht; für theoretische Zwecke wird eine Ungleichung von Markoff-Typ für Exponentialsummen hergeleitet. Im Falle der Polynome ergeben sich asymptotisch optimale Konstanten als Verschärfungen von Resultaten von Gautschi. Ferner wird eine elementare Herleitung der Normäquivalenzkonstanten für den Fall der Monombasis angegeben.

---

Error estimation in coefficients of exponential sums and polynomials

Summary Equivalence constants for the norms on parameter and function space are considered for both polynomials and exponential sums. In the latter case Chebyshev exponential sums are introduced as generalizations of the Chebyshev polynomials, providing a practical method for error estimation in parameter space. For theoretical purposes a Markoff-type inequality is proved. In the case of polynomials asymptotically optimal constants are derived, thus improving on earlier results of Gautschi. Furthermore, a simple construction of the equivalence constants for the monomial basis is included.

Diese Arbeit entstand als Studie Nr.2 des SFB 135 Ökosysteme auf Kalkgestein unter teiweiser Förderung durch die Deutsche Forschungsgemeinschaft. Die numerischen Rechnungen wurden auf der Rechenanlage der Gesellschaft für wissenschaftliche Datenverarbeitung in Göttingen durchgeführt     

Reihenentwicklungen im Weylschen Grenzkreisfall über einem halbunendlichen Intervall

Zusammenfassung Im Anschlu an eine frühere Arbeit beweisen wir im Grenzkreisfall für das Intervall s< einen Entwicklungssatz für reelle Funktionen bei vorgeschriebenen reellen Randbedingungen in s=0 und s=. Die Hilfsmittel sind: 1) der reelle Ansatz; 2) der explizite Ausdruck für die Greensche Funktion von Weyl und 3) die allgemeine Parsevalsche Gleichung.     

Parabelscharen und grenzkreise in der isotropen ebene

It is known by H. Sachs [5] that the classical curve theorem of ABRAMESCU also holds in isotropic geometry. Generalising an idea due to O. Röschel [2] we regard all inscribed parabolas (s, t) of a triangle (t). This triangle is formed by the tangents of three neighbouring points of a C -curve k(t) in an isotropic plane. Let U((t)) be the circumcircle of (t) and I((t)) the incircle of the triangle (t) whose midpoints of the sides are the vertices of (t). The circle U((t)) is the locus of the isotropic focal points of (s, t) and the incircle I((T)) the envelope of the isotropic axes of (s, t). We prove that the ABRAMESU-circle — lim U((t)) — is identical with the locus of the focal points of lim (s, t) and the circle lim I((t)) with the envelope of the axes of lim (s, t). The characteristic points, different from k(t), of the circles lim U((t)) and lim I((t)) determine the direction of the affine-normal of k(t).Herrn Professor Helmut Mäurer zum 60. Geburtstag gewidmet     

Generalized cylinders in semi-Riemannian and spin geometry

We use a construction which we call generalized cylinders to give a new proof of the fundamental theorem of hypersurface theory. It has the advantage of being very simple and the result directly extends to semi-Riemannian manifolds and to embeddings into spaces of constant curvature. We also give a new way to identify spinors for different metrics and to derive the variation formula for the Dirac operator. Moreover, we show that generalized Killing spinors for Codazzi tensors are restrictions of parallel spinors. Finally, we study the space of Lorentzian metrics and give a criterion when two Lorentzian metrics on a manifold can be joined in a natural manner by a 1-parameter family of such metrics.Mathematics Subject Classification (2000): 53C27,53A07,53B30Acknowledgement The authors would like to thank W. Ballmann, H. Karcher, as well as the referee, for valuable suggestions. The authors have been partially supported by the Research and Training Network HPRN-CT-2000-00101 EDGE funded by the European Commission. The first author has also been partially supported by the Research and Training Network HPRN-CT-1999-00118 Geometric Analysis. The first author would like to thank the Ecole Polytechnique, Palaiseau, and the the Max-Planck-Institut für Mathematik, Bonn, for their hospitality.     

Über die Kleinsche Ikosaeder-Kurve sechsten Grades

Ohne ZusammenfassungDiese Arbeit wurde unterstützt vom Mathematischen Institut der Universität Bonn, SFB 40 Theoretische Mathematik     

Beitrag zur Reduktion des Entscheidungsproblems auf Klassen von Hornformeln mit kurzen Alternationen

Ohne Zusammenfassung Zusatz bei der Korrektur: Ein vollständiger und korrekter Beweis für die Entscheidbarkeit der eingangs angeführten Aanderaaschen Klasse ((0, ), (, , ...)) erscheint demnächst im JSL (S.O. Aanderaa/H.R.Lewis: Prefix classes of Krom formulas). Ebendort wird auch die Reduktionstypeneigenschaft für ((0, ), (0, 0, )) und ((0, )), (0, 0, )) nachgewiesen, während ((0, ), (, )) sich als entscheidbar herausgestellt hat (s. E. Börger: Eine entscheidbare Klasse von Kromformeln. ZMLG 19 (1973), 117–120.) Der Kromsche Reduktionstyp konnte mittlerweile einerseits zu ((0, ), (0, 4)) verschärft werden (s. D. Rödding, E. Börger: The undecidability of (0, 4)-formulae with binary disjunctions, vorgetragen auf dem Logic Coll. Bristol 1973, ein abstract erscheint im JSL), andererseits kündigt H.R.Lewis die Reduktionstypeneigenschaft für ((0, ), (0, 1)) an (s. H.R.Lewis: Krom formulas with one dyadic predicate letter. Notices AMS 20, 5 (1973) A-500, abstr. no. 73T-E78.)Dieser Aufsatz geht aus der Dissertation [2] hervor, die dem Fachbereich Mathematik der Mathematisch-Naturwissenschaftlichen Fakultät der Universität Münster im Sommersemester 1971 vorgelegt worden ist. Die Ergebnisse stammen aus dem Wintersemester 1970/71. Eine Ankündigung der hauptsächlichen Resultate ist in den Notices of the American Mathematical Society 19, 2 (1972) A-333 unter der abstract no. * 72T-E24 erschienen.     

A general minimax theorem

This paper is concerned with minimax theorems for two-person zero-sum games (X, Y, f) with payofff and as main result the minimax equality inf supf (x, y)=sup inff (x, y) is obtained under a new condition onf. This condition is based on the concept of averaging functions, i.e. real-valued functions defined on some subset of the plane with min {x, y}< (x, y)x, y} forx y and (x, x)=x. After establishing some simple facts on averaging functions, we prove a minimax theorem for payoffsf with the following property: Forf there exist averaging functions and such that for any x₁, x₂ X, > 0 there exists x₀ X withf (x₀, y) > f (x₁,y),f (x₂,y))– for ally Y, and for any y₁, y₂ Y, > 0 there exists y₀ Y withf (x, y₀) (f (x, y₁),f (x, y₂))+. This result contains as a special case the Fan-König result for concave-convex-like payoffs in a general version, when we take linear averaging with (x, y)=x+(1–)y, (x, y)=x+(1–)y, 0 <, < 1.Then a class of hide-and-seek games is introduced, and we derive conditions for applying the minimax result of this paper.

---

Zusammenfassung In dieser Arbeit werden Minimaxsätze für Zwei-Personen-Nullsummenspiele (X, Y,f) mit Auszahlungsfunktionf behandelt, und als Hauptresultat wird die Gültigkeit der Minimaxgleichung inf supf (x, y)=sup inff (x, y) unter einer neuen Bedingung an f nachgewiesen. Diese Bedingung basiert auf dem Konzept mittelnder Funktionen, d.h. reellwertiger Funktionen, welche auf einer Teilmenge der Ebene definiert sind und dort der Eigenschaft min {x, y} < < (x, y)x, y} fürx y, (x, x)=x, genügen. Nach der Herleitung einiger einfacher Aussagen über mittelnde Funktionen beweisen wir einen Minimaxsatz für Auszahlungsfunktionenf mit folgender Eigenschaft: Zuf existieren mittelnde Funktionen und, so daß zu beliebigen x₁, x₂ X, > 0 mindestens ein x₀ X existiert mitf (x₀,y) (f (x ₁,y),f (x₂,y)) – für alley Y und zu beliebigen y₁, y₂ Y, > 0 mindestens ein y₀ Y existiert mitf (x, y₀) (f (x, y₁),f (x, y ₂))+ für allex X. Dieses Resultat enthält als Spezialfall den Fan-König'schen Minimaxsatz für konkav-konvev-ähnliche Auszahlungsfunktionen in einer allgemeinen Version, wenn wir lineare Mittelung mit (x, y)=x+(1–)y, (x, y)= x+(1–)y, 0 <, < 1, betrachten.Es wird eine Klasse von Suchspielen eingeführt, welche mit dem vorstehenden Resultat behandelt werden können.

     

On the linear isoperimetric inequality

This paper contains a sharp version of the well-known linear isoperimetric inequality for minimal surfacesX area(X)1/2oscillation(X)length(X).Supported by Sonderforschungsbereich 72 der Deutschen Forschungsgemeinschaft at Bonn University.     

Quadratische Semi-Ordnungen und quadratische Formen

Ohne ZusammenfassungDie Ergebnisse über quadratische Semi-Ordnungen entstammen zum größten Teil der Habilitationsschrift des Autors an der Universität Bonn vom Februar 1972. Diese Arbeit wurde im Rahmen des Programms des SFB Bonn Theoretische Mathematik verfaßt.     

On perfect graphs and polyhedra with (0, 1)-valued extreme points

LetC andA be (0, 1)-valued matrices with no zero columns. Fulkerson has shown that the extreme points of {x: Cx 1,x 0} are given by the rows ofA and their projections and the extreme points of {x: Ax 1,x 0} are given by the rows ofC and their projections if and only if the maximal rows ofC andA are the incidence vectors of maximal cliques and anticliques, respectively, of a perfect graph. This theorem is discussed and a new proof is given for the only if implication.Research partially supported by grant ENG 76-09936 from the National Science Foundation to Cornell University and by Sonderforschungsbereich 21 (DFG), Institut für Operations Research, Universität Bonn.     

Zur Stützpunktwahl beim Schnittverfahren der nichtlinearen Programmierung

Zusammenfassung In dem vonK. Kleibohm vorgeschlagenen Schnittverfahren der konvexen Programmierung ist die Wahl des Stützpunktes von großer Bedeutung. Die Untersuchung der für Stützebenen eingeführten Relation besser sowie des für dieses Schnittverfahren charakteristischen Ablösemechanismus für Stützebenen erlauben die Formulierung und Begründung zweier Forderungen zur Stützpunktwahl. Die Realisierung dieser Forderung führt zur Lösung eines Entscheidungsproblems.

---

Summary The efficiency of the cutting plane method of the convex programming suggested byK. Kleibohm may be increased by a skillful choice of the so-called Stützpunkt. The study of the relation besser, defined for supporting hyperplanes, as the study of the detach-mechanism of supporting hyperplanes characteristic for this cutting plane method will allow to formulate and propose two demands concerning the choice of the Stützpunkt. The realisation of these demands leads to the solution of a decision problem.

     

Beiträge zur Dekomposition von linearen Programmen

Zusammenfassung Das Ziel dieser Arbeit besteht vor allem darin, die Zusammenhänge der Dekompositionsmethoden für lineare Programme vonDantzig/Wolfe, Abadie/Williams, Benders, Rosen usw. aufzusuchen. In Kapitel I und III werden diese Methoden mehr oder weniger ausführlich behandelt. Für einige Sätze werden neue Beweise angegeben. In Kapitel II entwickeln wir eine neue Dekompositionsmethode, die aus der Kombination des primaldualen Verfahrens mit derDantzig/Wolfeschen Dekomposition entsteht. Der Idee vonCharnes/Cooper folgend benützen wir dyadische Transformationen in Kapitel IV, um mehrstufige und Transportprobleme durch Dekomposition zu lösen. Schließlich werden in Kapitel V Überlicke über Anwendungen, Erweiterungen für nichtlineare Programmierung und einige Ausblicke gegeben.

---

Summary In this paper we are concerned with the decomposition methods ofDantzig/Wolfe, Abadie/Williams, Benders andRosen, particularly to show the relations among them. A new method, the primal-dual decomposition method is developed. FollowingCharnes/Cooper, dyadic transformations are used to solve various linear programs by decomposition. A survey of extensions and applications is also given.

---

---

Diese Arbeit wurde von der Philosophischen Fakultät II der Universität Zürich als Dissertation angenommen.     

Fenchel-type duality for matroid valuations

The weighted matroid intersection problem has recently been extended to the valuated matroid intersection problem: Given a pair of valuated matroidsM _i = (V, _i , _i ) (i = 1,2) defined on a common ground setV, find a common baseB _{1 2} that maximizes ₁ (B) + ₂ (B). This paper develops a Fenchel-type duality theory related to this problem with a view to establishing a convexity framework for nonlinear integer programming. A Fenchel-type min max theorem and a discrete separation theorem are given. Furthermore, the subdifferentials of matroid valuations are investigated. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Part of this paper has been presented at fifth SIAM Conference on Optimization, Victoria, May 1996.This work was done while the author was at Forschungsinstitut für Diskrete Mathematik, Universität Bonn, 1994–1995.