research
∙
05/26/2023
Submodular Minimax Optimization: Finding Effective Sets
Despite the rich existing literature about minimax optimization in conti...
share
research
∙
10/12/2022
Resolving the Approximability of Offline and Online Non-monotone DR-Submodular Maximization over General Convex Sets
In recent years, maximization of DR-submodular continuous functions beca...
research
∙
04/11/2022
Submodular Maximization Subject to Matroid Intersection on the Fly
Despite a surge of interest in submodular maximization in the data strea...
research
∙
04/07/2022
Maximizing Sums of Non-monotone Submodular and Linear Functions: Understanding the Unconstrained Case
Motivated by practical applications, recent works have considered maximi...
research
∙
02/07/2022
Using Partial Monotonicity in Submodular Maximization
Over the last two decades, submodular function maximization has been the...
research
∙
09/13/2021
Maximum Matching sans Maximal Matching: A New Approach for Finding Maximum Matchings in the Data Stream Model
The problem of finding a maximum size matching in a graph (known as the ...
research
∙
07/15/2021
Streaming Submodular Maximization with Matroid and Matching Constraints
Recent progress in (semi-)streaming algorithms for monotone submodular f...
research
∙
06/09/2021
Submodular + Concave
It has been well established that first order optimization methods can c...
research
∙
04/06/2021
The Power of Subsampling in Submodular Maximization
We propose subsampling as a unified algorithmic technique for submodular...
research
∙
09/29/2020
Simultaneous Greedys: A Swiss Army Knife for Constrained Submodular Maximization
In this paper, we present SimultaneousGreedys, a deterministic algorithm...
research
∙
06/21/2020
Continuous Submodular Maximization: Beyond DR-Submodularity
In this paper, we propose the first continuous optimization algorithms t...
research
∙
03/30/2020
The One-way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness
We consider the classical problem of maximizing a monotone submodular fu...
research
∙
02/10/2020
Regularized Submodular Maximization at Scale
In this paper, we propose scalable methods for maximizing a regularized ...
research
∙
02/09/2020
Streaming Submodular Maximization under a k-Set System Constraint
In this paper, we propose a novel framework that converts streaming algo...
research
∙
06/26/2019
Making a Sieve Random: Improved Semi-Streaming Algorithm for Submodular Maximization under a Cardinality Constraint
In this paper we consider the problem of maximizing a non-negative submo...
research
∙
06/11/2019
Almost Optimal Semi-streaming Maximization for k-Extendible Systems
In this paper we consider the problem of finding a maximum weight set su...
research
∙
04/19/2019
Submodular Maximization Beyond Non-negativity: Guarantees, Fast Algorithms, and Applications
It is generally believed that submodular functions -- and the more gener...
research
∙
02/15/2019
Adaptive Sequence Submodularity
In many machine learning applications, one needs to interactively select...
research
∙
11/15/2018
Unconstrained Submodular Maximization with Constant Adaptive Complexity
In this paper, we consider the unconstrained submodular maximization pro...
research
∙
10/09/2018
Guess Free Maximization of Submodular and Linear Sums
We consider the problem of maximizing the sum of a monotone submodular f...
research
∙
07/15/2018
Deterministic (1/2 + ε)-Approximation for Submodular Maximization over a Matroid
We study the problem of maximizing a monotone submodular function subjec...
research
∙
07/15/2018
Online Submodular Maximization: Beating 1/2 Made Simple
The Submodular Welfare Maximization problem (SWM) captures an important ...
research
∙
02/26/2018
Submodularity on Hypergraphs: From Sets to Sequences
In a nutshell, submodular functions encode an intuitive notion of dimini...
research
∙
02/20/2018
Do Less, Get More: Streaming Submodular Maximization with Subsampling
In this paper, we develop the first one-pass streaming algorithm for sub...
research
∙
07/13/2017
Weakly Submodular Maximization Beyond Cardinality Constraints: Does Randomization Help Greedy?
Submodular functions are a broad class of set functions, which naturally...
research
∙
03/08/2017