WEKO3
アイテム
Linear Facility Cost Capacity Constrained Facility Location Problem on Local Differential Privacy without Superset Assumption
https://ipsj.ixsq.nii.ac.jp/records/233377
https://ipsj.ixsq.nii.ac.jp/records/2333771549be1d-da9d-4f59-a602-f066648024b5
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL24197002.pdf (870.6 kB)
2026年3月14日からダウンロード可能です。
|
Copyright (c) 2024 by the Information Processing Society of Japan
|
|
| 非会員：¥660, IPSJ:学会員：¥330, AL:会員：¥0, DLIB:会員：¥0 | ||
| Item type | SIG Technical Reports(1) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2024-03-14 | |||||||||
| タイトル | ||||||||||
| タイトル | Linear Facility Cost Capacity Constrained Facility Location Problem on Local Differential Privacy without Superset Assumption | |||||||||
| タイトル | ||||||||||
| 言語 | en | |||||||||
| タイトル | Linear Facility Cost Capacity Constrained Facility Location Problem on Local Differential Privacy without Superset Assumption | |||||||||
| 言語 | ||||||||||
| 言語 | eng | |||||||||
| 資源タイプ | ||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||||
| 資源タイプ | technical report | |||||||||
| 著者所属 | ||||||||||
| Technical University of Munich | ||||||||||
| 著者所属 | ||||||||||
| The University of Tokyo | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| Technical University of Munich | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| The University of Tokyo | ||||||||||
| 著者名 |
Kevin, Pfisterer
× Kevin, Pfisterer
× Vorapong, Suppakitpaisarn
|
|||||||||
| 著者名(英) |
Kevin, Pfisterer
× Kevin, Pfisterer
× Vorapong, Suppakitpaisarn
|
|||||||||
| 論文抄録 | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | We study the facility location problem in the local differential privacy (LDP) model. Previously, Gupta et al. (2019), Esencayi et al. (2019), and Cohen-Addad et al. (2022) studied the problem and proposed an ε-LDP algorithm with an approximation ratio of O(n1/4/ε2) under the HST metric. However, all the mechanisms are proposed undser the super-set output setting, which assumes that the final step of the mechanism uses private information. We believe that the setting is not practical and aim to remove that assumption in this work. We focus on a facility location problem where the costs of a facility are linear to the amount of connected clients to it. In this setting we propose an ε-LDP algorithm that achieves an O(1) approximation under the HST metric. We further provide a bound on the probability that the algorithm fails. | |||||||||
| 論文抄録(英) | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | We study the facility location problem in the local differential privacy (LDP) model. Previously, Gupta et al. (2019), Esencayi et al. (2019), and Cohen-Addad et al. (2022) studied the problem and proposed an ε-LDP algorithm with an approximation ratio of O(n1/4/ε2) under the HST metric. However, all the mechanisms are proposed undser the super-set output setting, which assumes that the final step of the mechanism uses private information. We believe that the setting is not practical and aim to remove that assumption in this work. We focus on a facility location problem where the costs of a facility are linear to the amount of connected clients to it. In this setting we propose an ε-LDP algorithm that achieves an O(1) approximation under the HST metric. We further provide a bound on the probability that the algorithm fails. | |||||||||
| 書誌レコードID | ||||||||||
| 収録物識別子タイプ | NCID | |||||||||
| 収録物識別子 | AN1009593X | |||||||||
| 書誌情報 |
研究報告アルゴリズム（AL） 巻 2024-AL-197, 号 2, p. 1-5, 発行日 2024-03-14 |
|||||||||
| ISSN | ||||||||||
| 収録物識別子タイプ | ISSN | |||||||||
| 収録物識別子 | 2188-8566 | |||||||||
| Notice | ||||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||||
| 出版者 | ||||||||||
| 言語 | ja | |||||||||
| 出版者 | 情報処理学会 | |||||||||
