A new class of cutting planes for the symmetric travelling salesman problem

A comprehensive class of cutting planes for the symmetric travelling salesman problem (TSP) is proposed which contains the known comb inequalities, the path inequalities and the 3-star constraints as special cases. Its relation to the clique tree inequalities is discussed. The cutting planes are shown to be valid for a relaxed version of the TSP, the travelling salesman problem on a road network, and—under certain conditions—to define facets of the polyhedron associated with this problem.     

Chapter 1 Introduction: Extensions and new developments in DEA

The extensions, new developments and new interpretations for DEA covered in this paper include: (1) new measures of efficiency, (2) new models and (3) new ways of implementing established models with new results and interpretations presented that include treatments of congestion, returns-to-scale and mix and technical inefficiencies and measures of efficiency that can be used to reflect all pertinent properties. Previously used models, such as those used to identify allocative inefficiencies, are extended by means of assurance region approaches which are less demanding in their information requirements and underlying assumptions. New opportunities for research are identified in each section of this chapter. Sources of further developments and possible sources for further help are also suggested with references supplied to other papers that appear in this volume and which are summarily described in this introductory chapter.     

Borel fibrations and G-spaces

Considering discrete groups G only, we present an elementary proof of the familiar equivalence of the category of G-spaces (with maps equivariant up to homotopy) and the category of Borel fibrations over BG.     

A Nonlinear Problem Associated to the Motion of a Membrane

A nonlinear model associated to the motion of a membrane is considered as limit of a sequence of approximate models, for which a global existence and uniqueness theorem can be proved. The paper investigates the relationship between the solutions of the real and approximate models.     

Role of information in the stochastic zero-sum differential game

In this paper, a linear-quadratic Gaussian zero-sum differential game is studied. Maneuverability is defined to measure players' strength. It is shown that a more maneuverable player would prefer a more observable information system. An example is given to show that a more controllable player might not prefer more observable measurements in the stochastic environment.The research reported in this paper was made possible through support extended to the Division of Engineering and Applied Physics, Harvard University, by the US Office of Naval Research under the Joint Services Electronics Program by Contract No. N00014-75-c-0648 and by the National Science Foundation under Grant No. GK31511.     

On the continuity of midpoint hull convex set-valued functions

Summary The concept of hull convexity (midpoint hull convexity) for set-valued functions in vector spaces is examined. This concept, introduced by A. V. Fiacco and J. Kyparisis (Journal of Optimization Theory and Applications,43 (1986), 95–126), is weaker than one of convexity (midpoint convexity).The main result is a sufficient condition for a midpoint hull convex set-valued function to be continuous. This theorem improves a result obtained by K. Nikodem (Bulletin of the Polish Academy of Sciences, Mathematics,34 (1986), 393–399).     

Model reduction techniques for sampled-data systems

An approximately balanced realization of linear finite-dimensional sampled-data systems is proposed. The theoretical support of the approximately balancing algorithm is represented by a result on the asymptotic expansions with respect to the sampling step of the sampled controllability and observability graminas. Reduced order models obtained as singular perturbational approximations of approximately balanced realizations of sampled-data systems are shown to be acceptable solutions to the sampled-data system model reduction problem in the sense that, enjoying some asymptotic properties, they come close to the exact solutions as the sampling step decreases. An example illustrates the results.     

Invarianz gewisser Operatorenklassen unter nichtkommutativen ergodischen Mitteln

Let be a group of *-automorphisms on the algebra of bounded linear operators on a complex Hilbert space H. Then the strongly closed convex hull of the orbit of any compact operator under consists of compact operators. The same is true if one replaces compact by nuclear, Hilbert-Schmidt or positive Fredholm. We further discuss these results in the framework of the noncommutative mean ergodic theorem of KOVACS and SZ#x00FC;CS and formulate an analogous theorem for the algebra of compact operators on a complex Hilbert space.

---

---

Gefördert von der Deutschen Forschungsgemeinschaft im Rahmen des Forschungsvorhabens Ko 506/1.     

Ein Syntaktischer Beweis für die Zulässigkeit der Schnittregel im Kalkül von Schütte für die Intuitionistische Typenlogik

In [1] Girard gives a procedure, by which all derivations in the calculus of natural deductions of Prawitz [4] are transformed into normal derivations. Exploiting his idea we give a syntactical proof of the admissibility of the cut rule in Schütte's formal system of intuitionistic type theory. We obtain a normal form theorem but not a normalization theorem. Our Berechnungsprädikate are different from the candidats de reductibilite of Girard. In the case of second order logic Berechnungsprädikate für Terme t^(O) are not defined for derivations ending with r^O e t^(O) which are normalizable, but for finite formula sets with the property, that r^O e t^(O) is derivable without cut.     

A Framework for Evaluating Knowledge-Based Interestingness of Association Rules

