{"ID":2851466,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.19191","arxiv_id":"2510.19191","title":"Supermodular Maximization with Cardinality Constraints","abstract":"Let $V$ be a finite set of $n$ elements, $f: 2^V \\rightarrow \\mathbb{R}_+$ be a nonnegative monotone supermodular function, and $k$ be a positive integer no greater than $n$. This paper addresses the problem of maximizing $f(S)$ over all subsets $S \\subseteq V$ subject to the cardinality constraint $|S| = k$ or $|S|\\le k$. Let $r$ be a constant integer. The function $f$ is assumed to be {\\em $r$-decomposable}, meaning there exist $m\\,(\\ge1)$ subsets $V_1, \\dots, V_m$ of $V$, each with a cardinality at most $r$, and a corresponding set of nonnegative supermodular functions $f_i : 2^{V_i} \\rightarrow \\mathbb{R}_+$, $i=1,\\ldots,m$ such that $f(S) =\\sum_{i=1}^m f_i(S \\cap V_i)$ holds for each $S \\subseteq V$. Given $r$ as an input, we present a polynomial-time $O(n^{(r-1)/2})$-approximation algorithm for this maximization problem, which does not require prior knowledge of the specific decomposition. When the decomposition $(V_i,f_i)_{i=1}^m$ is known, an additional connectivity requirement is introduced to the problem. Let $G$ be the graph with vertex set $V$ and edge set $\\cup_{i=1}^m \\{uv:u,v\\in V_i,u\\neq v\\}$. The cardinality constrained solution set $S$ is required to induce a connected subgraph in $G$. This model generalizes the well-known problem of finding the densest connected $k$-subgraph. We propose a polynomial time $O(n^{(r-1)/2})$-approximation algorithm for this generalization. Notably, this algorithm gives an $O(n^{1/2})$-approximation for the densest connected $k$-subgraph problem, improving upon the previous best-known approximation ratio of $O(n^{2/3})$.","short_abstract":"Let $V$ be a finite set of $n$ elements, $f: 2^V \\rightarrow \\mathbb{R}_+$ be a nonnegative monotone supermodular function, and $k$ be a positive integer no greater than $n$. This paper addresses the problem of maximizing $f(S)$ over all subsets $S \\subseteq V$ subject to the cardinality constraint $|S| = k$ or $|S|\\le...","url_abs":"https://arxiv.org/abs/2510.19191","url_pdf":"https://arxiv.org/pdf/2510.19191v1","authors":"[\"Xujin Chen\",\"Xiaodong Hu\",\"Changjun Wang\",\"Qingjie Ye\"]","published":"2025-10-22T02:56:42Z","proceeding":"math.OC","tasks":"[\"math.OC\",\"cs.DM\",\"cs.DS\",\"math.CO\"]","methods":"[]","has_code":false}