skip to main content


Title: A fast $$(2 + \frac{2}{7})$$-approximation algorithm for capacitated cycle covering
Abstract

We consider thecapacitated cycle covering problem: given an undirected, complete graphGwith metric edge lengths and demands on the vertices, we want to cover the vertices with vertex-disjoint cycles, each serving a demand of at most one. The objective is to minimize a linear combination of the total length and the number of cycles. This problem is closely related to the capacitated vehicle routing problem (CVRP) and other cycle cover problems such as min-max cycle cover and bounded cycle cover. We show that a greedy algorithm followed by a post-processing step yields a$$(2 + \frac{2}{7})$$(2+27)-approximation for this problem by comparing the solution to a polymatroid relaxation. We also show that the analysis of our algorithm is tight and provide a$$2 + \epsilon $$2+ϵlower bound for the relaxation.

 
more » « less
NSF-PAR ID:
10253777
Author(s) / Creator(s):
;
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
  1. Abstract

    We consider the problem of covering multiple submodular constraints. Given a finite ground setN, a weight function$$w: N \rightarrow \mathbb {R}_+$$w:NR+,rmonotone submodular functions$$f_1,f_2,\ldots ,f_r$$f1,f2,,froverNand requirements$$k_1,k_2,\ldots ,k_r$$k1,k2,,krthe goal is to find a minimum weight subset$$S \subseteq N$$SNsuch that$$f_i(S) \ge k_i$$fi(S)kifor$$1 \le i \le r$$1ir. We refer to this problem asMulti-Submod-Coverand it was recently considered by Har-Peled and Jones (Few cuts meet many point sets. CoRR.arxiv:abs1808.03260Har-Peled and Jones 2018) who were motivated by an application in geometry. Even with$$r=1$$r=1Multi-Submod-Covergeneralizes the well-known Submodular Set Cover problem (Submod-SC), and it can also be easily reduced toSubmod-SC. A simple greedy algorithm gives an$$O(\log (kr))$$O(log(kr))approximation where$$k = \sum _i k_i$$k=ikiand 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 forMulti-Submod-Coverthat covers each constraint to within a factor of$$(1-1/e-\varepsilon )$$(1-1/e-ε)while incurring an approximation of$$O(\frac{1}{\epsilon }\log r)$$O(1ϵlogr)in the cost. Second, we consider the special case when each$$f_i$$fiis a obtained from a truncated coverage function and obtain an algorithm that generalizes previous work on partial set cover (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.

     
    more » « less
  2. Abstract

    Rooted binarygalledtrees 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 withnleaves to enumerate rooted binary unlabeled galled trees withnleaves, also enumerating rooted binary unlabeled galled trees withnleaves andggalls,$$0 \leqslant g \leqslant \lfloor \frac{n-1}{2} \rfloor $$0gn-12. 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 binarynormalunlabeled 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$$0.0779(4.8230^n)n^{-\frac{3}{2}}$$0.0779(4.8230n)n-32, exceeding the growth$$0.3188(2.4833^n)n^{-\frac{3}{2}}$$0.3188(2.4833n)n-32of 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.3910n^{\frac{1}{2}}$$0.3910n12compared to$$0.3188n^{-\frac{3}{2}}$$0.3188n-32. For a fixed number of leavesn, the number of gallsgthat produces the largest number of rooted binary unlabeled galled trees lies intermediate between the minimum of$$g=0$$g=0and the maximum of$$g=\lfloor \frac{n-1}{2} \rfloor $$g=n-12. We discuss implications in mathematical phylogenetics.

     
    more » « less
  3. 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 ofNparticles interacting in$${\mathbb {T}}^d$$Td,$$d\ge 2$$d2, via Newton’s second law through asupercritical mean-field limit. Namely, the coupling constant$$\lambda $$λin front of the pair potential, which is Coulombic, scales like$$N^{-\theta }$$N-θfor some$$\theta \in (0,1)$$θ(0,1), in contrast to the usual mean-field scaling$$\lambda \sim N^{-1}$$λN-1. Assuming$$\theta \in (1-\frac{2}{d(d+1)},1)$$θ(1-2d(d+1),1), they showed that the empirical measure of the system is effectively described by the solution to the Euler equation as$$N\rightarrow \infty $$N. Han-Kwan and Iacobelli asked if their range for$$\theta $$θwas optimal. We answer this question in the negative by showing the validity of the incompressible Euler equation in the limit$$N\rightarrow \infty $$Nfor$$\theta \in (1-\frac{2}{d},1)$$θ(1-2d,1). 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 $$θ. Additionally, we show that for$$\theta \le 1-\frac{2}{d}$$θ1-2d, one cannot, in general, expect convergence in the modulated energy notion of distance.

     
    more » « less
  4. 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 withnon-Lipschitzianvalue 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$$(T+1)$$(T+1)-stage stochastic MINLP satisfyingL-exact Lipschitz regularization withd-dimensional state spaces, to obtain an$$\varepsilon $$ε-optimal root node solution, we prove that the number of iterations of the proposed deterministic sampling algorithm is upper bounded by$${\mathcal {O}}((\frac{2LT}{\varepsilon })^d)$$O((2LTε)d), and is lower bounded by$${\mathcal {O}}((\frac{LT}{4\varepsilon })^d)$$O((LT4ε)d)for the general case or by$${\mathcal {O}}((\frac{LT}{8\varepsilon })^{d/2-1})$$O((LT8ε)d/2-1)for the convex case. This shows that the obtained complexity bounds are rather sharp. It also reveals that the iteration complexity dependspolynomiallyon the number of stages. We further show that the iteration complexity dependslinearlyonT, if all the state spaces are finite sets, or if we seek a$$(T\varepsilon )$$(Tε)-optimal solution when the state spaces are infinite sets, i.e. allowing the optimality gap to scale withT. 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.

     
    more » « less
  5. 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$${\boldsymbol{(}}{{\bf{10}}}^{{\boldsymbol{-}}{\bf{7}}}{\boldsymbol{\lesssim }}{\bf{Re}}{\boldsymbol{\lesssim }}{{\bf{10}}}^{{\boldsymbol{-}}{\bf{3}}}{\boldsymbol{)}}$$(107Re103). Fluid drag is conceptualized via a critical Reynolds number:$${\bf{Re}}{\boldsymbol{=}}\frac{{{\bf{v}}}_{{\bf{0}}}{{\bf{x}}}_{{\bf{0}}}}{{\boldsymbol{\nu }}}$$Re=v0x0ν, wherev0corresponds to the maximum wetting speed on a flat, dry surface andx0is 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 withv0andx0measurements using Water$${\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{)}}$$(v02m/s,25µmx028µm), viscous FC-70$${\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{)}}$$(v00.3m/s,18.6µmx038.6µm)and lower viscosity Ethanol$${\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{)}}$$(v01.2m/s,11.8µmx033.3µm).

     
    more » « less