Search

In light of the log-Brunn-Minkowski conjecture, various attempts have been made to define the geometric mean of convex bodies. Many of these constructions are fairly complex and/or fail to satisfy some natural properties one would expect of such a mean. We remedy this by providing a new geometric mean that is both technically simple and inherits all the natural properties expected. To improve our understanding of potential geometric mean definitions, we first study general $p$-means of convex bodies, with the usual definition extended to two series ranging over all $p$ in the extended reals. We characterize their equality cases and obtain (in almost all instances tight) inequalities that quantify how well these means approximate each other. As a corollary, we establish that every Minkowski centered body is equidistant from all its $p$-symmetrizations with respect to the Banach-Mazur distance. Finally, we show that our geometric mean satisfies all the properties considered in recent literature and extend this list with some properties regarding symmetrization and asymmetry., Comment: 31 pages, 4 figures

We study geometric inequalities for the circumradius and diameter with respect to general gauges, partly also involving the inradius and the Minkowski asymmetry. There are a number of options for defining the diameter of a convex body that fall apart when we consider non-symmetric gauges. These definitions correspond to different symmetrizations of the gauge, i.e. means of the gauge $C$ and its origin reflection $-C$.

In network flow problems, there is a well-known one-to-one relationship between extreme points of the feasibility region and trees in the associated undirected graph. The same is true for the dual differential problem. In this paper, we study problems where the constraints of both problems appear simultaneously, a variant which is motivated by an application in the expansion planning of energy networks. We show that all extreme points still directly correspond to graph-theoretical structures in the underlying network. The reverse is generally also true in all but certain exceptional cases. We furthermore characterize graphs in which these exceptional cases never occur and present additional criteria for when those cases do not occur due to parameter values.

For a Minkowski centered convex compact set $K$ we define $\alpha(K)$ to be the smallest possible factor to cover $K \cap (-K)$ by a rescalation of $\mathrm{conv} (K\cup (-K))$ and give a complete description of the possible values of $\alpha(K)$ in the planar case in dependence of the Minkowski asymmetry of $K$. As a side product, we show that, if the asymmetry of $K$ is greater than the golden ratio, the boundary of $K$ intersects the boundary of its negative $-K$ always in exactly 6 points. As an application, we derive bounds for the diameter-width-ratio for pseudo-complete and complete sets, again in dependence of the Minkowski asymmetry of the convex bodies, tightening those depending solely on the dimension given in a recent result of Richter [10].

This paper deals with four symmetrizations of a convex set $C$: the intersection, the harmonic and the arithmetic mean, and the convex hull of $C$ and $-C$. A well-known result of Firey shows that those means build up a subset-chain in the given order. On the one hand, we determine the dilatation factors, depending on the asymmetry of $C$, to reverse the containments between any of those symmetrizations. On the other hand, we tighten the relations proven by Firey and show a stability result concerning those factors near the simplex.

We provide a study of Blaschke-Santal\'o diagrams for the inradius, diameter, and circumradius, measured with respect to different gauges. This contrasts previous works on those diagrams, which are all considered for euclidean measure. By proving several new inequalities and properties between these three functionals, we compute the intersection and the union over all possible gauges of those diagrams, showing that they coincide with the corresponding diagrams of a parallelotope and (in the planar case) a triangle, respectively. Further new extremal properties are derived considering the diagrams with respect to a regular pentagon or hexagon gauge., Comment: 19 pages

We show that for any Minkowski centered planar convex compact set $C$ the Harmonic mean of $C$ and $-C$ can be optimally contained in the arithmetic mean of the same sets if and only if the Minkowski asymmetry of $C$ is at most the golden ratio $(1+\sqrt{5})/2 \approx 1.618$. Moreover, the most asymmetric such set that is (up to a linear transformation) a special pentagon, which we call the golden house.

In this paper, we present a new perspective on cut generation in the context of Benders decomposition. The approach, which is based on the relation between the alternative polyhedron and the reverse polar set, helps us to improve established cut selection procedures for Benders cuts, like the one suggested by Fischetti, Salvagnin, and Zanette [FSZ10]. Our modified version of that criterion produces cuts which are always supporting and, unless in rare special cases, facet-defining. We discuss our approach in relation to the state of the art in cut generation for Benders decomposition. In particular, we refer to Pareto-optimality and facet-defining cuts and observe that each of these criteria can be matched to a particular subset of parameterizations for our cut generation framework. As a consequence, our framework includes the method to generate facet-defining cuts proposed by Conforti and Wolsey [CW18] as a special case.

This paper considers the radii functionals (circumradius, inradius, and diameter) as well as the Minkowski asymmetry for general (possibly non-symmetric) gauge bodies. A generalization of the concentricity inequality (which states that the sum of the inradius and circumradius is not greater than the diameter in general Minkowski spaces) for non-symmetric gauge bodies is derived and a strong connection between this new inequality, extremal sets of the generalized Bohnenblust inequality, and completeness of simplices is revealed.

