5 papers
Iterative Randomized Rounding for Better-Than-2 k-Median Approximation
Jarosław Byrka, Yuhao Guo, Yang Hu +5
We study the classic -median problem and refine the iterative rounding framework recently introduced by Byrka, Guo, Hu, Li, Wan, and Wang [FOCS'26], which yields a $(2+\varepsil…
Decisive Margins in Differentially Private Voting
Quentin Hillebrand, Pasin Manurangsi, Vorapong Suppakitpaisarn +1
Differential privacy protects individual voting records by injecting randomness into the published outcome, but this noise can lead to erroneous results when an election is close.…
Parsimonious Learning-Augmented Online Metric Matching
Yongho Shin, Phanu Vajanopath
Learning-augmented algorithms have received significant attention in recent years, particularly in the context of online optimization. Motivated by the high computational cost of g…
The Price of Privacy For Approximating Max-CSP
Prathamesh Dharangutte, Jingcheng Liu, Pasin Manurangsi +3
We study approximation algorithms for Maximum Constraint Satisfaction Problems (Max-CSPs) under differential privacy (DP) where the constraints are considered sensitive data. Infor…
Improved Differentially Private Algorithms for Rank Aggregation
Quentin Hillebrand, Pasin Manurangsi, Vorapong Suppakitpaisarn +1
Rank aggregation is a task of combining the rankings of items from multiple users into a single ranking that best represents the users' rankings. Alabi et al. (AAAI'22) presents di…