Showing 1–11 of 11 results for author: Reisner, S

Solving Edge Clique Cover Exactly via Synergistic Data Reduction

Authors: Anthony Hevia, Benjamin Kallus, Summer McClintic, Samantha Reisner, Darren Strash, Johnathan Wilson

Abstract: The edge clique cover (ECC) problem -- where the goal is to find a minimum cardinality set of cliques that cover all the edges of a graph -- is a classic NP-hard problem that has received much attention from both the theoretical and experimental algorithms communities. While small sparse graphs can be solved exactly via the branch-and-reduce algorithm of Gramm et al. [JEA 2009], larger instances c… ▽ More The edge clique cover (ECC) problem -- where the goal is to find a minimum cardinality set of cliques that cover all the edges of a graph -- is a classic NP-hard problem that has received much attention from both the theoretical and experimental algorithms communities. While small sparse graphs can be solved exactly via the branch-and-reduce algorithm of Gramm et al. [JEA 2009], larger instances can currently only be solved inexactly using heuristics with unknown overall solution quality. We revisit computing minimum ECCs exactly in practice by combining data reduction for both the ECC \emph{and} vertex clique cover (VCC) problems. We do so by modifying the polynomial-time reduction of Kou et al. [Commun. ACM 1978] to transform a reduced ECC instance to a VCC instance; alternatively, we show it is possible to ``lift'' some VCC reductions to the ECC problem. Our experiments show that combining data reduction for both problems (which we call \emph{synergistic data reduction}) enables finding exact minimum ECCs orders of magnitude faster than the technique of Gramm et al., and allows solving large sparse graphs on up to millions of vertices and edges that have never before been solved. With these new exact solutions, we evaluate the quality of recent heuristic algorithms on large instances for the first time. The most recent of these, \textsf{EO-ECC} by Abdullah et al. [ICCS 2022], solves 8 of the 27 instances for which we have exact solutions. It is our hope that our strategy rallies researchers to seek improved algorithms for the ECC problem. △ Less

Submitted 4 July, 2023; v1 submitted 30 June, 2023; originally announced June 2023.

Comments: 22 pages, 5 figures, 6 tables, accepted at the 31st Annual European Symposium on Algorithms (ESA 2023)

ACM Class: F.2.2; G.2.2

Ellipsoids are the only local maximizers of the volume product

Authors: Mathieu Meyer, Shlomo Reisner

Abstract: Using previous results about shadow systems and Steiner symmetrization, we prove that the local maximizers of the volume product of convex bodies are actually the global maximizers, that is: ellipsoids. Using previous results about shadow systems and Steiner symmetrization, we prove that the local maximizers of the volume product of convex bodies are actually the global maximizers, that is: ellipsoids. △ Less

Submitted 30 December, 2018; originally announced December 2018.

Comments: accepted to 'Mathematika'

Journal ref: Mathematika 65 (2019) 500-504

The isotropy constant and boundary properties of convex bodies

Authors: Mathieu Meyer, Shlomo Reisner

Abstract: Let ${\cal K}^n$ be the set of all convex bodies in $\mathbb R^n$ endowed with the Hausdorff distance. We prove that if $K\in {\cal K}^n$ has positive generalized Gauss curvature at some point of its boundary, then $K$ is not a local maximizer for the isotropy constant $L_K$. Let ${\cal K}^n$ be the set of all convex bodies in $\mathbb R^n$ endowed with the Hausdorff distance. We prove that if $K\in {\cal K}^n$ has positive generalized Gauss curvature at some point of its boundary, then $K$ is not a local maximizer for the isotropy constant $L_K$. △ Less

Submitted 20 December, 2015; v1 submitted 8 December, 2015; originally announced December 2015.

MSC Class: 46B20; 52A20; 53A05

Volume product of planar polar convex bodies --- lower estimates with stability

Authors: K. J. Böröczky, E. Makai Jr., M. Meyer, S. Reisner

