Monotone Closure of Relaxed Constraints in Submodular Optimization: Connections Between Minimization and Maximization
Abstract
It is becoming increasingly evident that many machine learning problems may be reduced to submodular optimization. Previous work addresses generic discrete approaches and specific relaxations. In this work, we take a generic view from a relaxation perspective, showing a relaxation formulation and simple rounding strategy that, based on the monotone closure of relaxed constraints, reveals analogies between minimization and maximization problems. We develop a continuous relaxation methodology for constrained submodular problems applicable for multiple types of constraints, establishing connections between minimization and maximization. Many important constraints, including matroid, cardinality, covers, cuts, paths, and matchings, can be expressed in our framework.
Cite
Text
Iyer et al. "Monotone Closure of Relaxed Constraints in Submodular Optimization: Connections Between Minimization and Maximization." Conference on Uncertainty in Artificial Intelligence, 2014.Markdown
[Iyer et al. "Monotone Closure of Relaxed Constraints in Submodular Optimization: Connections Between Minimization and Maximization." Conference on Uncertainty in Artificial Intelligence, 2014.](https://mlanthology.org/uai/2014/iyer2014uai-monotone/)BibTeX
@inproceedings{iyer2014uai-monotone,
title = {{Monotone Closure of Relaxed Constraints in Submodular Optimization: Connections Between Minimization and Maximization}},
author = {Iyer, Rishabh K. and Jegelka, Stefanie and Bilmes, Jeff A.},
booktitle = {Conference on Uncertainty in Artificial Intelligence},
year = {2014},
pages = {360-369},
url = {https://mlanthology.org/uai/2014/iyer2014uai-monotone/}
}