On the width—length inequality

This paper was written at the Rensselaer Polytechnic Institute in 1963. A lecture based on it was given at the Rand Corporation in 1965 and this version is in the form in which Ray Fulkerson received it at Rand.The paper is the underpinning for results on resistor network inequalities (Reference [4]) which has not been published. A specific example, however, appears inProceedings of the IEEE 51 (1963) 1047–1048. There is also a parallel theory of the abstract assignment problem; every W—L matrix being an assignment matrix.More is known about minimal non-W—L matrices. U. Peled has found several additional classes of matrices which are also classically known in other contexts. A consequence of a recent matrix theorem is apparently that the degenerate projective planes are the only minimal matrices requiring unequal weights.Due to unfortunate circumstances this article was originally published (Mathematical Programming 16(2)(1979) 245–259) without the proof corrections. Thecorrect version is printed herewith. Please use this version when referring to the paper.The preparation of this paper was supported by the National Science Foundation under grant GP-14. Editor's Note: This paper, although written in 1963, was sought for inclusion inMathematical Programming Study 8—Polyhedral Combinatorics, which was dedicated to the memory of D.R. Fulkerson. Unfortunately, an editorial mishap prevented its inclusion. Nevertheless, the historical importance of the paper, the fact that it has been widely referenced and influenced Fulkerson's and others' work in the area has convinced the Editor that it should be published and hence made readily available. Alfred Lehman has given his assent to this despite his reluctance to publish a paper which is not current.     

Almost integral polyhedra related to certain combinatorial optimization problems

The notion of an almost integral polyhedron is introduced and used to obtain a new proof of the characterization of perfect zero-one matrices which relies only on standard arguments from linear algebra and convexity. The characterization of perfect zero-one matrices in terms of forbidden submatrices is then used to derived the perfect-graph theorem due to Fulkerson and Lovász. Furthermore, a characterization of antiblocking pairs of zero-one matrices by means of a strengthened version of the max-max inequality due to Fulkerson is obtained which entails Lovász's recent characterization of perfect graphs.     

The Construction of Practical General Linear Methods

Using the property of inherent Runge—Kutta stability, it is possible to construct diagonally implicit general linear methods with stability regions exactly the same as for Runge—Kutta methods. In addition to A-stable methods found in this way, it is also possible to construct explicit methods with stability regions identical to those of explicit Runge—Kutta methods. The use of doubly companion matrices makes it possible to find all explicit and diagonally-implicit methods possessing the inherent Runge—Kutta stability property.This revised version was published online in October 2005 with corrections to the Cover Date.     

Identities for piecewise polynomial spaces determined by connection matrices

Summary TwoB-spline results — Marsden's identity and the de Boor-Fix dual functionals — are extended to geometrically continuous curves determined by connection matrices.Dedicated to the memory of Alexander M. Ostrowski on the occasion of the 100th anniversary of his birth.     

The Newtonian potential of homogeneous polyhedra

The Newtonian potential —U of an arbitrary homogeneous polyhedronD in three-dimensional space is represented in closed form.U, as a function of Cartesian coordinates, is the sum of 8k terms involving the elementary Artanh and arctan functions, wherek is the number of edges ofD.This expression is uniformly valid inD, on the boundary, or in the outside; only far away fromD it suffers from the loss of accuracy by cancellation. The present model includes multiply connected polyhedra as well as disjoint and overlapping regions. Finally, some applications to regular polyhedra are discussed.

---

Zusammenfassung Das Newtonsche Potential —U eines beliebigen homogen mit Masse belegten PolyedersD im dreidimensionalen Raum wird in geschlossener Form dargestellt.U erscheint als Summe von 8k Termen mit den elementaren Artanh- und arctan-Funktionen, wobeik die Anzahl der Kanten vonD ist. Dieser endliche Ausdruck gilt uniform inD, auf dem Rand und im Aeusseren; lediglich in grosser Ferne tritt Stellenauslöschung ein. Der verwendete Polyederbegriff schliesst auch mehrfach zusammenhängende und nicht zusammenhängende Gebiete ein. Zum Schluss werden einige Anwendungen auf die regulären Polyeder diskutiert.