In Knowledge Discovery in Databases (KDD)/Data Mining literature, interestingness measures are used to rank rules according to the interest a particular rule is expected to evoke. In this paper, we introduce an aspect of subjective interestingness called item-relatedness. Relatedness is a consequence of relationships that exist between items in a domain. Association rules containing unrelated or weakly related items are interesting since the co-occurrence of such items is unexpected. Item-Relatedness helps in ranking association rules on the basis of one kind of subjective unexpectedness. We identify three types of item-relatedness – captured in the structure of a fuzzy taxonomy (an extension of the classical concept hierarchy tree). An item-relatedness measure for describing relatedness between two items is developed by combining these three types. Efficacy of this measure is illustrated with the help of a sample taxonomy. We discuss three mechanisms for extending this measure from a two-item set to an association rule consisting of a set of more than two items. These mechanisms utilize the relatedness of item-pairs and other aspects of an association rule, namely its structure, distribution of items and item-pairs. We compare our approach with another method from recent literature.     

Kelley-Morse+Types of well order is not a conservative extension of Kelley Morse

Summary Assuming the consistency ofZF + There is an inaccessible number of inaccessibles, we prove that Kelley Morse theory plus types is not a conservative extension of Kelley-Morse theory.This paper was partially supported by: Dirección de Investigación de la Pontificia Universidad Católica de Chile (DIUC); Fondo Nacional de Desarrollo Científico y Tecnológico (FONDECYT)     

Stellare Abänderungen und Schälbarkeit von Komplexen und Polytopen

Brugesser and Mani proved that the boundary-complex of a convex polytope can be shelled. This result lead to McMullen's proof of the Upper-bound-conjecture. We show that the shellability of complexes has a close connection to the theory of stellar operations. Several results on special shelling procedures and on non-shellable complexes are obtained.     

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     

Approximation of continuous vector functions

We study the possibility of uniform approximation of continuous mappings of metric compact sets into metric spaces. Notions of weak dimension and weak Kolmogorov width are introduced to compare approximating properties of infinite-dimensional subspaces. For classes of mappings specified by the majorant of the modulus of continuity, we present bilateral estimates of weak widths that may coincide under certain conditions.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 46, No. 11, pp. 1435–1448, November, 1994.     

On affine scaling algorithms for nonconvex quadratic programming

We investigate the use of interior algorithms, especially the affine-scaling algorithm, to solve nonconvex — indefinite or negative definite — quadratic programming (QP) problems. Although the nonconvex QP with a polytope constraint is a hard problem, we show that the problem with an ellipsoidal constraint is easy. When the hard QP is solved by successively solving the easy QP, the sequence of points monotonically converge to a feasible point satisfying both the first and the second order optimality conditions.Research supported in part by NSF Grant DDM-8922636 and the College Summer Grant, College of Business Administration, The University of Iowa.     

Remark on the Helly number for strongly convex sets on Riemannian manifolds

Replacing convex by strongly convex we show that Helly's famous intersection theorem holds on every Riemannian n-manifold in the following form: The intersection of k relatively compact, strongly convex subsets of M (kn+i2) is nonvoid as soon as any n+i of these sets have a nonvoid intersection, where i=2 if M is homeomorphic to the standard n-sphere and i=1 otherwise.     

Two-phases Method and Branch and Bound Procedures to Solve the Bi–objective Knapsack Problem

The classical 0–1 knapsack problem is considered with two objectives. Two methods of the two–phases type are developed to generate the set of efficient solutions. In the first phase, the set of supported efficient solutions is determined by optimizing a parameterized single-objective knapsack problem. Two versions are proposed for a second phase, determining the non-supported efficient solutions: both versions are Branch and Bound approaches, but one is breadth first, while the other is depth first. Extensive numerical experiments have been realized to compare the results of both methods.     

Construction of Pseudorandom Binary Sequences Using Additive Characters

In earlier papers the authors studied finite pseudorandom binary sequences, and they constructed sequences with strong pseudorandom properties. In these earlier constructions multiplicative characters were used. In this paper a new construction is presented which utilizes properties of additive characters. These new sequences can be computed fast, they are well-distributed relative to arithmetic progressions and their correlations of small order are small, but the price paid for the fast computation is that the correlations of large order can be large.     

On the convergence of the multivariate “homogeneous”qd-algorithm

The convergence of columns in the univariateqd-algorithm to reciprocals of polar singularities of meromorphic functions has often proved to be very useful. A multivariateqd-algorithm was discovered in 1982 for the construction of the so-called homogeneous Padé approximants.In the first section we repeat the univariate convergence results. In the second section we summarize the homogeneous multivariateqd-algorithm. In the third section a multivariate convergence result is proved by combining results from the previous sections. This convergence result is compared with another theorem for the general order multivariateqdg-algorithm. The main difference lies in the fact that the homogeneous form detects the polar singularities pointwise while the general form detects them curvewise.     

Previsible sets for hyperfinite filtrations

Summary Previsible (or predictable) stochastic processes are defined for any filtration over a probability space (Dellacherie and Meyer (1978), IV. 61). This technical definition gives previsible processes certain predictability properties such as not being able to oscillate in unison with martingale differentials. Thus previsibility has become one essential ingredient in The General Theory of Stochastic Processes.We show that previsible sets for Keisler's (1984) special hyperfinite filtration are given both combinatorially and by a left filtration. Keisler's scheme has many other interesting features.Our main technical tool is an extension of Henson's (1979) analysis of analytic sets and the standard part map.