Overview
What this challenge is about.
Formulate the roster as a constrained multi-week assignment problem. Show it's NP-hard via reduction. Design a deterministic constant-factor approximation (likely candidate: an LP-rounding scheme or a primal-dual approach). Prove the approximation ratio formally. Implement in Python; on small instances (8 engineers × 4 weeks) run both your approximation and a CP-SAT optimal to verify the ratio holds empirically. Scale-test on the full instance (90 engineers × 4 weeks) and report runtime + fairness gap. Deliver formulation, proof, implementation, and a 5-page paper-style writeup.
The Brief
What you'll do, and what you'll demonstrate.
Design, analyze, and implement a provable constant-factor approximation for the on-call roster problem and validate the bound empirically.
Earning criteria — what you'll demonstrate
- Design an approximation algorithm for a real-world NP-hard problem
- Use LP-rounding or primal-dual techniques to bound approximation ratio
- Validate theoretical bounds with carefully designed empirical experiments
- Communicate algorithmic guarantees in a paper-style writeup
Program Fit
Where this fits in your program.
Sharpens the same skills your degree expects you to demonstrate.
Skills
Skills you'll demonstrate.
Each one shows up on your verified credential.
Careers
Roles this prepares you for.
Real titles. Real skill bridges. Pick the one closest to your trajectory.
Career mappings coming soon.