Attention:

The NSF Public Access Repository (NSF-PAR) system and access will be unavailable from 5:00 PM ET until 11:00 PM ET on Friday, June 21 due to maintenance. We apologize for the inconvenience.

From approximate to exact integer programming
Abstract

Approximate integer programming is the following: For a given convex body$$K \subseteq {\mathbb {R}}^n$$$K\subseteq {R}^{n}$, either determine whether$$K \cap {\mathbb {Z}}^n$$$K\cap {Z}^{n}$is empty, or find an integer point in the convex body$$2\cdot (K - c) +c$$$2·\left(K-c\right)+c$which isK, scaled by 2 from its center of gravityc. Approximate integer programming can be solved in time$$2^{O(n)}$$${2}^{O\left(n\right)}$while the fastest known methods for exact integer programming run in time$$2^{O(n)} \cdot n^n$$${2}^{O\left(n\right)}·{n}^{n}$. 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$$x^* \in (K \cap {\mathbb {Z}}^n)$$${x}^{\ast }\in \left(K\cap {Z}^{n}\right)$can be found in time$$2^{O(n)}$$${2}^{O\left(n\right)}$, provided that theremaindersof each component$$x_i^* \mod \ell$$${x}_{i}^{\ast }\phantom{\rule{0ex}{0ex}}mod\phantom{\rule{0ex}{0ex}}\ell$for some arbitrarily fixed$$\ell \ge 5(n+1)$$$\ell \ge 5\left(n+1\right)$of$$x^*$$${x}^{\ast }$are given. The algorithm is based on acutting-plane 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$$2^{O(n)}n^n$$${2}^{O\left(n\right)}{n}^{n}$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 newasymmetric approximate Carathéodory theoremthat might be of interest on its own. Our second method concerns integer programming problems in equation-standard form$$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}$. Such a problem can be reduced to the solution of$$\prod _i O(\log u_i +1)$$${\prod }_{i}O\left(log{u}_{i}+1\right)$approximate integer programming problems. This implies, for example thatknapsackorsubset-sumproblems withpolynomial variable range$$0 \le x_i \le p(n)$$$0\le {x}_{i}\le p\left(n\right)$can be solved in time$$(\log n)^{O(n)}$$${\left(logn\right)}^{O\left(n\right)}$. For these problems, the best running time so far was$$n^n \cdot 2^{O(n)}$$${n}^{n}·{2}^{O\left(n\right)}$.

more » « less
NSF-PAR ID:
10502164
Author(s) / Creator(s):
; ;
Publisher / Repository:
Date Published:
Journal Name:
Mathematical Programming
ISSN:
0025-5610
Format(s):
Medium: X
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:N\to {R}_{+}$,rmonotone submodular functions$$f_1,f_2,\ldots ,f_r$$${f}_{1},{f}_{2},\dots ,{f}_{r}$overNand requirements$$k_1,k_2,\ldots ,k_r$$${k}_{1},{k}_{2},\dots ,{k}_{r}$the goal is to find a minimum weight subset$$S \subseteq N$$$S\subseteq N$such that$$f_i(S) \ge k_i$$${f}_{i}\left(S\right)\ge {k}_{i}$for$$1 \le i \le r$$$1\le i\le r$. 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=1$Multi-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\left(log\left(kr\right)\right)$approximation where$$k = \sum _i k_i$$$k={\sum }_{i}{k}_{i}$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 forMulti-Submod-Coverthat covers each constraint to within a factor of$$(1-1/e-\varepsilon )$$$\left(1-1/e-\epsilon \right)$while incurring an approximation of$$O(\frac{1}{\epsilon }\log r)$$$O\left(\frac{1}{ϵ}logr\right)$in the cost. Second, we consider the special case when each$$f_i$$${f}_{i}$is 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