---

---

Meinem verehrten Lehrer, Herrn Professor Eduard Stiefel, in Dankbarkeit gewidmet     

An algebraic characterization ofB-convergent Runge-Kutta methods

Summary In the analysis of discretization methods for stiff intial value problems, stability questions have received most part of the attention in the past.B-stability and the equivalent criterion algebraic stability are well known concepts for Runge-Kutta methods applied to dissipative problems. However, for the derivation ofB-convergence results — error bounds which are not affected by stiffness — it is not sufficient in many cases to requireB-stability alone. In this paper, necessary and sufficient conditions forB-convergence are determined.This paper was written while J. Schneid was visiting the Centre for Mathematics and Computer Science with an Erwin-Schrödinger stipend from the Fonds zur Förderung der wissenschaftlichen Forschung     

Numerical calculation of elliptic integrals and elliptic functions. III

Summary This paper is a continuation of [2, 3]. It contains anALGOL program for the incomplete elliptic integral of the third kind based on a theory described in [4]. This program replaces the inadequate one based on the Gauß-transformation which was published in [2]. In addition, anAlgol program for a general complete elliptic integral is presented. Editor's note. In this fascicle, prepublication of algorithms from the Special Functions Series of the Handbook for Automatic Computation is continued. Algorithms are published inAlgol 60 reference language as approved by the IFIP. Contributions in this series should be styled after the most recently published ones.This research was supported by the Advanced Research Projects Agency of the Department of Defense and was monitored by the U. S. Army Research Office —Durham under Contract DA-31-124-ARO-D-257.     

Two commodity network flows and linear programming

This paper shows that the linear programming formulation of the two-commodity network flow problem leads to a direct derivation of the known results concerning this problem. An algorithm for solving the problem is given which essentially consists of two applications of the Ford—Fulkerson max flow computation. Moreover, the algorithm provides constructive proofs for the results. Some new facts concerning feasible integer flows are also given.     

A note on some computationally difficult set covering problems

Fulkerson et al. have given two examples of set covering problems that are empirically difficult to solve. They arise from Steiner triple systems and the larger problem, which has a constraint matrix of size 330 × 45 has only recently been solved. In this note, we show that the Steiner triple systems do indeed give rise to a series of problems that are probably hard to solve by implicit enumeration. The main result is that for ann variable problem, branch and bound algorithms using a linear programming relaxation, and/or elimination by dominance require the examination of a super-polynomial number of partial solutionsThis paper was written while the author was a CORE Fellow at the Université de Louvain, Louvain-la-Neuve, Belgium.     

On the minimal convex annulus of a planar convex body

In this paper we introduce the notion of a minimal convex annulusK (C) of a convex bodyC, generalizing the concept of a minimal circular annulus. Then we prove the existence — as for the minimal circular annulus — of a Radon partition of the set of contact points of the boundaries ofK (C) andC. Subsequently, the uniqueness ofK (C) is shown. Finally, it is proven that, for typicalC, the boundary ofC has precisely two points in common with each component of the boundary ofK (C).     

Infinite flocks of a quadratic cone

In this article, we construct some infinite analogues of the Fisher flocks. We also consider maximal partial flocks which may be constructed in several ways. In particular, we show that any derivation of a flock inPG(3,K), forK a full field, produces either a flock or a maximal partial flock. We provide constructions which produce maximal partial flocks or maximal partial spreads.In memoriam, Giuseppe TalliniThis article was written while the authors were visiting the Ricco Institute during June of 1994 and was partially supported by Glasgow-Caledonian University. Also, the authors are indebted to Christian Boltanski,D — S, in the writing of this article.The authors also are indebted to the referee for helpful suggestions with regard to this article.     