Abstract: Let $K \subset {\mathbb R}^2$ be an $o$-symmetric convex body, and $K^*$ its polar body. Then we have $|K|\cdot |K^*| \ge 8$, with equality if and only if $K$ is a parallelogram. ($| \cdot |$ denotes volume). If $K \subset {\mathbb R}^2$ is a convex body, with $o \in {\text{int}}\,K$, then $|K|\cdot |K^*| \ge 27/4$, with equality if and only if $K$ is a triangle and $o$ is its centroid. If… ▽ More Let $K \subset {\mathbb R}^2$ be an $o$-symmetric convex body, and $K^*$ its polar body. Then we have $|K|\cdot |K^*| \ge 8$, with equality if and only if $K$ is a parallelogram. ($| \cdot |$ denotes volume). If $K \subset {\mathbb R}^2$ is a convex body, with $o \in {\text{int}}\,K$, then $|K|\cdot |K^*| \ge 27/4$, with equality if and only if $K$ is a triangle and $o$ is its centroid. If $K \subset {\mathbb R}^2$ is a convex body, then we have $|K| \cdot |[(K-K)/2)]^* | \ge 6$, with equality if and only if $K$ is a triangle. These theorems are due to Mahler and Reisner, Mahler and Meyer, and to Eggleston, respectively. We show an analogous theorem: if $K$ has $n$-fold rotational symmetry about $o$, then $|K|\cdot |K^*| \ge n^2 \sin ^2 ( π/n)$, with equality if and only if $K$ is a regular $n$-gon of centre $o$. We will also give stability variants of these four inequalities, both for the body, and for the centre of polarity. For this we use the Banach-Mazur distance (from parallelograms, or triangles), or its analogue with similar copies rather than affine transforms (from regular $n$-gons), respectively. The stability variants are sharp, up to constant factors. We extend the inequality $|K|\cdot |K^*| \ge n^2 \sin ^2 ( π/n)$ to bodies with $o \in {\text{int}}\,K$, which contain, and are contained in, two regular $n$-gons, the vertices of the contained $n$-gon being incident to the sides of the containing $n$-gon. Our key lemma is a stability estimate for the area product of two sectors of convex bodies polar to each other. To several of our statements we give several proofs; in particular, we give a new proof for the theorem of Mahler-Reisner. △ Less

Submitted 6 July, 2015; originally announced July 2015.

Comments: 49 TEX pages

MSC Class: 52A40

Journal ref: Stud. Sci. Math. Hungar. 50 (2) (2013), 159-198

A note on Mahler's conjecture

Authors: Shlomo Reisner, Carsten Schütt, Elisabeth M. Werner

Abstract: Let $K$ be a convex body in $\mathbb{R}^n$ with Santaló point at 0\. We show that if $K$ has a point on the boundary with positive generalized Gauß curvature, then the volume product $|K| |K^\circ|$ is not minimal. This means that a body with minimal volume product has Gauß curvature equal to 0 almost everywhere and thus suggests strongly that a minimal body is a polytope. Let $K$ be a convex body in $\mathbb{R}^n$ with Santaló point at 0\. We show that if $K$ has a point on the boundary with positive generalized Gauß curvature, then the volume product $|K| |K^\circ|$ is not minimal. This means that a body with minimal volume product has Gauß curvature equal to 0 almost everywhere and thus suggests strongly that a minimal body is a polytope. △ Less

Submitted 18 September, 2010; originally announced September 2010.

MSC Class: 52A20

The GL-l.u.st.\ constant and asymmetry of the Kalton-Peck twisted sum in finite dimensions

Authors: Y. Gordon, M. Junge, M. Meyer, S. Reisner

Abstract: We prove that the Kalton-Peck twisted sum $Z_2^n$ of $n$-dimensional Hilbert spaces has GL-l.u.st.\ constant of order $\log n$ and bounded GL constant. This is the first concrete example which shows different explicit orders of growth in the GL and GL-l.u.st.\ constants. We discuss also the asymmetry constants of $Z_2^n$. We prove that the Kalton-Peck twisted sum $Z_2^n$ of $n$-dimensional Hilbert spaces has GL-l.u.st.\ constant of order $\log n$ and bounded GL constant. This is the first concrete example which shows different explicit orders of growth in the GL and GL-l.u.st.\ constants. We discuss also the asymmetry constants of $Z_2^n$. △ Less

Submitted 27 July, 2010; originally announced July 2010.

Local minimality of the volume-product at the simplex

Authors: Jaegil Kim, Shlomo Reisner

Abstract: It is proved that the simplex is a strict local minimum for the volume product, P(K)=min(vol(K) vol(K^z)), K^z is the polar body of K with respect to z, the minimum is taken over z in the interior of K, in the Banach-Mazur space of n-dimensional (classes of ) convex bodies. Linear local stability in the neighborhood of the simplex is proved as well. The proof consists of an extension to the non-sy… ▽ More It is proved that the simplex is a strict local minimum for the volume product, P(K)=min(vol(K) vol(K^z)), K^z is the polar body of K with respect to z, the minimum is taken over z in the interior of K, in the Banach-Mazur space of n-dimensional (classes of ) convex bodies. Linear local stability in the neighborhood of the simplex is proved as well. The proof consists of an extension to the non-symmetric setting of methods that were recently introduced by Nazarov, Petrov, Ryabogin and Zvavitch, as well as proving results of independent interest, concerning stability of square order of volumes of polars of non-symmetric convex bodies. △ Less

