We consider the problem of covering multiple submodular constraints. Given a finite ground set
We consider the
- NSF-PAR ID:
- 10253777
- Publisher / Repository:
- Springer Science + Business Media
- Date Published:
- Journal Name:
- Mathematical Programming
- Volume:
- 192
- Issue:
- 1-2
- ISSN:
- 0025-5610
- Page Range / eLocation ID:
- p. 497-518
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
Abstract N , a weight function ,$$w: N \rightarrow \mathbb {R}_+$$ r monotone submodular functions over$$f_1,f_2,\ldots ,f_r$$ N and requirements the goal is to find a minimum weight subset$$k_1,k_2,\ldots ,k_r$$ such that$$S \subseteq N$$ for$$f_i(S) \ge k_i$$ . We refer to this problem as$$1 \le i \le r$$ Multi-Submod-Cover and it was recently considered by Har-Peled and Jones (Few cuts meet many point sets. CoRR.arxiv:abs1808.03260 Har-Peled and Jones 2018) who were motivated by an application in geometry. Even with$$r=1$$ Multi-Submod-Cover generalizes the well-known Submodular Set Cover problem (Submod-SC ), and it can also be easily reduced toSubmod-SC . A simple greedy algorithm gives an approximation where$$O(\log (kr))$$ 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$$ Multi-Submod-Cover that covers each constraint to within a factor of while incurring an approximation of$$(1-1/e-\varepsilon )$$ in the cost. Second, we consider the special case when each$$O(\frac{1}{\epsilon }\log r)$$ is a obtained from a truncated coverage function and obtain an algorithm that generalizes previous work on partial set cover ($$f_i$$ Partial-SC ), 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 high-level model and the lens of submodularity in addressing this class of covering problems. -
Abstract Rooted binary
galled trees generalize rooted binary trees to allow a restricted class of cycles, known asgalls . We build upon the Wedderburn-Etherington enumeration of rooted binary unlabeled trees withn leaves to enumerate rooted binary unlabeled galled trees withn leaves, also enumerating rooted binary unlabeled galled trees withn leaves andg galls, . The enumerations rely on a recursive decomposition that considers subtrees descended from the nodes of a gall, adopting a restriction on galls that amounts to considering only the rooted binary$$0 \leqslant g \leqslant \lfloor \frac{n-1}{2} \rfloor $$ normal unlabeled galled trees in our enumeration. We write an implicit expression for the generating function encoding the numbers of trees for alln . We show that the number of rooted binary unlabeled galled trees grows with , exceeding the growth$$0.0779(4.8230^n)n^{-\frac{3}{2}}$$ of the number of rooted binary unlabeled trees without galls. However, the growth of the number of galled trees with only one gall has the same exponential order 2.4833 as the number with no galls, exceeding it only in the subexponential term,$$0.3188(2.4833^n)n^{-\frac{3}{2}}$$ compared to$$0.3910n^{\frac{1}{2}}$$ . For a fixed number of leaves$$0.3188n^{-\frac{3}{2}}$$ n , the number of gallsg that produces the largest number of rooted binary unlabeled galled trees lies intermediate between the minimum of and the maximum of$$g=0$$ . We discuss implications in mathematical phylogenetics.$$g=\lfloor \frac{n-1}{2} \rfloor $$ -
Abstract A long-standing problem in mathematical physics is the rigorous derivation of the incompressible Euler equation from Newtonian mechanics. Recently, Han-Kwan and Iacobelli (Proc Am Math Soc 149:3045–3061, 2021) showed that in the monokinetic regime, one can directly obtain the Euler equation from a system of
N particles interacting in ,$${\mathbb {T}}^d$$ , via Newton’s second law through a$$d\ge 2$$ supercritical mean-field limit . Namely, the coupling constant in front of the pair potential, which is Coulombic, scales like$$\lambda $$ for some$$N^{-\theta }$$ , in contrast to the usual mean-field scaling$$\theta \in (0,1)$$ . Assuming$$\lambda \sim N^{-1}$$ , they showed that the empirical measure of the system is effectively described by the solution to the Euler equation as$$\theta \in (1-\frac{2}{d(d+1)},1)$$ . Han-Kwan and Iacobelli asked if their range for$$N\rightarrow \infty $$ was optimal. We answer this question in the negative by showing the validity of the incompressible Euler equation in the limit$$\theta $$ for$$N\rightarrow \infty $$ . Our proof is based on Serfaty’s modulated-energy method, but compared to that of Han-Kwan and Iacobelli, crucially uses an improved “renormalized commutator” estimate to obtain the larger range for$$\theta \in (1-\frac{2}{d},1)$$ . Additionally, we show that for$$\theta $$ , one cannot, in general, expect convergence in the modulated energy notion of distance.$$\theta \le 1-\frac{2}{d}$$ -
Abstract In this paper, we study multistage stochastic mixed-integer nonlinear programs (MS-MINLP). This general class of problems encompasses, as important special cases, multistage stochastic convex optimization with
non-Lipschitzian value functions and multistage stochastic mixed-integer linear optimization. We develop stochastic dual dynamic programming (SDDP) type algorithms with nested decomposition, deterministic sampling, and stochastic sampling. The key ingredient is a new type of cuts based on generalized conjugacy. Several interesting classes of MS-MINLP are identified, where the new algorithms are guaranteed to obtain the global optimum without the assumption of complete recourse. This significantly generalizes the classic SDDP algorithms. We also characterize the iteration complexity of the proposed algorithms. In particular, for a -stage stochastic MINLP satisfying$$(T+1)$$ L -exact Lipschitz regularization withd -dimensional state spaces, to obtain an -optimal root node solution, we prove that the number of iterations of the proposed deterministic sampling algorithm is upper bounded by$$\varepsilon $$ , and is lower bounded by$${\mathcal {O}}((\frac{2LT}{\varepsilon })^d)$$ for the general case or by$${\mathcal {O}}((\frac{LT}{4\varepsilon })^d)$$ for the convex case. This shows that the obtained complexity bounds are rather sharp. It also reveals that the iteration complexity depends$${\mathcal {O}}((\frac{LT}{8\varepsilon })^{d/2-1})$$ polynomially on the number of stages. We further show that the iteration complexity dependslinearly onT , if all the state spaces are finite sets, or if we seek a -optimal solution when the state spaces are infinite sets, i.e. allowing the optimality gap to scale with$$(T\varepsilon )$$ T . To the best of our knowledge, this is the first work that reports global optimization algorithms as well as iteration complexity results for solving such a large class of multistage stochastic programs. The iteration complexity study resolves a conjecture by the late Prof. Shabbir Ahmed in the general setting of multistage stochastic mixed-integer optimization. -
Abstract Hemiwicking is the phenomena where a liquid wets a textured surface beyond its intrinsic wetting length due to capillary action and imbibition. In this work, we derive a simple analytical model for hemiwicking in micropillar arrays. The model is based on the combined effects of capillary action dictated by interfacial and intermolecular pressures gradients within the curved liquid meniscus and fluid drag from the pillars at ultra-low Reynolds numbers
. Fluid drag is conceptualized via a critical Reynolds number:$${\boldsymbol{(}}{{\bf{10}}}^{{\boldsymbol{-}}{\bf{7}}}{\boldsymbol{\lesssim }}{\bf{Re}}{\boldsymbol{\lesssim }}{{\bf{10}}}^{{\boldsymbol{-}}{\bf{3}}}{\boldsymbol{)}}$$ , where$${\bf{Re}}{\boldsymbol{=}}\frac{{{\bf{v}}}_{{\bf{0}}}{{\bf{x}}}_{{\bf{0}}}}{{\boldsymbol{\nu }}}$$ v 0corresponds to the maximum wetting speed on a flat, dry surface andx 0is the extension length of the liquid meniscus that drives the bulk fluid toward the adsorbed thin-film region. The model is validated with wicking experiments on different hemiwicking surfaces in conjunction withv 0andx 0measurements using Water , viscous FC-70$${\boldsymbol{(}}{{\bf{v}}}_{{\bf{0}}}{\boldsymbol{\approx }}{\bf{2}}\,{\bf{m}}{\boldsymbol{/}}{\bf{s}}{\boldsymbol{,}}\,{\bf{25}}\,{\boldsymbol{\mu }}{\bf{m}}{\boldsymbol{\lesssim }}{{\bf{x}}}_{{\bf{0}}}{\boldsymbol{\lesssim }}{\bf{28}}\,{\boldsymbol{\mu }}{\bf{m}}{\boldsymbol{)}}$$ and lower viscosity Ethanol$${\boldsymbol{(}}{{\boldsymbol{v}}}_{{\bf{0}}}{\boldsymbol{\approx }}{\bf{0.3}}\,{\bf{m}}{\boldsymbol{/}}{\bf{s}}{\boldsymbol{,}}\,{\bf{18.6}}\,{\boldsymbol{\mu }}{\bf{m}}{\boldsymbol{\lesssim }}{{\boldsymbol{x}}}_{{\bf{0}}}{\boldsymbol{\lesssim }}{\bf{38.6}}\,{\boldsymbol{\mu }}{\bf{m}}{\boldsymbol{)}}$$ .$${\boldsymbol{(}}{{\boldsymbol{v}}}_{{\bf{0}}}{\boldsymbol{\approx }}{\bf{1.2}}\,{\bf{m}}{\boldsymbol{/}}{\bf{s}}{\boldsymbol{,}}\,{\bf{11.8}}\,{\boldsymbol{\mu }}{\bf{m}}{\boldsymbol{\lesssim }}{{\bf{x}}}_{{\bf{0}}}{\boldsymbol{\lesssim }}{\bf{33.3}}\,{\boldsymbol{\mu }}{\bf{m}}{\boldsymbol{)}}$$