K-greedy algorithms for independence systems

Recently inJenkyns [1976] andKorte/Hausmann [1978] a tight worst-case bound for the well-known greedy heuristic for general independence systems has been deduced. Here some modifications of the greedy heuristic are investigated which allow to enlarge the current independent set by more than one element. It is shown that in spite of the additional enumeration incorporated in these heuristics they can behave worse than the usual greedy heuristic for some problem instances. For one of those modifications the same worst-case bound as mentioned above — but no better one — has been proved again. These results underline the predominant role of the usual greedy heuristic for general independence systems.

---

Zusammenfassung Kürzlich wurde inJenkyns [1976] undKorte/Hausmann [1978] eine scharfe Gütegarantie für die bekannte Greedy-Heuristik für allgemeine Unabhängigkeitssysteme hergeleitet. Hier werden nun einige Modifikationen der Greedy-Heuristik untersucht, die es gestatten, die laufende unabhängige Menge durch mehr als ein Element zu vergrößern. Es wird gezeigt, daß sich diese Heuristiken — trotz der zusätzlich in sie eingebauten Enumeration — in Einzelfällen schlechter verhalten können als die gewöhnliche Greedy-Heuristik.Für eine dieser Modifikationen konnte wieder die gleiche Gütegarantie wie die oben erwähnte —aber keine bessere — bewiesen werden. Diese Ergebnisse unterstreichen die beherrschende Rolle der gewöhnlichen Greedy-Heuristik für allgemeine Unabhängigkeitssysteme.

     

Convergence of Runge-Kutta Methods for Delay Differential Equations

This paper deals with the adaptation of Runge—Kutta methods to the numerical solution of nonstiff initial value problems for delay differential equations. We consider the interpolation procedure that was proposed in In 't Hout [8], and prove the new and positive result that for any given Runge—Kutta method its adaptation to delay differential equations by means of this interpolation procedure has an order of convergence equal to min {p,q}, where p denotes the order of consistency of the Runge—Kutta method and q is the number of support points of the interpolation procedure.This revised version was published online in October 2005 with corrections to the Cover Date.     

A well-conditioned estimator for large-dimensional covariance matrices

Many applied problems require a covariance matrix estimator that is not only invertible, but also well-conditioned (that is, inverting it does not amplify estimation error). For large-dimensional covariance matrices, the usual estimator—the sample covariance matrix—is typically not well-conditioned and may not even be invertible. This paper introduces an estimator that is both well-conditioned and more accurate than the sample covariance matrix asymptotically. This estimator is distribution-free and has a simple explicit formula that is easy to compute and interpret. It is the asymptotically optimal convex linear combination of the sample covariance matrix with the identity matrix. Optimality is meant with respect to a quadratic loss function, asymptotically as the number of observations and the number of variables go to infinity together. Extensive Monte Carlo confirm that the asymptotic results tend to hold well in finite sample.     

On some properties of the curvature and Ricci tensors in complex affine geometry

We present a new approach — which is more general than the previous ones — to the affine differential geometry of complex hypersurfaces inC ⁿ⁺¹. Using this general approach we study some curvature conditions for induced connections.The research supported by Alexander von Humboldt Stiftung and KBN grant no. 2 P30103004.     

Activity graphs: A language for flexible consultation systems

An intelligent decision system (IDS) uses artificial intelligence principles to deliver automated, interactive decision analysis (DA) consultations. Network methods adapted from operations research underlie two key IDS components: influence diagrams and activity graphs. Influence diagrams, which are familiar to DA researchers and practitioners, represent decision problems inevent space. Activity graphs, which are introduced in this paper, represent processes inaction space. While activity graphs can represent any process, we use them as a knowledge-engineering and programming language to represent the process knowledge of skilled decision analysts in the context of a specific class of decisions. This paper defines activity graphs as an extension of directed AND-OR graphs. Anactivity tree is a directed AND-OR tree consisting of nodes, which may contain activities (small computer programs) and connectors that establish logical relationships among nodes and define logical resolution agendas. Anactivity graph is a directed, multiply connected network of activity trees. Activity graphs may involve recursion. Development of the activity graph language is motivated by our desire to enable professional decision analysts — or other experts — with limited advanced programming experience to design and build consultation systems that combine the guidance offered by protocol systems with the flexibility and generality of transaction systems. This paper defines the activity graph language in detail. A simple example illustrates key concepts. The paper also discusses our experience using a computer system that implements activity graphs for developing commercial IDSs.     

