The Cayley Trick, lifting subdivisions and the Bohne-Dress theorem on zonotopal tilings

In 1994, Sturmfels gave a polyhedral version of the Cayley Trick of elimination theory: he established an order-preserving bijection between the posets of coherent mixed subdivisions of a Minkowski sum ?₁+...+? _r of point configurations and of coherent polyhedral subdivisions of the associated Cayley embedding ?(?₁,...,? _r ). In this paper we extend this correspondence in a natural way to cover also non-coherent subdivisions. As an application, we show that the Cayley Trick combined with results of Santos on subdivisions of Lawrence polytopes provides a new independent proof of the Bohne-Dress theorem on zonotopal tilings. This application uses a combinatorial characterization of lifting subdivisions, also originally proved by Santos. Received February 18, 1999 / final version received January 25, 2000?Published online May 22, 2000     

Die HOWARDsche Berechnung optimalen Anschaffungs- und Betriebsalters für Kraftwagen: Ein ergänzender Befund mit deutschen Daten

Zusammenfassung Mit Hilfe des Iterationsverfahrens vonHoward wird das optimale Anschaffungs-und Betriebsalter für ein deutsches PKW-Fabrikat bestimmt. Diese Zeiten liegen unterhalb der entsprechenden Werte, dieHoward auf Grund amerikanischer Daten erhalten hat.

---

Summary By aid of theHoward-Algorithm the optimal purchase- and operating age for a German automobile is determined. These time-spans are lying below the corresponding values which were received byHoward on account of American data.

---

---

Vorgel. v.: H.P.Künzi.     

Mathematische Grundlagen zur nichtlinearen Aktivitätsanalyse

Zusammenfassung Das Ziel der vorliegenden Arbeit ist es, die Menge der effizienten Aktivitäten einer konvexen Technologie zu untersuchen. Es wird gezeigt, daß der Begriff der Facette aus der linearen Aktivitätsanalyse auch im Fall einer beliebigen konvexen Technologie definiert werden kann, und es werden für diesen allgemeinen Fall analoge Sätze über Facetten bewiesen. Die Beschreibung der Facetten einer Technologie durch geeignete Preis-(oder Bewertungs-)systeme kann in voller Allgemeinheit gegeben werden.

---

Summary The purpose of this paper is to study the set of efficient activities of a convex technology. It is shown that the concept of a facet, as it is used in linear activity analysis, can also be defined in the case of an arbitrary convex technology; for this general case analogous theorems on facets are proved. A characterization of the facets of a technology by suitable price (or valuation) systems can be given in full generality.

---

---

Der Autor hat über mathematische Grundlagen der linearen Aktivitätsanalyse, wie sie inKoopmans [3], chap. III entwickelt wurde, in einem von Prof.W. Wittmann geleiteten Kolloquium an der Universität Heidelberg im S. S. 1964 und W. S. 1964/65 vorgetragen.

---

Vorgel. v.:W. Wittmann.     

An adaptive discretization for Tikhonov-Phillips regularization with a posteriori parameter selection

Summary. The aim of this paper is to describe an efficient adaptive strategy for discretizing ill-posed linear operator equations of the first kind: we consider Tikhonov-Phillips regularization with a finite dimensional approximation instead of A. We propose a sparse matrix structure which still leads to optimal convergences rates but requires substantially less scalar products for computing compared with standard methods. Received September 16, 1998 / Revised version received August 4, 1999 / Published online August 2, 2000     

On a stratification of the moduli of K3 surfaces

In this paper we give a characterization of the height of K3 surfaces in characteristic p>0. This enables us to calculate the cycle classes in families of K3 surfaces of the loci where the height is at least h. The formulas for such loci can be seen as generalizations of the famous formula of Deuring for the number of supersingular elliptic curves in characteristic p. In order to describe the tangent spaces to these loci we study the first cohomology of higher closed forms. Received October 14, 1999 / final version received February 22, 2000?Published online May 22, 2000     

Zur algebraischen Kennzeichnung mehrwertiger Halbordnungen

The radical R(T) of a planar ternary ring (PTR) T, which plays an important role in the theory of halforderings and orderings of PTRs, allows also to give an algebraic characterization ofJunkers' multiple-valued halforderings of projective planes. As an application we obtain some information on the group of projectivities in projective planes.

---

---

Herrn Professor G. Tallini zum 60. Geburtstag gewidmet     

Zyklische Orientierungen endlicher bewerteter Graphen

