Solving Positive Linear Programs with Differential Privacy

We study differentially private approximation algorithms for positive linear programs (LPs with nonnegative coefficients and variables), focusing on the fundamental families of packing, covering, and mixed packing-covering formulations. We focus on the high-sensitivity, constraint-private regime of Hsu-Roth-Roughgarden-Ullman (ICALP 2014), where neighboring instances may differ by an arbitrary single constraint, so one cannot hope to approximately satisfy every constraint under privacy. We give private solvers that return approximate solutions while violating only a controlled number of constraints. Our algorithms improve the prior instance-dependent guarantees, and also yield new data-independent bounds that depend only on the dimension. Our techniques involve a dense multiplicative weights update method developed from a regularized dual viewpoint, which we analyze in a way that exploits structure specific to positive LPs.

When computers solve complex logistical problems—like distributing goods or scheduling tasks—they often rely on highly sensitive data. The primary challenge is that strictly satisfying every single rule or constraint in these scenarios can accidentally expose an individual's private information. To tackle this, we developed new algorithms that intentionally allow a strictly controlled number of rules to be bent to preserve user privacy. Using a specialized mathematical approach, our system finds highly accurate solutions while guaranteeing that no single person's data can be leaked or reverse-engineered, all while minimizing the number of broken rules. Ultimately, this research provides a safer, more reliable way to solve large-scale optimization problems. By outperforming previous approaches, our methods empower institutions to streamline their operations without ever compromising user privacy.