Differentially private submodular maximization with a cardinality constraint over the integer lattice

Jiaming Hu (), Dachuan Xu (), Donglei Du () and Cuixia Miao ()
Additional contact information
Jiaming Hu: Beijing University of Technology
Dachuan Xu: Beijing University of Technology
Donglei Du: University of New Brunswick
Cuixia Miao: Qufu Normal University

Journal of Combinatorial Optimization, 2024, vol. 47, issue 4, No 5, 24 pages

Abstract: Abstract 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-\rho )$$ ( 1 - 1 / e - ρ ) -approximation guarantee with additive error $$O(r\sigma \ln |N|/\epsilon )$$ O ( r σ ln | N | / ϵ ) for any $$\rho >0$$ ρ > 0 , where N is the number of groundset, $$\epsilon $$ ϵ is the privacy budget, r is the cardinality constraint, and $$\sigma $$ σ is the sensitivity of a function. Our algorithm preserves $$O(\epsilon r^{2})$$ O ( ϵ r 2 ) -differential privacy. Meanwhile, for lattice submodular functions, we present a differential privacy algorithm that achieves a $$(1-1/e-O(\rho ))$$ ( 1 - 1 / e - O ( ρ ) ) -approximation guarantee with additive error $$O(r\sigma \ln |N|/\epsilon )$$ 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.

Keywords: DR-submodular; Lattice submodular; Cardinality constraint; Differentially private; Exponential mechanism (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-024-01158-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:47:y:2024:i:4:d:10.1007_s10878-024-01158-2

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-024-01158-2

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().