Consider two halfspaces
A classical parking function of length
 NSFPAR ID:
 10472917
 Publisher / Repository:
 Springer Science + Business Media
 Date Published:
 Journal Name:
 Annals of Combinatorics
 Volume:
 28
 Issue:
 2
 ISSN:
 02180006
 Format(s):
 Medium: X Size: p. 575613
 Size(s):
 ["p. 575613"]
 Sponsoring Org:
 National Science Foundation
More Like this

Abstract and$$H_1^+$$ ${H}_{1}^{+}$ in$$H_2^+$$ ${H}_{2}^{+}$ whose bounding hyperplanes$${\mathbb {R}}^{d+1}$$ ${R}^{d+1}$ and$$H_1$$ ${H}_{1}$ are orthogonal and pass through the origin. The intersection$$H_2$$ ${H}_{2}$ is a spherical convex subset of the$${\mathbb {S}}_{2,+}^d:={\mathbb {S}}^d\cap H_1^+\cap H_2^+$$ ${S}_{2,+}^{d}:={S}^{d}\cap {H}_{1}^{+}\cap {H}_{2}^{+}$d dimensional unit sphere , which contains a great subsphere of dimension$${\mathbb {S}}^d$$ ${S}^{d}$ and is called a spherical wedge. Choose$$d2$$ $d2$n independent random points uniformly at random on and consider the expected facet number of the spherical convex hull of these points. It is shown that, up to terms of lower order, this expectation grows like a constant multiple of$${\mathbb {S}}_{2,+}^d$$ ${S}_{2,+}^{d}$ . A similar behaviour is obtained for the expected facet number of a homogeneous Poisson point process on$$\log n$$ $logn$ . The result is compared to the corresponding behaviour of classical Euclidean random polytopes and of spherical random polytopes on a halfsphere.$${\mathbb {S}}_{2,+}^d$$ ${S}_{2,+}^{d}$ 
Abstract Approximate integer programming is the following: For a given convex body
, either determine whether$$K \subseteq {\mathbb {R}}^n$$ $K\subseteq {R}^{n}$ is empty, or find an integer point in the convex body$$K \cap {\mathbb {Z}}^n$$ $K\cap {Z}^{n}$ which is$$2\cdot (K  c) +c$$ $2\xb7(Kc)+c$K , scaled by 2 from its center of gravityc . Approximate integer programming can be solved in time while the fastest known methods for exact integer programming run in time$$2^{O(n)}$$ ${2}^{O\left(n\right)}$ . So far, there are no efficient methods for integer programming known that are based on approximate integer programming. Our main contribution are two such methods, each yielding novel complexity results. First, we show that an integer point$$2^{O(n)} \cdot n^n$$ ${2}^{O\left(n\right)}\xb7{n}^{n}$ can be found in time$$x^* \in (K \cap {\mathbb {Z}}^n)$$ ${x}^{\ast}\in (K\cap {Z}^{n})$ , provided that the$$2^{O(n)}$$ ${2}^{O\left(n\right)}$remainders of each component for some arbitrarily fixed$$x_i^* \mod \ell $$ ${x}_{i}^{\ast}\phantom{\rule{0ex}{0ex}}mod\phantom{\rule{0ex}{0ex}}\ell $ of$$\ell \ge 5(n+1)$$ $\ell \ge 5(n+1)$ are given. The algorithm is based on a$$x^*$$ ${x}^{\ast}$cuttingplane technique , iteratively halving the volume of the feasible set. The cutting planes are determined via approximate integer programming. Enumeration of the possible remainders gives a algorithm for general integer programming. This matches the current best bound of an algorithm by Dadush (Integer programming, lattice algorithms, and deterministic, vol. Estimation. Georgia Institute of Technology, Atlanta, 2012) that is considerably more involved. Our algorithm also relies on a new$$2^{O(n)}n^n$$ ${2}^{O\left(n\right)}{n}^{n}$asymmetric approximate Carathéodory theorem that might be of interest on its own. Our second method concerns integer programming problems in equationstandard form . Such a problem can be reduced to the solution of$$Ax = b, 0 \le x \le u, \, x \in {\mathbb {Z}}^n$$ $Ax=b,0\le x\le u,\phantom{\rule{0ex}{0ex}}x\in {Z}^{n}$ approximate integer programming problems. This implies, for example that$$\prod _i O(\log u_i +1)$$ ${\prod}_{i}O(log{u}_{i}+1)$knapsack orsubsetsum problems withpolynomial variable range can be solved in time$$0 \le x_i \le p(n)$$ $0\le {x}_{i}\le p\left(n\right)$ . For these problems, the best running time so far was$$(\log n)^{O(n)}$$ ${(logn)}^{O\left(n\right)}$ .$$n^n \cdot 2^{O(n)}$$ ${n}^{n}\xb7{2}^{O\left(n\right)}$ 
Abstract We introduce tools from discrete convexity theory and polyhedral geometry into the theory of West’s stacksorting map
s . Associated to each permutation is a particular set$$\pi $$ $\pi $ of integer compositions that appears in a formula for the fertility of$$\mathcal V(\pi )$$ $V\left(\pi \right)$ , which is defined to be$$\pi $$ $\pi $ . These compositions also feature prominently in more general formulas involving families of colored binary plane trees called$$s^{1}(\pi )$$ ${s}^{1}\left(\pi \right)$troupes and in a formula that converts from free to classical cumulants in noncommutative probability theory. We show that is a transversal discrete polymatroid when it is nonempty. We define the$$\mathcal V(\pi )$$ $V\left(\pi \right)$fertilitope of to be the convex hull of$$\pi $$ $\pi $ , and we prove a surprisingly simple characterization of fertilitopes as nestohedra arising from full binary plane trees. Using known facts about nestohedra, we provide a procedure for describing the structure of the fertilitope of$$\mathcal V(\pi )$$ $V\left(\pi \right)$ directly from$$\pi $$ $\pi $ using BousquetMélou’s notion of the canonical tree of$$\pi $$ $\pi $ . As a byproduct, we obtain a new combinatorial cumulant conversion formula in terms of generalizations of canonical trees that we call$$\pi $$ $\pi $quasicanonical trees . We also apply our results on fertilitopes to study combinatorial properties of the stacksorting map. In particular, we show that the set of fertility numbers has density 1, and we determine all infertility numbers of size at most 126. Finally, we reformulate the conjecture that is always realrooted in terms of nestohedra, and we propose natural ways in which this new version of the conjecture could be extended.$$\sum _{\sigma \in s^{1}(\pi )}x^{\textrm{des}(\sigma )+1}$$ ${\sum}_{\sigma \in {s}^{1}\left(\pi \right)}{x}^{\text{des}\left(\sigma \right)+1}$ 
Abstract For polyhedral constrained optimization problems and a feasible point
, it is shown that the projection of the negative gradient on the tangent cone, denoted$$\textbf{x}$$ $x$ , has an orthogonal decomposition of the form$$\nabla _\varOmega f(\textbf{x})$$ ${\nabla}_{\Omega}f\left(x\right)$ . At a stationary point,$$\varvec{\beta }(\textbf{x}) + \varvec{\varphi }(\textbf{x})$$ $\beta \left(x\right)+\phi \left(x\right)$ so$$\nabla _\varOmega f(\textbf{x}) = \textbf{0}$$ ${\nabla}_{\Omega}f\left(x\right)=0$ reflects the distance to a stationary point. Away from a stationary point,$$\Vert \nabla _\varOmega f(\textbf{x})\Vert $$ $\Vert {\nabla}_{\Omega}f\left(x\right)\Vert $ and$$\Vert \varvec{\beta }(\textbf{x})\Vert $$ $\Vert \beta \left(x\right)\Vert $ measure different aspects of optimality since$$\Vert \varvec{\varphi }(\textbf{x})\Vert $$ $\Vert \phi \left(x\right)\Vert $ only vanishes when the KKT multipliers at$$\varvec{\beta }(\textbf{x})$$ $\beta \left(x\right)$ have the correct sign, while$$\textbf{x}$$ $x$ only vanishes when$$\varvec{\varphi }(\textbf{x})$$ $\phi \left(x\right)$ is a stationary point in the active manifold. As an application of the theory, an active set algorithm is developed for convex quadratic programs which adapts the flow of the algorithm based on a comparison between$$\textbf{x}$$ $x$ and$$\Vert \varvec{\beta }(\textbf{x})\Vert $$ $\Vert \beta \left(x\right)\Vert $ .$$\Vert \varvec{\varphi }(\textbf{x})\Vert $$ $\Vert \phi \left(x\right)\Vert $ 
Abstract We consider the problem of covering multiple submodular constraints. Given a finite ground set
N , a weight function ,$$w: N \rightarrow \mathbb {R}_+$$ $w:N\to {R}_{+}$r monotone submodular functions over$$f_1,f_2,\ldots ,f_r$$ ${f}_{1},{f}_{2},\dots ,{f}_{r}$N and requirements the goal is to find a minimum weight subset$$k_1,k_2,\ldots ,k_r$$ ${k}_{1},{k}_{2},\dots ,{k}_{r}$ such that$$S \subseteq N$$ $S\subseteq N$ for$$f_i(S) \ge k_i$$ ${f}_{i}\left(S\right)\ge {k}_{i}$ . We refer to this problem as$$1 \le i \le r$$ $1\le i\le r$MultiSubmodCover and it was recently considered by HarPeled and Jones (Few cuts meet many point sets. CoRR.arxiv:abs1808.03260 HarPeled and Jones 2018) who were motivated by an application in geometry. Even with$$r=1$$ $r=1$MultiSubmodCover generalizes the wellknown Submodular Set Cover problem (SubmodSC ), and it can also be easily reduced toSubmodSC . A simple greedy algorithm gives an approximation where$$O(\log (kr))$$ $O(log(kr\left)\right)$ and this ratio cannot be improved in the general case. In this paper, motivated by several concrete applications, we consider two ways to improve upon the approximation given by the greedy algorithm. First, we give a bicriteria approximation algorithm for$$k = \sum _i k_i$$ $k={\sum}_{i}{k}_{i}$MultiSubmodCover that covers each constraint to within a factor of while incurring an approximation of$$(11/e\varepsilon )$$ $(11/e\epsilon )$ in the cost. Second, we consider the special case when each$$O(\frac{1}{\epsilon }\log r)$$ $O(\frac{1}{\u03f5}logr)$ is a obtained from a truncated coverage function and obtain an algorithm that generalizes previous work on partial set cover ($$f_i$$ ${f}_{i}$PartialSC ), covering integer programs (CIPs ) and multiple vertex cover constraints Bera et al. (Theoret Comput Sci 555:2–8 Bera et al. 2014). Both these algorithms are based on mathematical programming relaxations that avoid the limitations of the greedy algorithm. We demonstrate the implications of our algorithms and related ideas to several applications ranging from geometric covering problems to clustering with outliers. Our work highlights the utility of the highlevel model and the lens of submodularity in addressing this class of covering problems.