Portal de Periódicos da CAPES

Privately Solving Linear Programs

2014; Springer Science+Business Media; Linguagem: Inglês

10.1007/978-3-662-43948-7_51

1611-3349

Justin Hsu, Aaron Roth, Tim Roughgarden, Jonathan Ullman,

Complexity and Algorithms in Graphs

In this paper, we initiate the systematic study of solving linear programs under differential privacy. The first step is simply to define the problem: to this end, we introduce several natural classes of private linear programs that capture different ways sensitive data can be incorporated into a linear program. For each class of linear programs we give an efficient, differentially private solver based on the multiplicative weights framework, or we give an impossibility result.