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...

Full description

Saved in:
Bibliographic Details
Published in:Journal of combinatorial optimization 2024-05, Vol.47 (4), Article 58
Main Authors: Hu, Jiaming, Xu, Dachuan, Du, Donglei, Miao, Cuixia
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!
cited_by
cites cdi_FETCH-LOGICAL-c270t-cbb0a046390bbd3ed262d4fdfd490c38df752fed924004a9b985f12b872571253
container_end_page
container_issue 4
container_start_page
container_title Journal of combinatorial optimization
container_volume 47
creator Hu, Jiaming
Xu, Dachuan
Du, Donglei
Miao, Cuixia
description 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.
doi_str_mv 10.1007/s10878-024-01158-2
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_3041897439</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>3041897439</sourcerecordid><originalsourceid>FETCH-LOGICAL-c270t-cbb0a046390bbd3ed262d4fdfd490c38df752fed924004a9b985f12b872571253</originalsourceid><addsrcrecordid>eNp9kEtLAzEUhQdRsFb_gKuA69Gbx0ySpdQnFNzoOmQmiU2ZR03Sav31Rkdw5-qeC-dc7vmK4hzDJQbgVxGD4KIEwkrAuBIlOShmuOK0JELUh1lTQcpaQnVcnMS4BoCs2aywN945G-yQvO66PdoEv9PJorht-tFsOx1Qrz987z918uOA3n1aIY1aHYwfdOfTHrXjEFPQfkho3NmA0sqivNjXrDudkm_taXHkdBft2e-cFy93t8-Lh3L5dP-4uF6WLeGQyrZpQAOrqYSmMdQaUhPDnHGGSWipMI5XxFkjCQNgWjZSVA6TRnBScUwqOi8uprubML5tbUxqPW5D_jMqCgwLyRmV2UUmVxvGGIN1KrfuddgrDOobp5pwqoxT_eBUJIfoFIrZPORuf6f_SX0BZQ96PA</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>3041897439</pqid></control><display><type>article</type><title>Differentially private submodular maximization with a cardinality constraint over the integer lattice</title><source>Springer Nature</source><creator>Hu, Jiaming ; Xu, Dachuan ; Du, Donglei ; Miao, Cuixia</creator><creatorcontrib>Hu, Jiaming ; Xu, Dachuan ; Du, Donglei ; Miao, Cuixia</creatorcontrib><description>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 ρ &gt; 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.</description><identifier>ISSN: 1382-6905</identifier><identifier>EISSN: 1573-2886</identifier><identifier>DOI: 10.1007/s10878-024-01158-2</identifier><language>eng</language><publisher>New York: Springer US</publisher><subject>Algorithms ; Approximation ; Budgets ; Combinatorial analysis ; Combinatorics ; Convex and Discrete Geometry ; Integers ; Mathematical analysis ; Mathematical Modeling and Industrial Mathematics ; Mathematics ; Mathematics and Statistics ; Maximization ; Operations Research/Decision Theory ; Optimization ; Privacy ; Theory of Computation</subject><ispartof>Journal of combinatorial optimization, 2024-05, Vol.47 (4), Article 58</ispartof><rights>The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2024. Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><cites>FETCH-LOGICAL-c270t-cbb0a046390bbd3ed262d4fdfd490c38df752fed924004a9b985f12b872571253</cites><orcidid>0000-0003-2448-2158</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,780,784,27924,27925</link.rule.ids></links><search><creatorcontrib>Hu, Jiaming</creatorcontrib><creatorcontrib>Xu, Dachuan</creatorcontrib><creatorcontrib>Du, Donglei</creatorcontrib><creatorcontrib>Miao, Cuixia</creatorcontrib><title>Differentially private submodular maximization with a cardinality constraint over the integer lattice</title><title>Journal of combinatorial optimization</title><addtitle>J Comb Optim</addtitle><description>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 ρ &gt; 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.</description><subject>Algorithms</subject><subject>Approximation</subject><subject>Budgets</subject><subject>Combinatorial analysis</subject><subject>Combinatorics</subject><subject>Convex and Discrete Geometry</subject><subject>Integers</subject><subject>Mathematical analysis</subject><subject>Mathematical Modeling and Industrial Mathematics</subject><subject>Mathematics</subject><subject>Mathematics and Statistics</subject><subject>Maximization</subject><subject>Operations Research/Decision Theory</subject><subject>Optimization</subject><subject>Privacy</subject><subject>Theory of Computation</subject><issn>1382-6905</issn><issn>1573-2886</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2024</creationdate><recordtype>article</recordtype><recordid>eNp9kEtLAzEUhQdRsFb_gKuA69Gbx0ySpdQnFNzoOmQmiU2ZR03Sav31Rkdw5-qeC-dc7vmK4hzDJQbgVxGD4KIEwkrAuBIlOShmuOK0JELUh1lTQcpaQnVcnMS4BoCs2aywN945G-yQvO66PdoEv9PJorht-tFsOx1Qrz987z918uOA3n1aIY1aHYwfdOfTHrXjEFPQfkho3NmA0sqivNjXrDudkm_taXHkdBft2e-cFy93t8-Lh3L5dP-4uF6WLeGQyrZpQAOrqYSmMdQaUhPDnHGGSWipMI5XxFkjCQNgWjZSVA6TRnBScUwqOi8uprubML5tbUxqPW5D_jMqCgwLyRmV2UUmVxvGGIN1KrfuddgrDOobp5pwqoxT_eBUJIfoFIrZPORuf6f_SX0BZQ96PA</recordid><startdate>20240501</startdate><enddate>20240501</enddate><creator>Hu, Jiaming</creator><creator>Xu, Dachuan</creator><creator>Du, Donglei</creator><creator>Miao, Cuixia</creator><general>Springer US</general><general>Springer Nature B.V</general><scope>AAYXX</scope><scope>CITATION</scope><orcidid>https://orcid.org/0000-0003-2448-2158</orcidid></search><sort><creationdate>20240501</creationdate><title>Differentially private submodular maximization with a cardinality constraint over the integer lattice</title><author>Hu, Jiaming ; Xu, Dachuan ; Du, Donglei ; Miao, Cuixia</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c270t-cbb0a046390bbd3ed262d4fdfd490c38df752fed924004a9b985f12b872571253</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2024</creationdate><topic>Algorithms</topic><topic>Approximation</topic><topic>Budgets</topic><topic>Combinatorial analysis</topic><topic>Combinatorics</topic><topic>Convex and Discrete Geometry</topic><topic>Integers</topic><topic>Mathematical analysis</topic><topic>Mathematical Modeling and Industrial Mathematics</topic><topic>Mathematics</topic><topic>Mathematics and Statistics</topic><topic>Maximization</topic><topic>Operations Research/Decision Theory</topic><topic>Optimization</topic><topic>Privacy</topic><topic>Theory of Computation</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Hu, Jiaming</creatorcontrib><creatorcontrib>Xu, Dachuan</creatorcontrib><creatorcontrib>Du, Donglei</creatorcontrib><creatorcontrib>Miao, Cuixia</creatorcontrib><collection>CrossRef</collection><jtitle>Journal of combinatorial optimization</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Hu, Jiaming</au><au>Xu, Dachuan</au><au>Du, Donglei</au><au>Miao, Cuixia</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Differentially private submodular maximization with a cardinality constraint over the integer lattice</atitle><jtitle>Journal of combinatorial optimization</jtitle><stitle>J Comb Optim</stitle><date>2024-05-01</date><risdate>2024</risdate><volume>47</volume><issue>4</issue><artnum>58</artnum><issn>1382-6905</issn><eissn>1573-2886</eissn><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 - ρ ) -approximation guarantee with additive error O ( r σ ln | N | / ϵ ) for any ρ &gt; 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.</abstract><cop>New York</cop><pub>Springer US</pub><doi>10.1007/s10878-024-01158-2</doi><orcidid>https://orcid.org/0000-0003-2448-2158</orcidid></addata></record>
fulltext fulltext
identifier ISSN: 1382-6905
ispartof Journal of combinatorial optimization, 2024-05, Vol.47 (4), Article 58
issn 1382-6905
1573-2886
language eng
recordid cdi_proquest_journals_3041897439
source Springer Nature
subjects Algorithms
Approximation
Budgets
Combinatorial analysis
Combinatorics
Convex and Discrete Geometry
Integers
Mathematical analysis
Mathematical Modeling and Industrial Mathematics
Mathematics
Mathematics and Statistics
Maximization
Operations Research/Decision Theory
Optimization
Privacy
Theory of Computation
title Differentially private submodular maximization with a cardinality constraint over the integer lattice
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-25T20%3A54%3A56IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Differentially%20private%20submodular%20maximization%20with%20a%20cardinality%20constraint%20over%20the%20integer%20lattice&rft.jtitle=Journal%20of%20combinatorial%20optimization&rft.au=Hu,%20Jiaming&rft.date=2024-05-01&rft.volume=47&rft.issue=4&rft.artnum=58&rft.issn=1382-6905&rft.eissn=1573-2886&rft_id=info:doi/10.1007/s10878-024-01158-2&rft_dat=%3Cproquest_cross%3E3041897439%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c270t-cbb0a046390bbd3ed262d4fdfd490c38df752fed924004a9b985f12b872571253%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=3041897439&rft_id=info:pmid/&rfr_iscdi=true