Geometric Algorithms for Differentially Private Combinatorial Optimization with Constraints

Combinatorial optimization (CO) problems arise in a wide range of applications, including resource allocation, network design, and decision-making on sensitive data. While prior work has developed Differentially Private (DP) algorithms for specific problems—such as submodular maximization, graph cuts, and facility location—these approaches typically rely on problem-specific analyses, limiting their broader applicability. In this work, we introduce a unified framework for differentially private CO that applies across diverse constraint families. Our approach is based on a gradient-based method that optimizes a differentiable extension of the combinatorial objective. To achieve both privacy and differentiability, we develop an algorithm combining Carathéodory decomposition with Frank–Wolfe optimization, which enables efficient computation of gradients in a DP manner. A key insight of our framework is that, for a broad class of problems with data-independent polytopes—where the feasible region depends only on public structure—privacy can be ensured by adding calibrated noise solely to objective evaluations, while all other steps follow from privacy-preserving post-processing and composition. This class includes several important polytopes, such as the hypersimplex and the Birkhoff polytope. We also prove an impossibility results for cases where the constraint polytope is data-dependent. We validate our approach on a range of CO problems, including the quadratic assignment problem (QAP) and maximum coverage, demonstrating its practical effectiveness.