Submitted 31 August, 2010; v1 submitted 1 January, 2010; originally announced January 2010.

Comments: Mathematika, accepted

MSC Class: 52A40

A note on equipartition

Authors: M. A. Lopez, S. Reisner

Abstract: The problem of the existence of an equi-partition of a curve in $\R^n$ has recently been raised in the context of computational geometry. The problem is to show that for a (continuous) curve $Γ: [0,1] \to \R^n$ and for any positive integer N, there exist points $t_0=0<t_1<...<t_{N-1}<1=t_N$, such that $d(Γ(t_{i-1}),Γ(t_i))=d(Γ(t_{i}),Γ(t_{i+1}))$ for all $i=1,...,N$, where d is a metric or even… ▽ More The problem of the existence of an equi-partition of a curve in $\R^n$ has recently been raised in the context of computational geometry. The problem is to show that for a (continuous) curve $Γ: [0,1] \to \R^n$ and for any positive integer N, there exist points $t_0=0<t_1<...<t_{N-1}<1=t_N$, such that $d(Γ(t_{i-1}),Γ(t_i))=d(Γ(t_{i}),Γ(t_{i+1}))$ for all $i=1,...,N$, where d is a metric or even a semi-metric (a weaker notion) on $\R^n$. We show here that the existence of such points, in a broader context, is a consequence of Brower's fixed point theorem. △ Less

Submitted 15 July, 2008; v1 submitted 29 July, 2007; originally announced July 2007.

Comments: Some misprints in earlier versions are corrected, one reference is added with remarks concerning it

ACM Class: I.3.5

Shadow systems and volume of polar convex bodies

Authors: Mathieu Meyer, Shlomo Reisner

Abstract: We prove that the reciprocal of the volume of the polar bodies, about the Santaló point, of a {\em shadow system} of convex bodies $K_t$, is a convex function of $t$. Thus extending to the non-symmetric case a result of Campi and Gronchi. The case that the reciprocal of the volume is an affine function of $t$ is also investigated and is characterized under certain conditions. We apply these re… ▽ More We prove that the reciprocal of the volume of the polar bodies, about the Santaló point, of a {\em shadow system} of convex bodies $K_t$, is a convex function of $t$. Thus extending to the non-symmetric case a result of Campi and Gronchi. The case that the reciprocal of the volume is an affine function of $t$ is also investigated and is characterized under certain conditions. We apply these results to prove exact reverse Santaló inequality for polytopes in $\rd{d}$ that have at most $d+3$ vertices. △ Less

Submitted 14 July, 2008; v1 submitted 13 June, 2006; originally announced June 2006.

Comments: Mathematika 53 (2006), 129-148, here are some corrections of misprints

Umbrellas and polytopal approximation of the euclidean ball

Authors: Yehoram Gordon, Shlomo Reisner, Carsten Schütt

Abstract: There are two positive, absolute constants $c_{1}$ and $c_{2}$ so that the volume of the difference set of the $d$-dimensional Euclidean ball and an inscribed polytope with n vertices is larger than $$ c_{2}\ d\ {n}^{-\frac{2}{d-1}}vol_d(B^d_2) $$ for $n \geq (c_{1}\ d)^{\frac{d-1}{2}}$. There are two positive, absolute constants $c_{1}$ and $c_{2}$ so that the volume of the difference set of the $d$-dimensional Euclidean ball and an inscribed polytope with n vertices is larger than $$ c_{2}\ d\ {n}^{-\frac{2}{d-1}}vol_d(B^d_2) $$ for $n \geq (c_{1}\ d)^{\frac{d-1}{2}}$. △ Less

Submitted 17 March, 1996; originally announced March 1996.

Report number: Banach Archive 3/18/96 MSC Class: 52A

The volume of the intersection of a convex body with its translates

Authors: Mathieu Meyer, Shlomo Reisner, M. Schmuckenschlager

Abstract: It is proved that for a symmetric convex body K in R^n, if for some tau > 0, |K cap (x+tau K)| depends on ||x||_K only, then K is an ellipsoid. As a part of the proof, smoothness properties of convolution bodies ls are studied. It is proved that for a symmetric convex body K in R^n, if for some tau > 0, |K cap (x+tau K)| depends on ||x||_K only, then K is an ellipsoid. As a part of the proof, smoothness properties of convolution bodies ls are studied. △ Less

Submitted 14 April, 1992; originally announced April 1992.

Report number: Banach Archive 4/14/92