Provably Fair Approximation Algorithm for a Neobank On-Call Roster
Overview
What this challenge is about.
Prove NP-hardness and design a constant-factor approximation for a neobank’s roster, then implement it in Python. Get a verifiable certificate.
The scenario
Atlas Pay is a ~1,400-person consumer neobank in New York City running 8 production services that require 24/7 on-call coverage from a pool of about 90 engineers across multiple timezones. Reliability leadership needs roster fairness it can defend with a guarantee, not intuition, because perceived inequity in on-call load is driving engineer attrition.
The Brief
What you'll do, and what you'll demonstrate.
Design, analyze, and implement a deterministic constant-factor approximation algorithm for the NP-hard weekly on-call roster problem, and empirically validate that its fairness ratio respects the proven bound.
Earning criteria — what you'll demonstrate
- Formalize a real operational scheduling problem as a constrained optimization model and prove its hardness by reduction
- Design a deterministic constant-factor approximation using LP-rounding or primal-dual techniques and prove its ratio formally
- Implement an approximation algorithm and an exact solver baseline that operate on the same instance and produce comparable solutions
- Empirically validate a theoretical approximation bound and communicate the result in reviewer-ready written form
Program Fit
Where this fits in your program.
Sharpens the same skills your degree expects you to demonstrate.
Aligned coursework coming soon.
Skills
Skills you'll demonstrate.
Each one shows up on your verified credential.
- Approximation Algorithms
Apply approximation algorithms to solve real industry problems and demonstrate production-level capability.
- Linear Programming
Apply linear programming to solve real industry problems and demonstrate production-level capability.
- Np Completeness
Apply np completeness to solve real industry problems and demonstrate production-level capability.
- Python
Write clean, efficient Python for data processing, automation, and backend services.
- Complexity Theory
Apply complexity theory to solve real industry problems and demonstrate production-level capability.
- Constraint Handling
Apply constraint handling to solve real industry problems and demonstrate production-level capability.
Careers
Career paths this challenge builds toward
Completing this challenge demonstrates skills that transfer directly to these roles:
Site Reliability Engineer
Reliability teams routinely face NP-hard scheduling and capacity problems. This challenge builds the judgment to model an on-call roster rigorously, choose a defensible algorithm, and prove its quality, exactly the reasoning SREs need when manual heuristics stop scaling.
This challenge sharpens
- approximation-algorithms
- constraint-handling
- python
Optimization / Operations Research Engineer
Turning a messy operational need into a constrained model, an exact solver baseline, and a provable approximation is the core OR engineering loop. This challenge exercises that pipeline end to end on a realistic fintech instance.
This challenge sharpens
- linear-programming
- np-completeness
- approximation-algorithms
Algorithms Researcher
Proving an approximation ratio and validating it empirically against an optimal baseline mirrors how applied-algorithms research is produced and reviewed. The paper-style writeup develops the communication skills expected in research roles.
This challenge sharpens
- complexity-theory
- approximation-algorithms
- np-completeness