{"ID":2899476,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.00442","arxiv_id":"2507.00442","title":"Convex Submodular Minimization with Indicator Variables","abstract":"We study a general class of convex submodular optimization problems with indicator variables. Many applications such as the problem of inferring Markov random fields (MRFs) with a sparsity or robustness prior can be naturally modeled in this form. We show that these problems can be reduced to binary submodular minimization problems, possibly after a suitable reformulation, and thus are strongly polynomially solvable. %We also discuss the implication of our results in the case of quadratic objectives. Furthermore, we develop a parametric approach for computing the associated extreme bases under certain smoothness conditions. This leads to a fast solution method, whose efficiency is demonstrated through numerical experiments.","short_abstract":"We study a general class of convex submodular optimization problems with indicator variables. Many applications such as the problem of inferring Markov random fields (MRFs) with a sparsity or robustness prior can be naturally modeled in this form. We show that these problems can be reduced to binary submodular minimiza...","url_abs":"https://arxiv.org/abs/2507.00442","url_pdf":"https://arxiv.org/pdf/2507.00442v2","authors":"[\"Andres Gomez\",\"Shaoning Han\"]","published":"2025-07-01T05:49:00Z","proceeding":"math.OC","tasks":"[\"math.OC\"]","methods":"[]","has_code":false}