Loading…
Differentially private submodular maximization with a cardinality constraint over the integer lattice
The exploration of submodular optimization problems on the integer lattice offers a more precise approach to handling the dynamic interactions among repetitive elements in practical applications. In today’s data-driven world, the importance of efficient and reliable privacy-preserving algorithms has...
Saved in:
Published in: | Journal of combinatorial optimization 2024-05, Vol.47 (4), Article 58 |
---|---|
Main Authors: | , , , |
Format: | Article |
Language: | English |
Subjects: | |
Citations: | Items that this one cites |
Online Access: | Get full text |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Summary: | The exploration of submodular optimization problems on the integer lattice offers a more precise approach to handling the dynamic interactions among repetitive elements in practical applications. In today’s data-driven world, the importance of efficient and reliable privacy-preserving algorithms has become paramount for safeguarding sensitive information. In this paper, we delve into the DR-submodular and lattice submodular maximization problems subject to cardinality constraints on the integer lattice, respectively. For DR-submodular functions, we devise a differential privacy algorithm that attains a
(
1
-
1
/
e
-
ρ
)
-approximation guarantee with additive error
O
(
r
σ
ln
|
N
|
/
ϵ
)
for any
ρ
>
0
, where
N
is the number of groundset,
ϵ
is the privacy budget,
r
is the cardinality constraint, and
σ
is the sensitivity of a function. Our algorithm preserves
O
(
ϵ
r
2
)
-differential privacy. Meanwhile, for lattice submodular functions, we present a differential privacy algorithm that achieves a
(
1
-
1
/
e
-
O
(
ρ
)
)
-approximation guarantee with additive error
O
(
r
σ
ln
|
N
|
/
ϵ
)
. We evaluate their effectiveness using instances of the combinatorial public projects problem and the budget allocation problem within the bipartite influence model. |
---|---|
ISSN: | 1382-6905 1573-2886 |
DOI: | 10.1007/s10878-024-01158-2 |