40 citations · 225 across the 33 of their papers we have counts for
23 papers · 1 filter
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…
Accelerated Relax-and-Round for Concave Coverage Problems
Matthew Fahrbach, Mehraneh Liaee, Morteza Zadimoghaddam
We present an accelerated relax-and-round algorithm for concave coverage problems, which generalize the classic maximum coverage problem. Building on the relax-and-round framework…
Scalable contribution bounding to achieve privacy
Vincent Cohen-Addad, Alessandro Epasto, Jason Lee +1
In modern datasets, where single records can have multiple owners, enforcing user-level differential privacy requires capping each user's total contribution. This "contribution bou…
Scalable Private Partition Selection via Adaptive Weighting
Justin Y. Chen, Vincent Cohen-Addad, Alessandro Epasto +1
In the differentially private partition selection problem (a.k.a. private set union, private key discovery), users hold subsets of items from an unbounded universe. The goal is to…
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…