English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

It was observed in \citet{gupta2009differentially} that the Set Cover problemhas strong impossibility results under differential privacy. In our work, weobserve that these hardness results dissolve when we turn to the Partial SetCover problem, where we only need to cover a $\rho$-fraction of the elements inthe universe, for some $\rho\in(0,1)$. We show that this relaxation enables usto avoid the impossibility results: under loose conditions on the input setsystem, we give differentially private algorithms which output an explicit setcover with non-trivial approximation guarantees. In particular, this is thefirst differentially private algorithm which outputs an explicit set cover.  Using our algorithm for Partial Set Cover as a subroutine, we give adifferentially private (bicriteria) approximation algorithm for a facilitylocation problem which generalizes $k$-center/$k$-supplier with outliers. Likewith the Set Cover problem, no algorithm has been able to give non-trivialguarantees for $k$-center/$k$-supplier-type facility location problems due tothe high sensitivity and impossibility results. Our algorithm shows thatrelaxing the covering requirement to serving only a $\rho$-fraction of thepopulation, for $\rho\in(0,1)$, enables us to circumvent the inherent hardness.Overall, our work is an important step in tackling and understandingimpossibility results in private combinatorial optimization.

Differentially Private Partial Set Cover with Applications to Facility Location