Publication

Hardness of Approximating Flow and Job Shop Scheduling Problems

Ola Nils Anders Svensson
2011
Journal Articles

Résumé

We consider several variants of the job shop problem that is a fundamental and classical problem in scheduling. The currently best approximation algorithms have worse than logarithmic performance guarantee, but the only previously known inapproximability result says that it is NP-hard to approximate job shops within a factor less than 5/4. Closing this big approximability gap is a well-known and long-standing open problem.

Source officielle

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Hardness of Approximating Flow and Job Shop Scheduling Problems

Chattez avec Graph Search

Anthony C Davison and Igor Rodionov's contribution to the Discussion of 'Estimating means of bounded random variables by betting' by Waudby-Smith and Ramdas

Succinct ordering and aggregation constraints in algebraic array theories

OASIS: An integrated optimisation framework for activity scheduling