10 papers
Differentially Private Multicolor Discrepancy and Fair Division of Indivisible Goods
Max Dupré la Tour
We study the fair division of indivisible goods under pure differential privacy, continuing the line of work initiated by Manurangsi and Suksompong. For agents with nonnegative…
Subquadratic Subsidies for Nonnegative or Nonpositive Valuations
Max Dupré la Tour, Mashbat Suzuki
We study envy-freeness with subsidies for indivisible items beyond additive valuations. Assuming that every single-item marginal value lies in , we prove that a total subsi…
Balanced Fair Division for Three Agents under General Valuations and Laminar Constraints
Max Dupré la Tour
We study fair allocations of indivisible items under general set valuations. We prove that every instance with three agents and arbitrary real-valued valuations admits a balanced a…
Random Serial Dictatorship is -Envy-Free
Frank Connor, Max Dupré la Tour, Louis-Roy Langevin +4
We analyze the house allocation problem, in which a set of agents must be matched to a set of objects for which they have cardinal utilities. A central mechanism for this problem i…
Bad News for Couples: Bounds for Fair Division of Indivisible Items among Groups
Max Dupré la Tour
We consider the problem of fairly allocating indivisible items to couples, where each couple consists of two agents with distinct additive valuations. We show that there exist bina…
-Leaf Powers Cannot be Characterized by a Finite Set of Forbidden Induced Subgraphs for
Max Dupré la Tour, Manuel Lafond, Ndiamé Ndiaye +1
A graph is a -leaf power if there is a tree whose leaves are the vertices of with the property that a pair of leaves and induce an edge in if and o…
Faster and Simpler Greedy Algorithm for -Median and -Means
Max Dupré la Tour, David Saulpic
Clustering problems such as -means and -median are staples of unsupervised learning, and many algorithmic techniques have been developed to tackle their numerous aspects. In…
Fully Dynamic k-Means Coreset in Near-Optimal Update Time
Max Dupré la Tour, Monika Henzinger, David Saulpic
We study in this paper the problem of maintaining a solution to -median and -means clustering in a fully dynamic setting. To do so, we present an algorithm to efficiently mai…
Making Old Things New: A Unified Algorithm for Differentially Private Clustering
Max Dupré la Tour, Monika Henzinger, David Saulpic
As a staple of data analysis and unsupervised learning, the problem of private clustering has been widely studied under various privacy models. Centralized differential privacy is…
Differential Privacy for Clustering Under Continual Observation
Max Dupré la Tour, Monika Henzinger, David Saulpic
We consider the problem of clustering privately a dataset in that undergoes both insertion and deletion of points. Specifically, we give an -differentia…