Scheduling Problems with Constrained Rejections
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908623237545984 |
|---|---|
| author | Davies, Sami Guruswami, Venkatesan Ren, Xuandi |
| author_facet | Davies, Sami Guruswami, Venkatesan Ren, Xuandi |
| contents | We study bicriteria versions of Makespan Minimization on Unrelated Machines and Santa Claus by allowing a constrained number of rejections. Given an instance of Makespan Minimization on Unrelated Machines where the optimal makespan for scheduling $n$ jobs on $m$ unrelated machines is $T$, (Feige and Vondrák, 2006) gave an algorithm that schedules a $(1-1/e+10^{-180})$ fraction of jobs in time $T$. We show the ratio can be improved to $0.6533>1-1/e+0.02$ if we allow makespan $3T/2$. To the best our knowledge, this is the first result examining the tradeoff between makespan and the fraction of scheduled jobs when the makespan is not $T$ or $2T$.
For the Santa Claus problem (the Max-Min version of Makespan Minimization), the analogous bicriteria objective was studied by (Golovin, 2005), who gave an algorithm providing an allocation so a $(1-1/k)$ fraction of agents receive value at least $T/k$, for any $k \in \mathbb{Z}^+$ and $T$ being the optimal minimum value every agent can receive. We provide the first hardness result by showing there are constants $δ,\varepsilon>0$ such that it is NP-hard to find an allocation where a $(1-δ)$ fraction of agents receive value at least $(1-\varepsilon) T$. To prove this hardness result, we introduce a bicriteria version of Set Packing, which may be of independent interest, and prove some algorithmic and hardness results for it. Overall, we believe these bicriteria scheduling problems warrant further study as they provide an interesting lens to understand how robust the difficulty of the original optimization goal might be. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_00184 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Scheduling Problems with Constrained Rejections Davies, Sami Guruswami, Venkatesan Ren, Xuandi Data Structures and Algorithms Computational Complexity We study bicriteria versions of Makespan Minimization on Unrelated Machines and Santa Claus by allowing a constrained number of rejections. Given an instance of Makespan Minimization on Unrelated Machines where the optimal makespan for scheduling $n$ jobs on $m$ unrelated machines is $T$, (Feige and Vondrák, 2006) gave an algorithm that schedules a $(1-1/e+10^{-180})$ fraction of jobs in time $T$. We show the ratio can be improved to $0.6533>1-1/e+0.02$ if we allow makespan $3T/2$. To the best our knowledge, this is the first result examining the tradeoff between makespan and the fraction of scheduled jobs when the makespan is not $T$ or $2T$. For the Santa Claus problem (the Max-Min version of Makespan Minimization), the analogous bicriteria objective was studied by (Golovin, 2005), who gave an algorithm providing an allocation so a $(1-1/k)$ fraction of agents receive value at least $T/k$, for any $k \in \mathbb{Z}^+$ and $T$ being the optimal minimum value every agent can receive. We provide the first hardness result by showing there are constants $δ,\varepsilon>0$ such that it is NP-hard to find an allocation where a $(1-δ)$ fraction of agents receive value at least $(1-\varepsilon) T$. To prove this hardness result, we introduce a bicriteria version of Set Packing, which may be of independent interest, and prove some algorithmic and hardness results for it. Overall, we believe these bicriteria scheduling problems warrant further study as they provide an interesting lens to understand how robust the difficulty of the original optimization goal might be. |
| title | Scheduling Problems with Constrained Rejections |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2511.00184 |