Abstract:
Unfolding a convex polyhedron into a simple planar polygon is a well-studied problem. In this paper, we study the limits of unfoldability by studying nonconvex polyhedra with the same combinatorial structure as convex polyhedra. In particular, we give two examples of polyhedra, one with 24 convex faces and one with 36 triangular faces, that cannot be unfolded by cutting along edges. We further show that such a polyhedron can indeed be unfolded if cuts are allowed to cross faces. Finally, we prove that ``open'' polyhedra with triangular faces may not be unfoldable no matter how they are cut.

Abstract:
Covering a convex body by its homothets is a classical notion in discrete geometry that has resulted in a number of interesting and long-standing problems. Swanepoel introduced the covering parameter of a convex body as a means of quantifying its covering properties. In this paper, we introduce two relatives of the covering parameter called covering index and weak covering index, which upper bound well-studied quantities like the illumination number, the illumination parameter and the covering parameter of a convex body. Intuitively, the two indices measure how well a convex body can be covered by a relatively small number of homothets having the same relatively small homothety ratio. We show that the covering index is a lower semicontinuous functional on the Banach-Mazur space of convex bodies. We further show that the affine d-cubes minimize covering index in any dimension d, while circular disks maximize it in the plane. Furthermore, the covering index satisfies a nice compatibility with the operations of direct vector sum and vector sum. In fact, we obtain an exact formula for the covering index of a direct vector sum of convex bodies that works in infinitely many instances. This together with a minimization property can be used to determine the covering index of infinitely many convex bodies. As the name suggests, the weak covering index loses some of the important properties of the covering index. Finally, we obtain upper bounds on the covering and weak covering index.

Abstract:
Covering numbers of convex bodies based on homothetical copies and related illumination numbers are well-known in combinatorial geometry and, for example, related to Hadwiger's famous covering problem. Similar numbers can be defined by using proper translates instead of homothets, and even more related concepts make sense. On these lines we introduce some new covering and illumination numbers of convex bodies, present their properties and compare them with each other as well as with already known numbers. Finally, some suggestive examples illustrate that these new illumination numbers are interesting and non-trivial.

Abstract:
In this paper we study the covering numbers of the space of convex and uniformly bounded functions in multi-dimension. We find optimal upper and lower bounds for the $\epsilon$-covering number of $\C([a, b]^d, B)$, in the $L_p$-metric, $1 \le p < \infty$, in terms of the relevant constants, where $d \geq 1$, $a < b \in \mathbb{R}$, $B>0$, and $\C([a,b]^d, B)$ denotes the set of all convex functions on $[a, b]^d$ that are uniformly bounded by $B$. We summarize previously known results on covering numbers for convex functions and also provide alternate proofs of some known results. Our results have direct implications in the study of rates of convergence of empirical minimization procedures as well as optimal convergence rates in the numerous convexity constrained function estimation problems.

Abstract:
We study the online convex covering problem and online convex packing problem. The (offline) convex covering problem is modeled by the following convex program: $\min_{x \in R_+^n} f(x) \ \text{s.t}\ A x \ge 1$, where $f : R_+^n \mapsto R_+$ is a monotone and convex cost function, and $A$ is an $m \times n$ matrix with non-negative entries. Each row of the constraint matrix $A$ corresponds to a covering constraint. In the online problem, each row of $A$ comes online and the algorithm must maintain a feasible assignment $x$ and may only increase $x$ over time. The (offline) convex packing problem is modeled by the following convex program: $\max_{y\in R_+^m} \sum_{j = 1}^m y_j - g(A^T y)$, where $g : R_+^n \mapsto R_+$ is a monotone and convex cost function. It is the Fenchel dual program of convex covering when $g$ is the convex conjugate of $f$. In the online problem, each variable $y_j$ arrives online and the algorithm must decide the value of $y_j$ on its arrival. We propose simple online algorithms for both problems using the online primal dual technique, and obtain nearly optimal competitive ratios for both problems for the important special case of polynomial cost functions. For any convex polynomial cost functions with non-negative coefficients and maximum degree $\tau$, we introduce an $O(\tau \log n)^\tau$-competitive online convex covering algorithm, and an $O(\tau)$-competitive online convex packing algorithm, matching the known $\Omega(\tau \log n)^\tau$ and $\Omega(\tau)$ lower bounds respectively. There is a large family of online resource allocation problems that can be modeled under this online convex covering and packing framework, including online covering and packing problems (with linear objectives), online mixed covering and packing, and online combinatorial auction. Our framework allows us to study these problems using a unified approach.

