Optimale Quantisierung

Zusammenfassung. Optimale Quantisierungen oder – damit ?quivalent – minimale Summen von Momenten spielen in mehreren Zweigen der Mathematik und ihrer Anwendungen eine Rolle. Ausgehend von der Fejes Tóth'schen Ungleichung für Summen von Momenten in der euklidischen Ebene und einem zugeh?rigen Stabilit?tssatz, werden gewisse Erweiterungen auf normierte R?ume und riemannsche Mannigfaltigkeiten h?herer Dimension besprochen. Die Ergebnisse werden dann auf Probleme aus folgenden Bereichen angewendet: (i) Datenübertragung, (ii) Wahrscheinlichkeitstheorie, (iii) numerische Integration, (iv) Approximation konvexer K?rper und (v) isoperimetrische Probleme. Eingegangen am 29. Mai 2002 / Angenommen am 8. Juli 2002     

Euler–MacLaurin formulas via differential operators

Recently there has been a renewed interest in asymptotic Euler–MacLaurin formulas, because of their applications to spectral theory of differential operators. Using elementary means, we recover such formulas for compactly supported smooth functions on intervals, polygons, and three-dimensional polytopes, where the coefficients in the asymptotic expansion are sums of differential operators involving only derivatives of the function in directions normal to the faces of the polytope. Our formulas apply to wedges of any dimension.     

Composition of stable set polyhedra

Barahona and Mahjoub found a defining system of the stable set polytope for a graph with a cut-set of cardinality 2. We extend this result to cut-sets composed of a complete graph minus an edge and use the new theorem to derive a class of facets.     

Geometric characterizations of centroids of simplices

We study the centroid of a simplex in space. Primary attention is paid to the relationships among the centroids of the different k-skeletons of a simplex in n-dimensional space. We prove that the 0-dimensional skeleton and the n-dimensional skeleton always have the same centroid. The centroids of the other skeleta are generically different (as we prove), but there are remarkable instances where they coincide in pairs. They never coincide in triples for regular pyramids.     

多面体截面和小覆盖的闭子流形

设π:M~n→P~n是P~n上的小覆盖,S是P~n的任意一个n-1维截面.给出了π~(-1)(S)是n-1维闭子流形(或者两个相互同胚n-1维闭子流形的不交并),以及π~(-1)(S)是n-1维伪流形的充要条件.     

Note on the computational complexity ofj-radii of polytopes in ℝ n

We show that, for fixed dimensionn, the approximation of inner and outerj-radii of polytopes in ℝ ⁿ , endowed with the Euclidean norm, is in ℙ. Our method is based on the standard polynomial time algorithms for solving a system of polynomial inequalities over the reals in fixed dimension.     

Facets of the independent path-matching polytope

Cunningham and Geelen introduced the independent path-matching problem as a common generalization of the weighted matching problem and the weighted matroid intersection problem. Associated with an independent path-matching is an independent path-matching vector. The independent path-matching polytope of an instance of the independent path-matching problem is the convex hull of all the independent path-matching vectors. Cunningham and Geelen described a system of linear inequalities defining the independent path-matching polytope. In this paper, we characterize which inequalities in this system induce facets of the independent path-matching polytope, generalizing previous results on the matching polytope and the common independent set polytope.     

Characterization of rankings generated by linear discriminant analysis

Pairwise linear discriminant analysis can be regarded as a process to generate rankings of the populations. But in general, not all rankings are generated. We give a characterization of generated rankings. We also derive some basic properties of this model.     

On the Hardness of Computing Intersection,Union and Minkowski Sum of Polytopes

For polytopes P ₁,P ₂⊂ℝ ^d , we consider the intersection P ₁∩P ₂, the convex hull of the union CH(P ₁∪P ₂), and the Minkowski sum P ₁+P ₂. For the Minkowski sum, we prove that enumerating the facets of P ₁+P ₂ is NP-hard if P ₁ and P ₂ are specified by facets, or if P ₁ is specified by vertices and P ₂ is a polyhedral cone specified by facets. For the intersection, we prove that computing the facets or the vertices of the intersection of two polytopes is NP-hard if one of them is given by vertices and the other by facets. Also, computing the vertices of the intersection of two polytopes given by vertices is shown to be NP-hard. Analogous results for computing the convex hull of the union of two polytopes follow from polar duality. All of the hardness results are established by showing that the appropriate decision version, for each of these problems, is NP-complete.