Improved lower bound for differentially private facility location

DOI10.1016/J.IPL.2024.106502MaRDI QIDQ6602319zbMATH OpenFDO

Authors Pasin Manurangsi

Publication date 11 September 2024

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.IPL.2024.106502

zbMATH Keywords

approximation algorithmsdifferential privacyfacility locationlower bound

Mathematics Subject Classification ID

Privacy of data (68P27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Discrete location and assignment (90B80)

Recommendations

• Differentially private combinatorial optimization
• Optimal lower bounds for universal and differentially private Steiner trees and TSPs
• Locally private \(k\)-means clustering
• Lower bounds in differential privacy
• On the geometry of differential privacy

Cites work

• A 1.488 approximation algorithm for the uncapacitated facility location problem
• A new greedy approach for facility location problems
• A tight bound on approximating arbitrary metrics by tree metrics
• An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem
• Analysis of a Local Search Heuristic for Facility Location Problems
• Approximation Algorithms for Metric Facility Location Problems
• Differentially private combinatorial optimization
• Dynamic cage survey
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• Greedy Strikes Back: Improved Facility Location Algorithms
• Heuristics for the fixed cost median problem
• scientific article; zbMATH DE number 1559542 (Why is no real title available?)
• scientific article; zbMATH DE number 1775400 (Why is no real title available?)
• scientific article; zbMATH DE number 3189017 (Why is no real title available?)
• Improved Approximation Algorithms for the Uncapacitated Facility Location Problem
• On the geometry of differential privacy
• The algorithmic foundations of differential privacy
• Theory of Cryptography

This page was built for publication: Improved lower bound for differentially private facility location

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6602319)