42 citations · 110 across the 24 of their papers we have counts for
27 papers
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…
Large-Scale Graph Building in Dynamic Environments: Low Latency and High Quality
Filipe Miguel Gonçalves de Almeida, CJ Carey, Hendrik Fichtenberger +8
Learning and constructing large-scale graphs has attracted attention in recent decades, resulting in a rich literature that introduced various systems, tools, and algorithms. Grale…
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…
Fairness in Submodular Maximization over a Matroid Constraint
Marwa El Halabi, Jakub Tarnawski, Ashkan Norouzi-Fard +1
Submodular maximization over a matroid constraint is a fundamental problem with various applications in machine learning. Some of these applications involve decision-making over da…
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…
Fairness in Streaming Submodular Maximization over a Matroid Constraint
Marwa El Halabi, Federico Fusco, Ashkan Norouzi-Fard +2
Streaming submodular maximization is a natural model for the task of selecting a representative subset from a large-scale dataset. If datapoints have sensitive attributes such as g…
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…
Near-Optimal Correlation Clustering with Privacy
Vincent Cohen-Addad, Chenglin Fan, Silvio Lattanzi +4
Correlation clustering is a central problem in unsupervised learning, with applications spanning community detection, duplicate detection, automated labelling and many more. In the…
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…
Streaming Belief Propagation for Community Detection
Yuchen Wu, MohammadHossein Bateni, Andre Linhares +4
The community detection problem requires to cluster the nodes of a network into a small number of well-connected "communities". There has been substantial recent progress in charac…
Fast and Accurate -means++ via Rejection Sampling
Vincent Cohen-Addad, Silvio Lattanzi, Ashkan Norouzi-Fard +2
-means++ \cite{arthur2007k} is a widely used clustering algorithm that is easy to implement, has nice theoretical guarantees and strong empirical performance. Despite its wide a…
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…
Fairness in Streaming Submodular Maximization: Algorithms and Hardness
Marwa El Halabi, Slobodan Mitrović, Ashkan Norouzi-Fard +2
Submodular maximization has become established as the method of choice for the task of selecting representative and diverse summaries of data. However, if datapoints have sensitive…
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…
Beyond -Approximation for Submodular Maximization on Massive Data Streams
Ashkan Norouzi-Fard, Jakub Tarnawski, Slobodan Mitrović +3
Many tasks in machine learning and data mining, such as data diversification, non-parametric learning, kernel machines, clustering etc., require extracting a small but representati…
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…