ETH-Tight FPT Algorithm for Makespan Minimization on Uniform Machines
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915095600168960 |
|---|---|
| author | Rohwedder, Lars |
| author_facet | Rohwedder, Lars |
| contents | Given $n$ jobs with processing times $p_1,\dotsc,p_n\in\mathbb N$ and $m\le n$ machines with speeds $s_1,\dotsc,s_m\in\mathbb N$ our goal is to allocate the jobs to machines minimizing the makespan. We present an algorithm that solves the problem in time $p_{\max}^{O(d)} n^{O(1)}$, where $p_{\max}$ is the maximum processing time and $d\le p_{\max}$ is the number of distinct processing times. This is essentially the best possible due to a lower bound based on the exponential time hypothesis (ETH).
Our result improves over prior works that had a quadratic term in $d$ in the exponent and answers an open question by Koutecký and Zink. The algorithm is based on integer programming techniques combined with novel ideas based on modular arithmetic. They can also be implemented efficiently for the more compact high-multiplicity instance encoding. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_04859 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | ETH-Tight FPT Algorithm for Makespan Minimization on Uniform Machines Rohwedder, Lars Data Structures and Algorithms Given $n$ jobs with processing times $p_1,\dotsc,p_n\in\mathbb N$ and $m\le n$ machines with speeds $s_1,\dotsc,s_m\in\mathbb N$ our goal is to allocate the jobs to machines minimizing the makespan. We present an algorithm that solves the problem in time $p_{\max}^{O(d)} n^{O(1)}$, where $p_{\max}$ is the maximum processing time and $d\le p_{\max}$ is the number of distinct processing times. This is essentially the best possible due to a lower bound based on the exponential time hypothesis (ETH). Our result improves over prior works that had a quadratic term in $d$ in the exponent and answers an open question by Koutecký and Zink. The algorithm is based on integer programming techniques combined with novel ideas based on modular arithmetic. They can also be implemented efficiently for the more compact high-multiplicity instance encoding. |
| title | ETH-Tight FPT Algorithm for Makespan Minimization on Uniform Machines |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2501.04859 |