Let$$(h_I)$$$\left({h}_{I}\right)$denote the standard Haar system on [0, 1], indexed by$$I\in \mathcal {D}$$$I\in D$, the set of dyadic intervals and$$h_I\otimes h_J$$${h}_{I}\otimes {h}_{J}$denote the tensor product$$(s,t)\mapsto h_I(s) h_J(t)$$$\left(s,t\right)↦{h}_{I}\left(s\right){h}_{J}\left(t\right)$,$$I,J\in \mathcal {D}$$$I,J\in D$. We consider a class of two-parameter function spaces which are completions of the linear span$$\mathcal {V}(\delta ^2)$$$V\left({\delta }^{2}\right)$of$$h_I\otimes h_J$$${h}_{I}\otimes {h}_{J}$,$$I,J\in \mathcal {D}$$$I,J\in D$. This class contains all the spaces of the formX(Y), whereXandYare either the Lebesgue spaces$$L^p[0,1]$$${L}^{p}\left[0,1\right]$or the Hardy spaces$$H^p[0,1]$$${H}^{p}\left[0,1\right]$,$$1\le p < \infty$$$1\le p<\infty$. We say that$$D:X(Y)\rightarrow X(Y)$$$D:X\left(Y\right)\to X\left(Y\right)$is a Haar multiplier if$$D(h_I\otimes h_J) = d_{I,J} h_I\otimes h_J$$$D\left({h}_{I}\otimes {h}_{J}\right)={d}_{I,J}{h}_{I}\otimes {h}_{J}$, where$$d_{I,J}\in \mathbb {R}$$${d}_{I,J}\in R$, and ask which more elementary operators factor throughD. A decisive role is played by theCapon projection$$\mathcal {C}:\mathcal {V}(\delta ^2)\rightarrow \mathcal {V}(\delta ^2)$$$C:V\left({\delta }^{2}\right)\to V\left({\delta }^{2}\right)$given by$$\mathcal {C} h_I\otimes h_J = h_I\otimes h_J$$$C{h}_{I}\otimes {h}_{J}={h}_{I}\otimes {h}_{J}$if$$|I|\le |J|$$$|I|\le |J|$, and$$\mathcal {C} h_I\otimes h_J = 0$$$C{h}_{I}\otimes {h}_{J}=0$if$$|I| > |J|$$$|I|>|J|$, as our main result highlights: Given any bounded Haar multiplier$$D:X(Y)\rightarrow X(Y)$$$D:X\left(Y\right)\to X\left(Y\right)$, there exist$$\lambda ,\mu \in \mathbb {R}$$$\lambda ,\mu \in R$such that\begin{aligned} \lambda \mathcal {C} + \mu ({{\,\textrm{Id}\,}}-\mathcal {C})\text { approximately 1-projectionally factors through }D, \end{aligned}$\begin{array}{c}\lambda C+\mu \left(\phantom{\rule{0ex}{0ex}}\text{Id}\phantom{\rule{0ex}{0ex}}-C\right)\phantom{\rule{0ex}{0ex}}\text{approximately 1-projectionally factors through}\phantom{\rule{0ex}{0ex}}D,\end{array}$i.e., for all$$\eta > 0$$$\eta >0$, there exist bounded operatorsABso thatABis the identity operator$${{\,\textrm{Id}\,}}$$$\phantom{\rule{0ex}{0ex}}\text{Id}\phantom{\rule{0ex}{0ex}}$,$$\Vert A\Vert \cdot \Vert B\Vert = 1$$$‖A‖·‖B‖=1$and$$\Vert \lambda \mathcal {C} + \mu ({{\,\textrm{Id}\,}}-\mathcal {C}) - ADB\Vert < \eta$$$‖\lambda C+\mu \left(\phantom{\rule{0ex}{0ex}}\text{Id}\phantom{\rule{0ex}{0ex}}-C\right)-ADB‖<\eta$. Additionally, if$$\mathcal {C}$$$C$is unbounded onX(Y), then$$\lambda = \mu$$$\lambda =\mu$and then$${{\,\textrm{Id}\,}}$$$\phantom{\rule{0ex}{0ex}}\text{Id}\phantom{\rule{0ex}{0ex}}$either factors throughDor$${{\,\textrm{Id}\,}}-D$$$\phantom{\rule{0ex}{0ex}}\text{Id}\phantom{\rule{0ex}{0ex}}-D$.

more » « less
3. Abstract

