Ahan Mishra

collaborators

3 papers

cs.DS2026

NP-Hardness and a PTAS for the Pinwheel Problem

Robert Kleinberg, Ahan Mishra

In the pinwheel problem, one is given an $m$ -tuple of positive integers $(a_{1}, \dots, a_{m})$ and asked whether the integers can be partitioned into $m$ color classes $C_1,\ldots,C_…

cs.DS2026

An Optimal Density Bound for Discretized Point Patrolling

Ahan Mishra

The pinwheel problem is a real-time scheduling problem that asks, given $n$ tasks with periods $a_{i} \in N$ , whether it is possible to infinitely schedule the tasks, one pe…

cs.DS2025

Improving Pinwheel Density Bounds for Small Minimums

Ahan Mishra, Parker Rho, Robert Kleinberg

The density bound for schedulability for general pinwheel instances is $\frac{5}{6}$ , but density bounds better than $\frac{5}{6}$ can be shown for cases in which the minimum eleme…