Simple approximation algorithms for Polyamorous Scheduling
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913575440744448 |
|---|---|
| author | Biktairov, Yuriy Gąsieniec, Leszek Jiamjitrak, Wanchote Po Namrata Smith, Benjamin Wild, Sebastian |
| author_facet | Biktairov, Yuriy Gąsieniec, Leszek Jiamjitrak, Wanchote Po Namrata Smith, Benjamin Wild, Sebastian |
| contents | In Polyamorous Scheduling, we are given an edge-weighted graph and must find a periodic schedule of matchings in this graph which minimizes the maximal weighted waiting time between consecutive occurrences of the same edge. This NP-hard problem generalises Bamboo Garden Trimming and is motivated by the need to find schedules of pairwise meetings in a complex social group. We present two different analyses of an approximation algorithm based on the Reduce-Fastest heuristic, from which we obtain first a 6-approximation and then a 5.24-approximation for Polyamorous Scheduling. We also strengthen the extant proof that there is no polynomial-time $(1+δ)$-approximation algorithm for the Optimisation Polyamorous Scheduling problem for any $δ< \frac1{12}$ unless P = NP to the bipartite case. The decision version of Polyamorous Scheduling has a notion of density, similar to that of Pinwheel Scheduling, where problems with density below the threshold are guaranteed to admit a schedule (cf. the recently proven 5/6 conjecture, Kawamura, STOC 2024). We establish the existence of a similar threshold for Polyamorous Scheduling and give the first non-trivial bounds on the poly density threshold. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_06292 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Simple approximation algorithms for Polyamorous Scheduling Biktairov, Yuriy Gąsieniec, Leszek Jiamjitrak, Wanchote Po Namrata Smith, Benjamin Wild, Sebastian Data Structures and Algorithms Computational Complexity In Polyamorous Scheduling, we are given an edge-weighted graph and must find a periodic schedule of matchings in this graph which minimizes the maximal weighted waiting time between consecutive occurrences of the same edge. This NP-hard problem generalises Bamboo Garden Trimming and is motivated by the need to find schedules of pairwise meetings in a complex social group. We present two different analyses of an approximation algorithm based on the Reduce-Fastest heuristic, from which we obtain first a 6-approximation and then a 5.24-approximation for Polyamorous Scheduling. We also strengthen the extant proof that there is no polynomial-time $(1+δ)$-approximation algorithm for the Optimisation Polyamorous Scheduling problem for any $δ< \frac1{12}$ unless P = NP to the bipartite case. The decision version of Polyamorous Scheduling has a notion of density, similar to that of Pinwheel Scheduling, where problems with density below the threshold are guaranteed to admit a schedule (cf. the recently proven 5/6 conjecture, Kawamura, STOC 2024). We establish the existence of a similar threshold for Polyamorous Scheduling and give the first non-trivial bounds on the poly density threshold. |
| title | Simple approximation algorithms for Polyamorous Scheduling |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2411.06292 |