Research map / Federated learning and privacy / Privacy attacks and secure learning
Privacy-and-Utility-Aware Publishing of Schedules
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Formulates privacy-and-utility preservation for publishing parallel-machine schedules and solves it via schedule perturbations (swap, move, feature change) searched with constraint programming/breadth-first search to defeat inverse scheduling attacks.
Problem
Publishing schedules can leak sensitive job features (e.g., patient priorities) via inverse scheduling attacks, while published schedules must remain useful for analysis.
Approach
Defines the Privacy-and-Utility Preservation Problem (PUP) bounding both privacy loss and utility loss, and instantiates it with schedule perturbation functions (swapping jobs, moving jobs, perturbing public features) explored systematically as neighborhoods, implemented via constraint programming and breadth-first search.
Key results
- PUP solved for 58.7-74.4% of synthetic TWCT instances and 58.3-80.1% of AWT instances, depending on configuration and perturbation.
- For MAKE synthetic schedules, move and swap-based functions (M, MP, S, SP) solved 83.8-87.9% of instances for z=Cmax.
- Real-world experiments solved PUP for 20-83% of schedules, with move-based perturbations generally performing best.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SP (job swaps plus feature perturbation) instead of other tested perturbation functions | PUP on synthetic TWCT schedules · Synthetic TWCT schedules | PUP success rate: 68.9-74.4% | Helped |
| Use SP (job swaps plus feature perturbation) instead of other tested perturbation functions | PUP on synthetic AWT schedules · Synthetic AWT schedules | PUP success rate: 72.6-80.1% | Helped |
| Use P (feature perturbation) alone rather than the other perturbation functions | PUP on synthetic schedules · Synthetic TWCT and AWT schedules | PUP success rate | Hurt |
| Use M or MP rather than the other perturbation functions | PUP on real-world clinic schedules · Real-world clinic schedules | PUP success rate | Helped |
| Increase the utility-loss threshold δ | PUP on real-world clinic schedules · Real-world clinic schedules | PUP success rate | Helped |
| Increase the utility-loss threshold δ | PUP using P with TWCT utility and ϵ = 0.5 · Synthetic TWCT schedules | PUP success rate | Hurt |
| Add moving jobs and feature perturbation (MP) rather than using job swaps alone (S) (ablation) | PUP on synthetic MAKE schedules · Synthetic MAKE schedules, z = Cmax | PUP success rate: 53.1-55.2% -> 83.8-87.9% | Helped |
| Add moving jobs and feature perturbation (MP) rather than using job swaps alone (S) (ablation) | PUP on synthetic MAKE schedules · Synthetic MAKE schedules, z = AWT | PUP success rate: 51.2-61.7% -> 83-88.4% | Helped |
| Use combinations of perturbation functions rather than any single perturbation function (ablation) | PUP on synthetic TWCT schedules · Synthetic TWCT schedules | PUP instances solved exclusively | Mixed |
Surprising findings
- Feature perturbation alone (P) consistently performed worst among perturbation functions, while each perturbation type uniquely solved some instances.
- For MAKE, the empty candidate-set outcome prevents finding a consistent release date vector but does not prevent deriving individual release dates for some jobs.
Limitations
- Search can time out; PUP is computationally expensive and needs heuristics for scalability.
- Assumes a specific adversary with domain knowledge and that schedules are optimal or dispatching-rule-based; stronger adversaries not considered.
- For MAKE, individual release dates can still be inferred even when the candidate set is empty.
Experimental setup
Datasets: synthetic schedules (1000 generated) real-world outpatient cancer hospital infusion schedules (30 schedules)
Benchmarks: synthetic schedules (TWCT, MAKE) real-world infusion schedules
Metrics: success rate of PUP privacy loss (distance-based) utility loss (relative change) runtime
Baselines: P (feature perturbation only) S (swap only) M (move only)
Builds on: Inverse scheduling attack (Fahrenkrog-Petersen et al. 2023) WSPT dispatching rule EST principle
Closest papers by meaning
- Privacy Attacks on Schedule-Driven Data (AAAI 2023 · similarity 0.93)
- Differentially Private Linear Programming: Reduced Sub-Optimality and Guaranteed Constraint Satisfaction (AAAI 2026 · similarity 0.84)
- Privately Publishable Per-instance Privacy (NeurIPS 2021 · similarity 0.83)
- Privacy Odometers and Filters: Pay-as-you-Go Composition (NeurIPS 2016 · similarity 0.83)
- Fully-Adaptive Composition in Differential Privacy (ICML 2023 · similarity 0.83)
- The Last Iterate Advantage: Empirical Auditing and Principled Heuristic Analysis of Differentially Private SGD (ICLR 2025 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.