The uniqueness for minimal surfaces inS 3

We give a sufficient condition on a Jordan curve in the 3-dimensional open hemisphereH ofS ³ in terms of the Hopf fibering under which spans a unique compact generalized minimal surface inH. The maximum principle for minimal surfaces inS ³ is proved and plays an important role in the proof of the uniqueness theorem.Dedicated to Professor Shingo Murakami on his 60th birthdayThis work was carried out while the author was a visitor to the Max-Planck-Institut für Mathematik.     

Mono-Implicit Runge-Kutta-Nyström Methods with Application to Boundary Value Ordinary Differential Equations

The successful use of mono-implicit Runge—Kutta methods has been demonstrated by several researchers who have employed these methods in software packages for the numerical solution of boundary value ordinary differential equations. However, these methods are only applicable to first order systems of equations while many boundary value systems involve higher order equations. While it is straightforward to convert such systems to first order, several advantages, including substantial gains in efficiency, higher continuity of the approximate solution, and lower storage requirements, are realized when the equations can be treated in their original higher order form. In this paper, we consider generalizations of mono-implicit Runge—Kutta methods, called mono-implicit Runge—Kutta—Nyström methods, suitable for systems of second order ordinary differential equations having the general form, y(t) = f(t,y(t),y(t)), and derive optimal symmetric methods of orders two, four, and six. We also introduce continuous mono-implicit Runge—Kutta—Nyström methods which allow us to provide continuous solution and derivative approximations. Numerical results are included to demonstrate the effectiveness of these methods; savings of 65% are attained in some instances.This revised version was published online in October 2005 with corrections to the Cover Date.     

Some applications of computers to the investigation of substitutional dynamical systems

A new sufficient condition for topological mixing of a permutational dynamical system is given. Using a computer, it was verified for a system studied earlier by other methods. For a permutation that does not satisfy the above sufficient condition, topological mixing is proved by a rather general method of recurrence relations. The formulas expressing these relations are written by a computer.Published inZapiski Nauchnykh Seminarov POMI, Vol. 240, 1997, pp. 147–153.     

AIC, Overfitting Principles, and the Boundedness of Moments of Inverse Matrices for Vector Autotregressions and Related Models

In his somewhat informal derivation, Akaike (in “Proceedings of the 2nd International Symposium Information Theory” (C. B. Petrov and F. Csaki, Eds.), pp. 610–624, Academici Kiado, Budapest, 1973) obtained AIC's parameter-count adjustment to the log-likelihood as a bias correction: it yields an asymptotically unbiased estimate of the quantity that measures the average fit of the estimated model to an independent replicate of the data used for estimation. We present the first mathematically complete derivation of an analogous property of AIC for comparing vector autoregressions fit to weakly stationary series. As a preparatory result, we derive a very general “overfitting principle,” first formulated in a more limited context in Findley (Ann. Inst. Statist. Math.43, 509–514, 1991), asserting that a natural measure of an estimated model's overfit due to parameter estimation is equal, asymptotically, to a measure of its accuracy loss with independent replicates. A formal principle of parsimony for fitted models is obtained from this, which for nested models, covers the situation in which all models considered are misspecified. To prove these results, we establish a set of general conditions under which, for each τ1, the absolute τth moments of the entries of the inverse matrices associated with least squares estimation are bounded for sufficiently large sample sizes.