Title: Hardness and approximation of submodular minimum linear ordering problems
Abstract The minimum linear ordering problem (MLOP) generalizes well-known combinatorial optimization problems such as minimum linear arrangement and minimum sum set cover. MLOP seeks to minimize an aggregated cost$$f(\cdot )$$ f ( · ) due to an ordering$$\sigma $$ σ of the items (say [n]), i.e.,$$\min _{\sigma } \sum _{i\in [n]} f(E_{i,\sigma })$$ min σ i [ n ] f ( E i , σ ) , where$$E_{i,\sigma }$$ E i , σ is the set of items mapped by$$\sigma $$ σ to indices [i]. Despite an extensive literature on MLOP variants and approximations for these, it was unclear whether the graphic matroid MLOP was NP-hard. We settle this question through non-trivial reductions from mininimum latency vertex cover and minimum sum vertex cover problems. We further propose a new combinatorial algorithm for approximating monotone submodular MLOP, using the theory of principal partitions. This is in contrast to the rounding algorithm by Iwata et al. (in: APPROX, 2012), using Lovász extension of submodular functions. We show a$$(2-\frac{1+\ell _{f}}{1+|E|})$$ ( 2 - 1 + f 1 + | E | ) -approximation for monotone submodular MLOP where$$\ell _{f}=\frac{f(E)}{\max _{x\in E}f(\{x\})}$$ f = f ( E ) max x E f ( { x } ) satisfies$$1 \le \ell _f \le |E|$$ 1 f | E | . Our theory provides new approximation bounds for special cases of the problem, in particular a$$(2-\frac{1+r(E)}{1+|E|})$$ ( 2 - 1 + r ( E ) 1 + | E | ) -approximation for the matroid MLOP, where$$f = r$$ f = r is the rank function of a matroid. We further show that minimum latency vertex cover is$$\frac{4}{3}$$ 4 3 -approximable, by which we also lower bound the integrality gap of its natural LP relaxation, which might be of independent interest.  more » « less
Award ID(s):
2151283
PAR ID:
10525122
Author(s) / Creator(s):
; ; ; ;
Publisher / Repository:
Springer Verlag
Date Published:
Journal Name:
Mathematical Programming
ISSN:
0025-5610
Subject(s) / Keyword(s):
Submodular optimization graph labeling approximation algorithm linear arrangement
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract For the partition functionp(n), Ramanujan proved the striking identities$$\begin{aligned} \begin{aligned} \mathcal {P}_5(q):=\sum _{n\ge 0} p(5n+4)q^n&=5\prod _{n\ge 1} \frac{\left( q^5;q^5\right) _{\infty }^5}{(q;q)_{\infty }^6},\\ \mathcal {P}_{7}(q):=\sum _{n\ge 0} p(7n+5)q^n&=7\prod _{n\ge 1}\frac{\left( q^7;q^7\right) _{\infty }^3}{(q;q)_{\infty }^4}+49q \prod _{n\ge 1}\frac{\left( q^7;q^7\right) _{\infty }^7}{(q;q)_{\infty }^8}, \end{aligned} \end{aligned}$$ P 5 ( q ) : = n 0 p ( 5 n + 4 ) q n = 5 n 1 q 5 ; q 5 5 ( q ; q ) 6 , P 7 ( q ) : = n 0 p ( 7 n + 5 ) q n = 7 n 1 q 7 ; q 7 3 ( q ; q ) 4 + 49 q n 1 q 7 ; q 7 7 ( q ; q ) 8 , where$$(q;q)_{\infty }:=\prod _{n\ge 1}(1-q^n).$$ ( q ; q ) : = n 1 ( 1 - q n ) . As these identities imply his celebrated congruences modulo 5 and 7, it is natural to seek, for primes$$\ell \ge 5,$$ 5 , closed form expressions of the power series$$ \mathcal {P}_{\ell }(q):=\sum _{n\ge 0} p(\ell n-\delta _{\ell })q^n\pmod {\ell }, $$ P ( q ) : = n 0 p ( n - δ ) q n ( mod ) , where$$\delta _{\ell }:=\frac{\ell ^2-1}{24}.$$ δ : = 2 - 1 24 . In this paper, we prove that$$ \mathcal {P}_{\ell }(q)\equiv c_{\ell } \dfrac{\mathcal {T}_{\ell }(q)}{\left( q^\ell ; q^\ell \right) _\infty } \pmod {\ell }, $$ P ( q ) c T ( q ) q ; q ( mod ) , where$$c_{\ell }\in \mathbb Z$$ c Z is explicit and$${\mathcal {T}}_{\ell }(q)$$ T ( q ) is the generating function for the Hecke traces of$$\ell $$ -ramified values of special Dirichlet series for weight$$\ell -1$$ - 1 cusp forms on$$\textrm{SL}_2(\mathbb Z)$$ SL 2 ( Z ) . This is a new proof of Ramanujan’s congruences modulo 5, 7, and 11, as there are no nontrivial cusp forms of weight 4, 6, and 10. 
    more » « less
  2. Abstract Let$$\mathbb {F}_q^d$$ F q d be thed-dimensional vector space over the finite field withqelements. For a subset$$E\subseteq \mathbb {F}_q^d$$ E F q d and a fixed nonzero$$t\in \mathbb {F}_q$$ t F q , let$$\mathcal {H}_t(E)=\{h_y: y\in E\}$$ H t ( E ) = { h y : y E } , where$$h_y:E\rightarrow \{0,1\}$$ h y : E { 0 , 1 } is the indicator function of the set$$\{x\in E: x\cdot y=t\}$$ { x E : x · y = t } . Two of the authors, with Maxwell Sun, showed in the case$$d=3$$ d = 3 that if$$|E|\ge Cq^{\frac{11}{4}}$$ | E | C q 11 4 andqis sufficiently large, then the VC-dimension of$$\mathcal {H}_t(E)$$ H t ( E ) is 3. In this paper, we generalize the result to arbitrary dimension by showing that the VC-dimension of$$\mathcal {H}_t(E)$$ H t ( E ) isdwhenever$$E\subseteq \mathbb {F}_q^d$$ E F q d with$$|E|\ge C_d q^{d-\frac{1}{d-1}}$$ | E | C d q d - 1 d - 1
    more » « less
  3. Abstract We study holomorphic mapsFfrom a smooth Levi non-degenerate real hypersurface$$ M_{\ell }\subset {\mathbb {C}}^n $$ M C n into a hyperquadric$$ {\mathbb {H}}_{\ell '}^N $$ H N with signatures$$ \ell \le (n-1)/2 $$ ( n - 1 ) / 2 and$$ \ell '\le (N-1)/2,$$ ( N - 1 ) / 2 , respectively. Assuming that$$ N - n < n - 1,$$ N - n < n - 1 , we prove that if$$ \ell = \ell ',$$ = , thenFis either CR transversal to$$ {\mathbb {H}}_{\ell }^N $$ H N at every point of$$ M_{\ell },$$ M , or it maps a neighborhood of$$ M_{\ell } $$ M in$$ {\mathbb {C}}^n $$ C n into$$ {\mathbb {H}}_{\ell }^N.$$ H N . Furthermore, in the case where$$ \ell ' > \ell ,$$ > , we show that ifFis not CR transversal at$$0\in M_\ell ,$$ 0 M , then it must be transversally flat. The latter is best possible. 
    more » « less
  4. Abstract LetXbe a compact normal complex space of dimensionnandLbe a holomorphic line bundle onX. Suppose that$$\Sigma =(\Sigma _1,\ldots ,\Sigma _\ell )$$ Σ = ( Σ 1 , , Σ ) is an$$\ell $$ -tuple of distinct irreducible proper analytic subsets ofX,$$\tau =(\tau _1,\ldots ,\tau _\ell )$$ τ = ( τ 1 , , τ ) is an$$\ell $$ -tuple of positive real numbers, and let$$H^0_0(X,L^p)$$ H 0 0 ( X , L p ) be the space of holomorphic sections of$$L^p:=L^{\otimes p}$$ L p : = L p that vanish to order at least$$\tau _jp$$ τ j p along$$\Sigma _j$$ Σ j ,$$1\le j\le \ell $$ 1 j . If$$Y\subset X$$ Y X is an irreducible analytic subset of dimensionm, we consider the space$$H^0_0 (X|Y, L^p)$$ H 0 0 ( X | Y , L p ) of holomorphic sections of$$L^p|_Y$$ L p | Y that extend to global holomorphic sections in$$H^0_0(X,L^p)$$ H 0 0 ( X , L p ) . Assuming that the triplet$$(L,\Sigma ,\tau )$$ ( L , Σ , τ ) is big in the sense that$$\dim H^0_0(X,L^p)\sim p^n$$ dim H 0 0 ( X , L p ) p n , we give a general condition onYto ensure that$$\dim H^0_0(X|Y,L^p)\sim p^m$$ dim H 0 0 ( X | Y , L p ) p m . WhenLis endowed with a continuous Hermitian metric, we show that the Fubini-Study currents of the spaces$$H^0_0(X|Y,L^p)$$ H 0 0 ( X | Y , L p ) converge to a certain equilibrium current onY. We apply this to the study of the equidistribution of zeros inYof random holomorphic sections in$$H^0_0(X|Y,L^p)$$ H 0 0 ( X | Y , L p ) as$$p\rightarrow \infty $$ p
    more » « less
  5. Abstract A family ofrdistinct sets$$\{A_1,\ldots , A_r\}$$ { A 1 , , A r } is anr-sunflower if for all$$1 \leqslant i < j\leqslant r$$ 1 i < j r and$$1 \leqslant i' < j'\leqslant r$$ 1 i < j r , we have$$A_i\cap A_j = A_{i'}\cap A_{j'}$$ A i A j = A i A j . Erdős and Rado conjectured in 1960 that every family$$\mathcal {H}$$ H of$$\ell $$ -element sets of size at least$$K(r)^\ell $$ K ( r ) contains anr-sunflower, whereK(r) is some function that depends only onr. We prove that if$$\mathcal {H}$$ H is a family of$$\ell $$ -element sets of VC-dimension at mostdand$$|\mathcal H| > (C r(\log d+\log ^*\ell ))^\ell $$ | H | > ( C r ( log d + log ) ) for some absolute constant$$C > 0$$ C > 0 , then$$\mathcal {H}$$ H contains anr-sunflower. This improves a recent result of Fox, Pach, and Suk. When$$d=1$$ d = 1 , we obtain a sharp bound, namely that$$|\mathcal H| > (r-1)^\ell $$ | H | > ( r - 1 ) is sufficient. Along the way, we establish a strengthening of the Kahn–Kalai conjecture for set families of bounded VC-dimension, which is of independent interest. 
    more » « less