Robert D. Kleinberg

collaborators

2 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.DS2025

The $k$ -Fold Matroid Secretary Problem

Rishi Gujjar, Kevin Hua, Robert Kleinberg +1

In the matroid secretary problem, elements $N := [n]$ of a matroid $M \subseteq 2^{N}$ arrive in random order. When an element arrives, its weight is revealed and a choice…

NP-Hardness and a PTAS for the Pinwheel Problem

The k-Fold Matroid Secretary Problem

The $k$ -Fold Matroid Secretary Problem