How to Make Your Approximation Algorithm Private: A Black-Box Differentially-Private Transformation for Tunable Approximation Algorithms of Functions with Low Sensitivity.
Jeremiah BlockiElena GrigorescuTamalika MukherjeeSamson ZhouPublished in: APPROX/RANDOM (2023)
Keyphrases
- approximation algorithms
- approximation ratio
- np hard
- black box
- vertex cover
- worst case
- set cover
- polynomial time approximation
- constant factor
- approximation schemes
- randomized algorithms
- error bounds
- special case
- greedy algorithm
- differentially private
- learning algorithm
- database
- upper bound
- primal dual
- integrality gap
- solution space
- lower bound
- feature space
- computational complexity
- objective function
- data sets