Publication

Hardness of Approximating Flow and Job Shop Scheduling Problems

Ola Nils Anders Svensson
2011
Journal Articles

Abstract

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.

Official source

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Hardness of Approximating Flow and Job Shop Scheduling Problems

Chat with 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