Starting from problem 4 ofK. Wagner [2],H. Fleischner andP. D. Vestergaard [1] introduce the notion of a value-true walk in a finite, connected graph, the edges of which are valuated with nonnegative integers. Their main theorem states that the existence of such a walk is equivalent to the existence of an orientation of the edges with the following property: For every vertex the sum of the valuations of the incoming edges equals the sum of the valuations of the outgoing edges. Let us call such an orientation a cyclic one. In the present paper we study finite, valuated graphs that admit a cyclic orientation. First, we give two necessary conditions for a valuated graphG to admit a cyclic orientation concerning the stars and the bonds ofG, respectively. (The starS (v) of a vertexv is the set of all edges ofG incident withv.) Then, as the main part of the paper we give a characterization of those graphs for which the star- and the bond-condition is sufficient, respectively (for any valuation of the graph). These characterizations are in terms of constructability from trees andK ₃, respectively, as well as in terms of forbidden subgraphs.

---

---

Mit 2 Abbildungen     

Linear preselective policies for stochastic project scheduling

In the context of stochastic resource-constrained project scheduling we introduce a novel class of scheduling policies, the linear preselective policies. They combine the benefits of preselective policies and priority policies; two classes that are well known from both deterministic and stochastic scheduling. We study several properties of this new class of policies which indicate its usefulness for computational purposes. Based on a new representation of preselective policies as and/or precedence constraints we derive efficient algorithms for computing earliest job start times and state a necessary and sufficient dominance criterion for preselective policies.  A computational experiment based on 480 instances empirically validates the theoretical findings.     

Some Geometric Characterizations of the Hopf Fibrations of the Three-Sphere

The Fréchet manifold of all embeddings (up to orientation preserving reparametrizations) of the circle in S ³ has a canonical weak Riemannian metric. We use the characterization obtained by H. Gluck and F. Warner of the oriented great circle fibrations of S ³ to prove that among all such fibrations π:S ³→B, the manifold B consisting of the oriented fibers is totally geodesic in , or has minimum volume or diameter with the induced metric, exactly when π is a Hopf fibration. Partially supported by foncyt, Antorchas, ciem (conicet) and secyt (unc).     

Analytic Semigroups on C [0,1] Generated by Some Classes of Second Order Differential Operators

C [0,1], α > 0 in (0,1) and α(1), we consider the second order differential operator on C[0,1] defined by Au: = αu″ + βu′, where D(A) may include Wentzell boundary conditions. Under integrability conditions involving √α and β/√α, we prove the analyticity of the semigroup generated by (A,D(A)) on Co[0,1], Cπ[0,1] and on C[0,1], where Co[0,1]: {u∈ C[0,1]|u (1)} and Cπ[0,1]: = {u∈ C[0,1]| u (0) = u (1)}. We also prove different characterizations of D(A) related to some results in [1], where β≡ 0, exhibiting peculiarities of Wentzell boundary conditions. Applications can be derived for the case αx = x ^k (1 - x )^kγ(x )(k≥j/2, x∈ [0,1], γ∈ C{0,1}).     

Lokal endliche Andre-Systeme

Lüneburg's generalization of a construction ofAndre is used to describe all countable, locally finite André-systems and the locally finite André-nearfields. The last section gives a characterization of those countable, locally finite André-planes which have locally finite groups of affine projectivites.

---

---

Herrn Professor Dr. Walter Benz zum 60. Geburtstag     

Recognizing Planar Strict Quasi-Parity Graphs

 A graph is a strict-quasi parity (SQP) graph if every induced subgraph that is not a clique contains a pair of vertices with no odd chordless path between them (an “even pair”). We present an O(n ³) algorithm for recognizing planar strict quasi-parity graphs, based on Wen-Lian Hsu's decomposition of planar (perfect) graphs and on the (non-algorithmic) characterization of planar minimal non-SQP graphs given in [9]. Received: September 21, 1998 Final version received: May 9, 2000     

Properties of Distortion Risk Measures

The current literature does not reach a consensus on which risk measures should be used in practice. Our objective is to give at least a partial solution to this problem. We study properties that a risk measure must satisfy to avoid inadequate portfolio selections. The properties that we propose for risk measures can help avoid the problems observed with popular measures, like Value at Risk (VaR _α ) or Conditional VaR _α (CVaR _α ). This leads to the definition of two new families: complete and adapted risk measures. Our focus is on risk measures generated by distortion functions. Two new properties are put forward for these: completeness, ensuring that the distortion risk measure uses all the information of the loss distribution, and adaptability, forcing the measure to use this information adequately. This research was partially funded by ^1,3 Welzia Management, SGIIC SA, RD Sistemas SA, Comunidad Autónoma de Madrid Grant s-0505/tic/000230, and MEyC Grant BEC2000-1388-C04-03 and by ² the Natural Sciences and Engineering Research Council of Canada (NSERC) Grant 36860-06.     

