# An Asymptotic PTAS for a Special Case of Minimum Makespan Job Scheduling

Published in *Unpublished technical report*, 2019

In this project, we developed an asymptotic polynomial-time approximation scheme (APTAS) for a special case of the minimum makespan job scheduling problem with job cost constraints motivated by applications to fair chore division problems.

### Authors

Christopher Scarvelis, Adrian Vetta

### Background

Fairly distributing tasks among a set of agents based on their reported per-task costs is a computationally difficult problem. One common setup, the so-called minimum makespan job scheduling problem, has long been known to be NP-hard. In fact, it’s NP-hard to compute a solution to this problem that’s always “sufficiently close” to optimal.

However, it’s often reasonable to assume that each agent ranks the tasks in the same way: They might all agree that one task is the worst, another is second-worst, and so on. In many settings, we’ll also give each agent a budget for their costs to prevent them from “cheating” by reporting very high costs for every task.

Working under Prof. Adrian Vetta, I designed an efficient approximation scheme (an asymptotic polynomial-time approximation scheme) for an instance of this problem that satisfies the two assumptions I laid out above. This algorithm has potential applications to problems at the nexus of economics and computer science involving the fair division of tasks.