Is it true that a convex body $K$ being complete and reduced with respect to some gauge body $C$ is necessarily of constant width, that is, satisfies $K-K=\rho(C-C)$ for some $\rho>0$? We prove this implication for several cases including the following: if $K$ is a simplex and or if $K$ possesses a smooth extreme point, then the implication holds. Moreover, we derive several new results on perfect norms., Comment: 12 pages

We consider the sum of the incurred start-up costs of a single unit in a Unit Commitment problem. Our major result is a correspondence between the facets of its epigraph and some binary trees for concave start-up cost functions CU, which is bijective if CU is strictly concave. We derive an exponential H-representation of this epigraph, and provide an exact linear separation algorithm. These results significantly reduce the integrality gap of the Mixed Integer formulation of a Unit Commitment Problem compared to current literature., Comment: 28 pages, preprint

In this paper we state a one-to-one connection between the maximal ratio of the circumradius and the diameter of a body (the Jung constant) in an arbitrary Minkowski space and the maximal Minkowski asymmetry of the complete bodies within that space. This allows to generalize and unify recent results on complete bodies and to derive a necessary condition on the unit ball of the space, assuming a given body to be complete. Finally, we state several corollaries, i.e. concerning the Helly dimension or the Banach-Mazur distance.

Starting from a basic Unit Commitment problem as published in [Carri\'on2006], we develop a fully functional, running implementation for Xpress Mosel, useable in power market modeling. The constraints of the model are discussed in details and solutions to left open implementation problems are presented, guidelines on how to handle data input (from both, databases and Excel), as well as data output (to Excel) are given., Comment: 37 pages, 1 figure

This paper presents an improved mixed-integer model for the Thermal Unit Commitment Problem. By introducing new variables for the temperature of each thermal unit, the off-time-dependent start-up costs are modeled accurately and with a lower integrality gap than state-of-the-art formulations. This new approach significantly improves computational efficiency compared to existing formulations, even if they only model a rough approximation of the start-up costs. Our findings were validated on real-world test cases using CPLEX., Comment: 9 pages, 5 figures, 1 table, data sets

We present a complete 3-dimensional Blaschke-Santal\'o diagram for planar convex bodies with respect to the four classical magnitudes inner and outer radius, diameter and (minimal) width in euclidean spaces.

Many classical geometric inequalities on functionals of convex bodies depend on the dimension of the ambient space. We show that this dimension dependence may often be replaced (totally or partially) by different symmetry measures of the convex body. Since these coefficients are bounded by the dimension but possibly smaller, our inequalities sharpen the original ones. Since they can often be computed efficiently, the improved bounds may also be used to obtain better bounds in approximation algorithms., Comment: This is a preprint. The proper publication in final form is available at journals.cambridge.org, DOI 10.1112/S0025579314000291

This paper deals with the containment problem under homothetics which has the minimal enclosing ball (MEB) problem as a prominent representative. We connect the problem to results in classic convex geometry and introduce a new series of radii, which we call core-radii. For the MEB problem, these radii have already been considered from a different point of view and sharp inequalities between them are known. In this paper sharp inequalities between core-radii for general containment under homothetics are obtained. Moreover, the presented inequalities are used to derive sharp upper bounds on the size of core-sets for containment under homothetics. In the MEB case, this yields a tight (dimension independent) bound for the size of such core-sets. In the general case, we show that there are core-sets of size linear in the dimension and that this bound stays sharp even if the container is required to be symmetric., Comment: Discrete & Computational Geometry, 2012; The final publication is available at http://www.springerlink.com

We provide a characterization of the radii minimal projections of polytopes onto $j$-dimensional subspaces in Euclidean space $\E^n$. Applied on simplices this characterization allows to reduce the computation of an outer radius to a computation in the circumscribing case or to the computation of an outer radius of a lower-dimensional simplex. In the second part of the paper, we use this characterization to determine the sequence of outer $(n-1)$-radii of regular simplices (which are the radii of smallest enclosing cylinders). This settles a question which arose from the incidence that a paper by Wei{\ss}bach (1983) on this determination was erroneous. In the proof, we first reduce the problem to a constrained optimization problem of symmetric polynomials and then to an optimization problem in a fixed number of variables with additional integer constraints., Comment: Minor revisions. To appear in Advances in Geometry

This paper deals with the three types of regular polytopes which exist in all dimensions -- regular simplices, cubes and regular cross-polytopes -- and their outer and inner radii. While the inner radii of regular simplices are well studied, only a few cases are solved for the outer radii. We give a lower bound on these radii, and show that this bound is tight in almost 3 out of 4 dimensions. In a further section we complete the results about inner and outer radii of general boxes and cross-polytopes. Finally, because cubes and regular cross-polytopes are radii-minimal projections of simplices, we show that it is possible to deduce the results about their radii from the results about the outer radii of simplices., Comment: 12 pages