Zwei Algorithmen zur Lösung eines komplexen Reihenfolgeproblems

Zusammenfassung Bei der Ordnung von Input-Output-Matrizen treten Kriterien auf, die wesentlich komplexer sind als die Ordnungsbedingungen bei klassischen Reihenfolgeproblemen (z. B.Traveling-Salesman-Problem). Ausgehend von den Arbeiten vonHelmstädter werden im folgenden die mathematische Formulierung eines solchen Reihenfolgeproblems sowie zwei Algorithmen zu dessen Lösung angegeben. Ein Verfahren ist ein lexikographischer Suchalgorithmus, das andere eine Modifikation des bekanntenJacobi-Verfahrens zur Berechnung von EigenwertenHermitescher Matrizen.

---

Summary On the ordering of input-output matrices we use some criteria which are more complex than the order conditions of classical sequencing problems (e. g.Traveling-Salesman-Problem). Basing on the papers ofHelmstädter we will give a mathematical formulation of this sequencing problem and two algorithms solving them. One procedure is a lexicographic searching algorithm, the other one a modification of the well knownJacobi-method which calculates the eigenvalues ofHermiteian matrices.

---

---

Ein Teil dieser Arbeit wurde als Referat auf der Jahrestagung der Deutschen Gesellschaft für Unternehmensforschung (DGU) am 23. September 1968 in Dortmund vorgetragen.

---

Vorgel. v.:W. Krelle.     

On a characterization of convexity-preserving maps, Davidon’s collinear scalings and Karmarkar’s projective transformations

In a recent paper, the authors have proved results characterizing convexity-preserving maps defined on a subset of a not-necessarily finite dimensional real vector space as projective maps. The purpose of this note is three-fold. First, we state a theorem characterizing continuous, injective, convexity-preserving maps from a relatively open, connected subset of an affine subspace of ℝ ^m into ℝ ⁿ as projective maps. This result follows from the more general results stated and proved in a coordinate-free manner in the above paper, and is intended to be more accessible to researchers interested in optimization algorithms. Second, based on that characterization theorem, we offer a characterization theorem for collinear scalings first introduced by Davidon in 1977 for deriving certain algorithms for nonlinear optimization, and a characterization theorem for projective transformations used by Karmarkar in 1984 in his linear programming algorithm. These latter two theorems indicate that Davidon’s collinear scalings and Karmarkar’s projective transformations are the only continuous, injective, convexity-preserving maps possessing certain features that Davidon and Karmarkar respectively desired in the derivation of their algorithms. The proofs of these latter two theorems utilize our characterization of continuous, injective, convexity-preserving maps in a way that has implications to the choice of scalings and transformations in the derivation of optimization algorithms in general. The third purpose of this note is to point this out. Received: January 2000 / Accepted: November 2000?Published online January 17, 2001     

On the stability of the $L_2$ projection in fractional Sobolev spaces

Summary.   In this paper we prove the stability of the projection onto the finite element trial space of piecewise polynomial, in particular, piecewise linear basis functions in for . We formulate explicit and computable local mesh conditions to be satisfied which depend on the Sobolev index s. In conclusion we prove a stability condition needed in the numerical analysis of mixed and hybrid boundary element methods as well as in the construction of efficient preconditioners in adaptive boundary and finite element methods. Received October 14, 1999 / Revised version received March 24, 2000 / Published online October 16, 2000     

On the parameterized complexity of short computation and factorization

A completeness theory for parameterized computational complexity has been studied in a series of recent papers, and has been shown to have many applications in diverse problem domains including familiar graph-theoretic problems, VLSI layout, games, computational biology, cryptography, and computational learning [ADF,BDHW,BFH, DEF,DF1-7,FHW,FK]. We here study the parameterized complexity of two kinds of problems: (1) problems concerning parameterized computations of Turing machines, such as determining whether a nondeterministic machine can reach an accept state in steps (the Short TM Computation Problem), and (2) problems concerning derivations and factorizations, such as determining whether a word can be derived in a grammar in steps, or whether a permutation has a factorization of length over a given set of generators. We show hardness and completeness for these problems for various levels of the hierarchy. In particular, we show that Short TM Computation is complete for . This gives a new and useful characterization of the most important of the apparently intractable parameterized complexity classes. Received August 1, 1994