Abstract We study the problem of () as defined by Bodek and Feldman (Maximizing sums of non-monotone submodular and linear functions: understanding the unconstrained case, arXiv:2204.03412 , 2022): given query access to a non-negative submodular function $$f:2^{{\mathcal {N}}}\rightarrow {\mathbb {R}}_{\ge 0}$$ f : 2 N → R ≥ 0 and a linear function $$\ell :2^{{\mathcal {N}}}\rightarrow {\mathbb {R}}$$ ℓ : 2 N → R over the same ground set $${\mathcal {N}}$$ N , output a set $$T\subseteq {\mathcal {N}}$$ T ⊆ N approximately maximizing the sum $$f(T)+\ell (T)$$ f ( T ) + ℓ ( T ) . An algorithm is said to provide an $$(\alpha ,\beta )$$ ( α , β ) -approximation for if it outputs a set T such that $${\mathbb {E}}[f(T)+\ell (T)]\ge \max _{S\subseteq {\mathcal {N}}}[\alpha \cdot f(S)+\beta \cdot \ell (S)]$$ E [ f ( T ) + ℓ ( T ) ] ≥ max S ⊆ N [ α · f ( S ) + β · ℓ ( S ) ] . We also consider the setting where S and T are constrained to be independent in a given matroid, which we refer to as Constrained (). The special case of with monotone f has been extensively studied (Sviridenko et al. in Math Oper Res 42(4):1197–1218, 2017; Feldman in Algorithmica 83(3):853–878, 2021; Harshaw et al., in: International conference on machine learning, PMLR, 2634–2643, 2019), whereas we are aware of only one prior work that studies with non-monotone f (Lu et al. in Optimization 1–27, 2023), and that work constrains $$\ell $$ ℓ to be non-positive. In this work, we provide improved $$(\alpha ,\beta )$$ ( α , β )<

Given a set of discrete probability distributions, the minimum entropy coupling is the minimum entropy joint distribution that has the input distributions as its marginals. This has immediate relevance to tasks such as entropic causal inference for causal graph discovery and bounding mutual information between variables that we observe separately. Since finding the minimum entropy coupling is NP-Hard, various works have studied approximation algorithms. The work of [Compton, 2022] shows that the greedy coupling algorithm of [Kocaoglu et al., 2017a] is always within $\log_2(e)$ $\approx$ 1.44 bits of the optimal coupling. Moreover, they show that it is impossible to obtain a better approximation guarantee using the majorization lower-bound that all prior works have used: thus establishing a majorization barrier. In this work, we break the majorization barrier by designing a stronger lower-bound that we call the profile method. Using this profile method, we are able to show that the greedy algorithm is always within $\log_2(e)/e$ $\approx$ 0.53 bits of optimal for coupling two distributions (previous best-known bound is within 1 bit), and within $(1 + \log_2(e))/2$ $\approx$ 1.22 bits for coupling any number of distributions (previous best-known bound is within 1.44 bits). We also examine a generalization of the minimum entropy coupling problem: Concave Minimum-Cost Couplings. We are able to obtain similar guarantees for this generalization in terms of the concave cost function. Additionally, we make progress on the open problem of [Kovačević et al., 2015] regarding NP membership of the minimum entropy coupling problem by showing that any hardness of minimum entropy coupling beyond NP comes from the difficulty of computing arithmetic in the complexity class NP. Finally, we present exponential-time algorithms for computing the exactly optimal solution. We experimentally observe that our new profile method lower bound is not only helpful for analyzing the greedy approximation algorithm, but also for improving the speed of our new backtracking-based exact algorithm.

We analyze the touring regions problem: find a (1+ε)-approximate Euclidean shortest path in d-dimensional space that starts at a given starting point, ends at a given ending point, and visits given regions R₁, R₂, R₃, … , R_n in that order. Our main result is an O (n/√ε log{1/ε} + 1/ε)-time algorithm for touring disjoint disks. We also give an O(min(n/ε, n²/√ε))-time algorithm for touring disjoint two-dimensional convex fat bodies. Both of these results naturally generalize to larger dimensions; we obtain O(n/{ε^{d-1}} log²1/ε + 1/ε^{2d-2}) and O(n/ε^{2d-2})-time algorithms for touring disjoint d-dimensional balls and convex fat bodies, respectively.

We study the problem of Regularized Unconstrained Submodular Maximization (RegularizedUSM) as defined by Bodek and Feldman [BF22]. In this problem, you are given a non-monotone non-negative submodular function $f:2^{\mathcal N}\to \mathbb R_{\ge 0}$ and a linear function $\ell:2^{\mathcal N}\to \mathbb R$ over the same ground set $\mathcal N$, and the objective is to output a set $T\subseteq \mathcal N$ approximately maximizing the sum $f(T)+\ell(T)$. Specifically, an algorithm is said to provide an $(α,β)$-approximation for RegularizedUSM if it outputs a set $T$ such that $\mathbb E[f(T)+\ell(T)]\ge \max_{S\subseteq \mathcal N}[α\cdot f(S)+β\cdot \ell(S)]$. We also study the setting where $S$ and $T$ are subject to a matroid constraint, which we refer to as Regularized Constrained Submodular Maximization (RegularizedCSM). For both RegularizedUSM and RegularizedCSM, we provide improved $(α,β)$-approximation algorithms for the cases of non-positive $\ell$, non-negative $\ell$, and unconstrained $\ell$. In particular, for the case of unconstrained $\ell$, we are the first to provide nontrivial $(α,β)$-approximations for RegularizedCSM, and the $α$ we obtain for RegularizedUSM is superior to that of [BF22] for all $β\in (0,1)$. In addition to approximation algorithms, we provide improved inapproximability results for all of the aforementioned cases. In particular, we show that the $α$ our algorithm obtains for RegularizedCSM with unconstrained $\ell$ is tight for $β\ge \frac{e}{e+1}$. We also show 0.478-inapproximability for maximizing a submodular function where $S$ and $T$ are subject to a cardinality constraint, improving the long-standing 0.491-inapproximability result due to Gharan and Vondrak [GV10].