Algorithmes d'approximation polynomiale du temps pour la planification des machines: combien de problèmes ouverts subsistent-ils?

22

En 1999, Petra Schuurman et Gerhard J. Woeginger ont publié l'article "Algorithmes d'approximation du temps polynomiaux pour la planification des machines: dix problèmes ouverts" . Depuis lors, à ma connaissance, des critiques qui concerneraient très exactement la même liste de problèmes ne sont pas apparues. Il serait donc formidable et utile que chacun de nous puisse faire un tel résumé sur certains des dix problèmes ouverts et y contribuer ici.

Dai Le
la source
Je ne pense pas que cela devait être fait CW ...
Suresh Venkat
@Suresh Venkat: Comment supprimer CW?
Oleksandr Bondarenko
Malheureusement, il n'y a aucun moyen de transformer une question wiki communautaire en une question non CW. L'ajout de cette fonctionnalité au moteur Stack Exchange est demandé à: meta.stackexchange.com/questions/6821/…
Tsuyoshi Ito du
Voir également la FAQ sur l'utilisation du tag CW: meta.cstheory.stackexchange.com/questions/225/…
Suresh Venkat

Réponses:

16

Minimisation de la durée de vie sur des machines identiques sous contraintes de priorité

Problème ouvert 1. Fournir un résultat inapproximabilité pour P | p r e c | C m a x .4/3+δP|prec|CmuneX

Ici, ce qui me vient à l'esprit est le papier de cette année par Ola Svensson "La dureté conditionnelle de la planification ordonnée contrainte sur les machines identiques". Dans son article, Ola prouve que

"si le problème d'une seule machine est difficile à estimer dans un facteur de alors le problème de machine parallèle considéré, même dans le cas des temps de traitement unitaires, est difficile à estimer dans un facteur de 2 - ζ2-ϵ2-ζ , où tend vers 0 car ϵ tend vers 0. "ζϵ

En 2008, il a été publié le document "Ordonnancement contraint par priorité dans · optimal "décrivant un algorithme pourP|prec,pj=1|Cmax(2-73p+1)P|prec,pj=1|CmuneX . Avec le rapport de performance, mentionné dans le titre Ce améliore algorithme Coffman-Graham avec borne 22p , où p est le nombre de machines.

L'article «Algorithmes d'approximation pour la planification des travaux avec des contraintes de priorité de chaîne» par Jansen et Solis-Oba contient PTAS pour et, par conséquent, pour P m | c h a i n s | C m a xQm|chains|CmaxPm|chains|Cmax comme cas particulier de l'ancien problème.

Cette année est apparu l'article "Schémas d'approximation pour la planification des travaux avec des contraintes de priorité de chaîne" par Jansen et Solis-Oba (version journal de la précédente), qui concerne PTAS pour avec un nombre fixe d'emplois dans chaque chaîne et P | p r e c | C m a x avec un nombre constant de tâches dans le composant connecté de chaque commande.P|chains|CmaxP|prec|Cmax

Minimisation de la durée de vie sur des machines uniformes soumises à des contraintes de priorité

L'article de 2003 de l'année «Algorithmes d'approximation pour la planification des travaux avec des contraintes de précédence de chaîne» par Jansen et Solis-Oba contient PTAS pour Qm|chains|Cmax .

Minimisation du Makespan sous contraintes de priorité avec retards de communication

Minimisation de la durée de vie sur des machines indépendantes

Minimisation du Makespan dans les magasins ouverts

Minimisation de la durée de vie dans les magasins de flux

Dans l'article de Nagarajan et Sviridenko de 2008 "Limites serrées pour la planification des ateliers de flux de permutation", nous pouvons trouver la limite supérieure du rapport entre la durée optimale et la durée du meilleur calendrier de permutation. Cette borne est le rapport d'approximation d'un algorithme proposé, et c'est le meilleur possible parmi les algorithmes basés sur les bornes inférieures triviales, jusqu'à22Facteur . Soit dit en passant, les algorithmes proposés sont actuellement ceux qui présentent les meilleurs rapports d'approximation.

Minimisation du Makespan dans les ateliers d'emploi

J||Cmaxmμ5/4+δJ||CmaxJ||Cmaxm de machines à infity.

J2||Cmaxμ NP.

J||CmaxO((loglb)1ϵ)NPZTIME(2lognO(1/ϵ))J2||CmaxNPDTIME(nO(logn)).

Total job completion time without precedence constraints

Total job completion time under precedence constraints

Open problem 9. Prove that 1|prec|Cj and 1|prec|wjCj do not have polynomial time approximation algorithms with performance guarantee 2ϵ unless P=NP.

In "Optimal long code test with one free bit" Bansal and Khot proved that it is so, but assuming a new variant of the unique games conjecture.

Flow time criteria

Open problem 10. Design polynomial time approximation algorithms with constant performance guarantees for 1|pmtn;rj|wjFj and for P|pmtn;rj|Fj.

In "Weighted flow time does not admit O(1)-competitive algorithms" Bansal and Chan proved that 1|pmtn;rj|wjFj "does not admit O(1)-competitive algorithms". Interestingly, the authors don't cite the paper of Schuurman and Woeginger.

In "Minimizing Average Flow-time: Upper and Lower Bounds" Garg and Kumar proved a lower bound Ω(logPloglogP) on the approximation ratio for P|pmtn;rj|Fj. Later this bound was improved to Ω(logPloglogP) in "Minimizing Total Flow-Time: The Unrelated Case" by Garg, Kumar and Muralidhara.

Oleksandr Bondarenko
la source