Let us fix a primepand a homogeneous system ofmlinear equations$$a_{j,1}x_1+\dots +a_{j,k}x_k=0$$${a}_{j,1}{x}_{1}+\cdots +{a}_{j,k}{x}_{k}=0$for$$j=1,\dots ,m$$$j=1,\cdots ,m$with coefficients$$a_{j,i}\in \mathbb {F}_p$$${a}_{j,i}\in {F}_{p}$. Suppose that$$k\ge 3m$$$k\ge 3m$, that$$a_{j,1}+\dots +a_{j,k}=0$$${a}_{j,1}+\cdots +{a}_{j,k}=0$for$$j=1,\dots ,m$$$j=1,\cdots ,m$and that every$$m\times m$$$m×m$minor of the$$m\times k$$$m×k$matrix$$(a_{j,i})_{j,i}$$${\left({a}_{j,i}\right)}_{j,i}$is non-singular. Then we prove that for any (large)n, any subset$$A\subseteq \mathbb {F}_p^n$$$A\subseteq {F}_{p}^{n}$of size$$|A|> C\cdot \Gamma ^n$$$|A|>C·{\Gamma }^{n}$contains a solution$$(x_1,\dots ,x_k)\in A^k$$$\left({x}_{1},\cdots ,{x}_{k}\right)\in {A}^{k}$to the given system of equations such that the vectors$$x_1,\dots ,x_k\in A$$${x}_{1},\cdots ,{x}_{k}\in A$are all distinct. Here,Cand$$\Gamma$$$\Gamma$are constants only depending onp,mandksuch that$$\Gamma $\Gamma . The crucial point here is the condition for the vectors$$x_1,\dots ,x_k$$${x}_{1},\cdots ,{x}_{k}$in the solution$$(x_1,\dots ,x_k)\in A^k$$$\left({x}_{1},\cdots ,{x}_{k}\right)\in {A}^{k}$to be distinct. If we relax this condition and only demand that$$x_1,\dots ,x_k$$${x}_{1},\cdots ,{x}_{k}$are not all equal, then the statement would follow easily from Tao’s slice rank polynomial method. However, handling the distinctness condition is much harder, and requires a new approach. While all previous combinatorial applications of the slice rank polynomial method have relied on the slice rank of diagonal tensors, we use a slice rank argument for a non-diagonal tensor in combination with combinatorial and probabilistic arguments. more » « less 4. Abstract In this article, we study the moduli of irregular surfaces of general type with at worst canonical singularities satisfying$$K^2 = 4p_g-8$$${K}^{2}=4{p}_{g}-8$, for any even integer$$p_g\ge 4$$${p}_{g}\ge 4$. These surfaces also have unbounded irregularityq. We carry out our study by investigating the deformations of the canonical morphism$$\varphi :X\rightarrow {\mathbb {P}}^N$$$\phi :X\to {P}^{N}$, where$$\varphi $$$\phi$is a quadruple Galois cover of a smooth surface of minimal degree. These canonical covers are classified in Gallego and Purnaprajna (Trans Am Math Soc 360(10):5489-5507, 2008) into four distinct families, one of which is the easy case of a product of curves. The main objective of this article is to study the deformations of the other three, non trivial, unbounded families. We show that any deformation of$$\varphi $$$\phi$factors through a double cover of a ruled surface and, hence, is never birational. More interestingly, we prove that, with two exceptions, a general deformation of$$\varphi $$$\phi$is two-to-one onto its image, whose normalization is a ruled surface of appropriate irregularity. We also show that, with the exception of one family, the deformations ofXare unobstructed even though$$H^2(T_X)$$${H}^{2}\left({T}_{X}\right)$does not vanish. Consequently,Xbelongs to a unique irreducible component of the Gieseker moduli space. These irreducible components are uniruled. As a result of all this, we show the existence of infinitely many moduli spaces, satisfying the strict Beauville inequality$$p_g > 2q-4$$${p}_{g}>2q-4$, with an irreducible component that has a proper quadruple sublocus where the degree of the canonical morphism jumps up. These components are above the Castelnuovo line, but nonetheless parametrize surfaces with non birational canonical morphisms. The existence of jumping subloci is a contrast with the moduli of surfaces with$$K^2 = 2p_g- 4$$${K}^{2}=2{p}_{g}-4$, studied by Horikawa. Irreducible moduli components with a jumping sublocus also present a similarity and a difference to the moduli of curves of genus$$g\ge 3$g\ge 3$, for, like in the case of curves, the degree of the canonical morphism goes down outside a closed sublocus but, unlike in the case of curves, it is never birational. Finally, our study shows that there are infinitely many moduli spaces with an irreducible component whose general elements have non birational canonical morphism and another irreducible component whose general elements have birational canonical map.

more » « less
5. Abstract

We continue the program of proving circuit lower bounds via circuit satisfiability algorithms. So far, this program has yielded several concrete results, proving that functions in$\mathsf {Quasi}\text {-}\mathsf {NP} = \mathsf {NTIME}[n^{(\log n)^{O(1)}}]$$\mathrm{Quasi}-\mathrm{NP}=\mathrm{NTIME}\left[{n}^{{\left(\mathrm{log}n\right)}^{O\left(1\right)}}\right]$and other complexity classes do not have small circuits (in the worst case and/or on average) from various circuit classes$\mathcal { C}$$C$, by showing that$\mathcal { C}$$C$admits non-trivial satisfiability and/or#SAT algorithms which beat exhaustive search by a minor amount. In this paper, we present a new strong lower bound consequence of having a non-trivial#SAT algorithm for a circuit class${\mathcal C}$$C$. Say that a symmetric Boolean functionf(x1,…,xn) issparseif it outputs 1 onO(1) values of${\sum }_{i} x_{i}$${\sum }_{i}{x}_{i}$. We show that for every sparsef, and for all “typical”$\mathcal { C}$$C$, faster#SAT algorithms for$\mathcal { C}$$C$circuits imply lower bounds against the circuit class$f \circ \mathcal { C}$$f\circ C$, which may bestrongerthan$\mathcal { C}$$C$itself. In particular:

#SAT algorithms fornk-size$\mathcal { C}$$C$-circuits running in 2n/nktime (for allk) implyNEXPdoes not have$(f \circ \mathcal { C})$$\left(f\circ C\right)$-circuits of polynomial size.

#SAT algorithms for$2^{n^{{\varepsilon }}}$${2}^{{n}^{\epsilon }}$-size$\mathcal { C}$$C$-circuits running in$2^{n-n^{{\varepsilon }}}$${2}^{n-{n}^{\epsilon }}$time (for someε> 0) implyQuasi-NPdoes not have$(f \circ \mathcal { C})$$\left(f\circ C\right)$-circuits of polynomial size.

Applying#SAT algorithms from the literature, one immediate corollary of our results is thatQuasi-NPdoes not haveEMAJACC0THRcircuits of polynomial size, whereEMAJis the “exact majority” function, improving previous lower bounds againstACC0[Williams JACM’14] andACC0THR[Williams STOC’14], [Murray-Williams STOC’18]. This is the first nontrivial lower bound against such a circuit class.

more » « less