More Like this

1. Hardness and approximation of submodular minimum linear ordering problems

   https://doi.org/10.1007/s10107-023-02038-z  

   Farhadi, Majid; Gupta, Swati; Sun, Shengding; Tetali, Prasad; Wigal, Michael C (December 2023, Mathematical Programming)

   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 $$ $\sigma$of the items (say [n]), i.e.,$$\min _{\sigma } \sum _{i\in [n]} f(E_{i,\sigma })$$ ${min}_{\sigma }{\sum }_{i\in \left[n\right]}f\left(E_{i,\sigma }\right)$, where$$E_{i,\sigma }$$ $E_{i,\sigma }$is the set of items mapped by$$\sigma $$ $\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-\frac{1+{\ell }_f}{1+\left|E\right|})$-approximation for monotone submodular MLOP where$$\ell _{f}=\frac{f(E)}{\max _{x\in E}f(\{x\})}$$ ${\ell }_f=\frac{f\left(E\right)}{{max}_{x\in E}f\left(\left\{x\right\}\right)}$satisfies$$1 \le \ell _f \le |E|$$ $1\le {\ell }_f\le \left|E\right|$. Our theory provides new approximation bounds for special cases of the problem, in particular a$$(2-\frac{1+r(E)}{1+|E|})$$ $(2-\frac{1+r\left(E\right)}{1+\left|E\right|})$-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}$$ $\frac{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
2. Finding solutions with distinct variables to systems of linear equations over $$\mathbb {F}_p$$

   https://doi.org/10.1007/s00208-022-02391-y  

   Sauermann, Lisa (April 2022, Mathematische Annalen)

   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\times m$minor of the$$m\times k$$ $m\times 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$$ $\left|A\right|>C·{\Gamma }^n$contains a solution$$(x_1,\dots ,x_k)\in A^k$$ $(x_1,\cdots ,x_k)\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 <p$. 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$$ $(x_1,\cdots ,x_k)\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
3. On a Traveling Salesman Problem for Points in the Unit Cube

   https://doi.org/10.1007/s00453-024-01257-w  

   Balogh, József; Clemen, Felix Christian; Dumitrescu, Adrian (September 2024, Algorithmica)

   Abstract LetXbe ann-element point set in thek-dimensional unit cube$$[0,1]^k$$ ${[0,1]}^k$where$$k \ge 2$$ $k\ge 2$. According to an old result of Bollobás and Meir (Oper Res Lett 11:19–21, 1992) , there exists a cycle (tour)$$x_1, x_2, \ldots , x_n$$ $x_1,x_2,\dots ,x_n$through thenpoints, such that$$\left( \sum _{i=1}^n |x_i - x_{i+1}|^k \right) ^{1/k} \le c_k$$ ${\left({\sum }_{i=1}^n,{|x_i-x_{i+1}|}^k\right)}^{1/k}\le c_k$, where$$|x-y|$$ $|x-y|$is the Euclidean distance betweenxandy, and$$c_k$$ $c_k$is an absolute constant that depends only onk, where$$x_{n+1} \equiv x_1$$ $x_{n+1}\equiv x_1$. From the other direction, for every$$k \ge 2$$ $k\ge 2$and$$n \ge 2$$ $n\ge 2$, there existnpoints in$$[0,1]^k$$ ${[0,1]}^k$, such that their shortest tour satisfies$$\left( \sum _{i=1}^n |x_i - x_{i+1}|^k \right) ^{1/k} = 2^{1/k} \cdot \sqrt{k}$$ ${\left({\sum }_{i=1}^n,{|x_i-x_{i+1}|}^k\right)}^{1/k}=2^{1/k}·\sqrt{k}$. For the plane, the best constant is$$c_2=2$$ $c_2=2$and this is the only exact value known. Bollobás and Meir showed that one can take$$c_k = 9 \left( \frac{2}{3} \right) ^{1/k} \cdot \sqrt{k}$$ $c_k=9{\left(\frac{2}{3}\right)}^{1/k}·\sqrt{k}$for every$$k \ge 3$$ $k\ge 3$and conjectured that the best constant is$$c_k = 2^{1/k} \cdot \sqrt{k}$$ $c_k=2^{1/k}·\sqrt{k}$, for every$$k \ge 2$$ $k\ge 2$. Here we significantly improve the upper bound and show that one can take$$c_k = 3 \sqrt{5} \left( \frac{2}{3} \right) ^{1/k} \cdot \sqrt{k}$$ $c_k=3\sqrt{5}{\left(\frac{2}{3}\right)}^{1/k}·\sqrt{k}$or$$c_k = 2.91 \sqrt{k} \ (1+o_k(1))$$ $c_k=2.91\sqrt{k}(1+o_k\left(1\right))$. Our bounds are constructive. We also show that$$c_3 \ge 2^{7/6}$$ $c_3\ge 2^{7/6}$, which disproves the conjecture for$$k=3$$ $k=3$. Connections to matching problems, power assignment problems, related problems, including algorithms, are discussed in this context. A slightly revised version of the Bollobás–Meir conjecture is proposed. 

   more » « less
4. Equality Conditions for the Fractional Superadditive Volume Inequalities

   https://doi.org/10.1007/s00454-024-00672-8  

   Meyer, Mark (July 2025, Discrete & Computational Geometry)

   Abstract While studying set function properties of Lebesgue measure, F. Barthe and M. Madiman proved that Lebesgue measure is fractionally superadditive on compact sets in$$\mathbb {R}^n$$ $R^n$. In doing this they proved a fractional generalization of the Brunn–Minkowski–Lyusternik (BML) inequality in dimension$$n=1$$ $n=1$. In this paper we will prove the equality conditions for the fractional superadditive volume inequalites for any dimension. The non-trivial equality conditions are as follows. In the one-dimensional case we will show that for a fractional partition$$(\mathcal {G},\beta )$$ $(G,\beta )$and nonempty sets$$A_1,\dots ,A_m\subseteq \mathbb {R}$$ $A_1,\cdots ,A_m\subseteq R$, equality holds iff for each$$S\in \mathcal {G}$$ $S\in G$, the set$$\sum _{i\in S}A_i$$ ${\sum }_{i\in S}{A}_i$is an interval. In the case of dimension$$n\ge 2$$ $n\ge 2$we will show that equality can hold if and only if the set$$\sum _{i=1}^{m}A_i$$ ${\sum }_{i=1}^m{A}_i$has measure 0. 

   more » « less
5. Universality and phase transitions in low moments of secular coefficients of critical holomorphic multiplicative chaos

   https://doi.org/10.1007/s00440-025-01443-z  

   Gu, Haotian; Zhang, Zhenyuan (November 2025, Probability Theory and Related Fields)

   Abstract We investigate the low moments$$\mathbb {E}[|A_N|^{2q}],\, 0 $E\left[\right|A_N{|}^{2q}],0<q⩽1$of secular coefficients$$A_N$$ $A_N$of the critical non-Gaussian holomorphic multiplicative chaos, i.e. coefficients of$$z^N$$ $z^N$in the power series expansion of$$\exp (\sum _{k=1}^\infty X_kz^k/\sqrt{k})$$ $exp({\sum }_{k=1}^{\infty }{X}_k{z}^k/\sqrt{k})$, where$$\{X_k\}_{k\geqslant 1}$$ ${\left\{X_k\right\}}_{k⩾1}$are i.i.d. rotationally invariant unit variance complex random variables. Inspired by Harper’s remarkable result on random multiplicative functions, Soundararajan and Zaman recently showed that if each$$X_k$$ $X_k$is standard complex Gaussian,$$A_N$$ $A_N$features better-than-square-root cancellation:$$\mathbb {E}[|A_N|^2]=1$$ $E\left[\right|A_N{|}^2]=1$and$$\mathbb {E}[|A_N|^{2q}]\asymp (\log N)^{-q/2}$$ $E\left[\right|A_N{|}^{2q}]\asymp {(logN)}^{-q/2}$for fixed$$q\in (0,1)$$ $q\in (0,1)$as$$N\rightarrow \infty $$ $N\to \infty$. We show that this asymptotics holds universally if$$\mathbb {E}[e^{\gamma |X_k|}]<\infty $$ $E\left[e^{\gamma |X_k|}\right]<\infty$for some$$\gamma >2q$$ $\gamma >2q$. As a consequence, we establish the universality for the tightness of the normalized secular coefficients$$A_N(\log (1+N))^{1/4}$$ $A_N{(log(1+N))}^{1/4}$, generalizing a result of Najnudel, Paquette, and Simm. Another corollary is the almost sure regularity of some critical non-Gaussian holomorphic chaos in appropriate Sobolev spaces. Moreover, we characterize the asymptotics of$$\mathbb {E}[|A_N|^{2q}]$$ $E\left[\right|A_N{|}^{2q}]$for$$|X_k|$$ $|X_k|$following a stretched exponential distribution with an arbitrary scale parameter, which exhibits a completely different behavior and underlying mechanism from the Gaussian universality regime. As a result, we unveil a double-layer phase transition around the critical case of exponential tails. Our proofs combine Harper’s robust approach with a careful analysis of the (possibly random) leading terms in the monomial decomposition of$$A_N$$ $A_N$. 

   more » « less