42 citations · 110 across the 24 of their papers we have counts for
19 papers · 1 filter
Consistent Submodular Maximization with Full Foresight
Eric Balkanski, Paul Dütting, Federico Fusco +4
Online algorithms with bounded recourse face three intertwined obstacles: uncertainty about the future, computational limits, and a limited budget for changes. We ask a fundamental…
A General Framework for Dynamic Consistent Submodular Maximization
Paul Dütting, Federico Fusco, Silvio Lattanzi +3
Consistency is an important property in dynamic submodular maximization and entails maintaining a near-optimal solution at all times, making only a small number of adjustments to t…
Clustering with Label Consistency
Diptarka Chakraborty, Hendrik Fichtenberger, Bernhard Haeupler +3
Designing efficient, effective, and consistent metric clustering algorithms is a significant challenge attracting growing attention. Traditional approaches focus on the stability o…
The Cost of Consistency: Submodular Maximization with Constant Recourse
Paul Dütting, Federico Fusco, Silvio Lattanzi +3
In this work, we study online submodular maximization, and how the requirement of maintaining a stable solution impacts the approximation. In particular, we seek bounds on the best…
Consistent Submodular Maximization
Paul Dütting, Federico Fusco, Silvio Lattanzi +2
Maximizing monotone submodular functions under cardinality constraints is a classic optimization task with several applications in data mining and machine learning. In this paper w…
Fully Dynamic Submodular Maximization over Matroids
Paul Dütting, Federico Fusco, Silvio Lattanzi +2
Maximizing monotone submodular functions under a matroid constraint is a classic algorithmic problem with multiple applications in data mining and machine learning. We study this c…
Deletion Robust Non-Monotone Submodular Maximization over Matroids
Paul Dütting, Federico Fusco, Silvio Lattanzi +2
Maximizing a submodular function is a fundamental task in machine learning and in this paper we study the deletion robust version of the problem under the classic matroids constrai…
Submodular Maximization Subject to Matroid Intersection on the Fly
Moran Feldman, Ashkan Norouzi-Fard, Ola Svensson +1
Despite a surge of interest in submodular maximization in the data stream model, there remain significant gaps in our knowledge about what can be achieved in this setting, especial…
Deletion Robust Submodular Maximization over Matroids
Paul Dütting, Federico Fusco, Silvio Lattanzi +2
Maximizing a monotone submodular function is a fundamental task in machine learning. In this paper, we study the deletion robust version of the problem under the classic matroids c…
Streaming Submodular Maximization under Matroid Constraints
Moran Feldman, Paul Liu, Ashkan Norouzi-Fard +2
Recent progress in (semi-)streaming algorithms for monotone submodular function maximization has led to tight results for a simple cardinality constraint. However, current techniqu…
Correlation Clustering in Constant Many Parallel Rounds
Vincent Cohen-Addad, Silvio Lattanzi, Slobodan Mitrović +3
Correlation clustering is a central topic in unsupervised learning, with many applications in ML and data mining. In correlation clustering, one receives as input a signed graph an…
Consistent k-Clustering for General Metrics
Hendrik Fichtenberger, Silvio Lattanzi, Ashkan Norouzi-Fard +1
Given a stream of points in a metric space, is it possible to maintain a constant approximate clustering by changing the cluster centers only a small number of times during the ent…
Fully Dynamic Algorithm for Constrained Submodular Optimization
Silvio Lattanzi, Slobodan Mitrović, Ashkan Norouzi-Fard +2
The task of maximizing a monotone submodular function under a cardinality constraint is at the core of many machine learning and data mining applications, including data summarizat…
The One-way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness
Moran Feldman, Ashkan Norouzi-Fard, Ola Svensson +1
We consider the classical problem of maximizing a monotone submodular function subject to a cardinality constraint, which, due to its numerous applications, has recently been studi…
Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples
Michael Kapralov, Slobodan Mitrović, Ashkan Norouzi-Fard +1
Given a source of iid samples of edges of an input graph with vertices and edges, how many samples does one need to compute a constant factor approximation to the maxim…
Streaming Robust Submodular Maximization: A Partitioned Thresholding Approach
Slobodan Mitrović, Ilija Bogunovic, Ashkan Norouzi-Fard +2
We study the classical problem of maximizing a monotone submodular function subject to a cardinality constraint k, with two additional twists: (i) elements arrive in a streaming fa…
Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms
Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson +1
Clustering is a classic topic in optimization with -means being one of the most fundamental such problems. In the absence of any restrictions on the input, the best known algori…
An Efficient Streaming Algorithm for the Submodular Cover Problem
Ashkan Norouzi-Fard, Abbas Bazzi, Marwa El Halabi +3
We initiate the study of the classical Submodular Cover (SC) problem in the data streaming model which we refer to as the Streaming Submodular Cover (SSC). We show that any single…
Dynamic Facility Location via Exponential Clocks
Hyung-Chan An, Ashkan Norouzi-Fard, Ola Svensson
The \emph{dynamic facility location problem} is a generalization of the classic facility location problem proposed by Eisenstat, Mathieu, and Schabanel to model the dynamics of evo…