Abstract:
A subset of the sphere is said short if it is contained in an open hemisphere. A short closed set which is geodesically convex is called a cap. The following theorem holds: 1. The minimal number of short closed sets covering the $n$-sphere is $n+2$. 2. If $n+2$ short closed sets cover the $n$-sphere then (i) their intersection is empty; (ii) the intersection of any proper subfamily of them is non-empty. In the case of caps (i) and (ii) are also sufficient for the family to be a covering of the sphere.

Abstract:
It is proved that if $u_1,\ldots, u_n$ are vectors in ${\Bbb R}^k, k\le n, 1 \le p < \infty$ and $$r = ({1\over k} \sum ^n_1 |u_i|^p)^{1\over p}$$ then the volume of the symmetric convex body whose boundary functionals are $\pm u_1,\ldots, \pm u_n$, is bounded from below as $$|\{ x\in {\Bbb R}^k\colon \ |\langle x,u_i\rangle | \le 1 \ \hbox{for every} \ i\}|^{1\over k} \ge {1\over \sqrt{\rho}r}.$$ An application to number theory is stated.

Abstract:
It is conjectured that for every convex disks K, the translative covering density of K and the lattice covering density of K are identical. It is well known that this conjecture is true for every centrally symmetric convex disks. For the non-symmetric case, we only know that the conjecture is true for triangles. In this paper, we prove the conjecture for a class of convex disks (quarter-convex disks), which includes all triangles and convex quadrilaterals.

Abstract:
We give an algorithmic framework for minimizing general convex objectives (that are differentiable and monotone non-decreasing) over a set of covering constraints that arrive online. This substantially extends previous work on online covering for linear objectives (Alon {\em et al.}, STOC 2003) and online covering with offline packing constraints (Azar {\em et al.}, SODA 2013). To the best of our knowledge, this is the first result in online optimization for generic non-linear objectives; special cases of such objectives have previously been considered, particularly for energy minimization. As a specific problem in this genre, we consider the unrelated machine scheduling problem with startup costs and arbitrary $\ell_p$ norms on machine loads (including the surprisingly non-trivial $\ell_1$ norm representing total machine load). This problem was studied earlier for the makespan norm in both the offline (Khuller~{\em et al.}, SODA 2010; Li and Khuller, SODA 2011) and online settings (Azar {\em et al.}, SODA 2013). We adapt the two-phase approach of obtaining a fractional solution and then rounding it online (used successfully to many linear objectives) to the non-linear objective. The fractional algorithm uses ideas from our general framework that we described above (but does not fit the framework exactly because of non-positive entries in the constraint matrix). The rounding algorithm uses ideas from offline rounding of LPs with non-linear objectives (Azar and Epstein, STOC 2005; Kumar {\em et al.}, FOCS 2005). Our competitive ratio is tight up to a logarithmic factor. Finally, for the important special case of total load ($\ell_1$ norm), we give a different rounding algorithm that obtains a better competitive ratio than the generic rounding algorithm for $\ell_p$ norms. We show that this competitive ratio is asymptotically tight.

Abstract:
For n greater than or equal to 4, the square of the volume of an n-simplex satisfies a polynomial relation with coefficients depending on the squares of the areas of 2-faces of this simplex. First, we compute the minimal degree of such polynomial relation. Second, we prove that the volume an n-simplex satisfies a monic polynomial relation with coefficients depending on the areas of 2-faces of this simplex if and only if n is even and at least 6, and we study the leading coefficients of polynomial relations satisfied by the volume for other n.