The Library
No-wait flowshop scheduling is as hard as asymmetric traveling salesman problem
Tools
Mucha, Marcin and Sviridenko, Maxim (2013) No-wait flowshop scheduling is as hard as asymmetric traveling salesman problem. In: Freivalds, Rūsiņš and Kwiatkowska, Martha and Fomin, Fedor V. and Peleg , David, (eds.) Automata, Languages, and Programming : 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I. Lecture Notes in Computer Science, Volume 7965 . Berlin ; London: Springer Berlin Heidelberg, pp. 769-779. ISBN 9783642392054
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1007/978-3-642-39206-1_65
Abstract
In this paper we study the classical no-wait flowshop scheduling problem with makespan objective (F|no − wait|C max in the standard three-field notation). This problem is well-known to be a special case of the asymmetric traveling salesman problem (ATSP) and as such has an approximation algorithm with logarithmic performance guarantee. In this work we show a reverse connection, we show that any polynomial time α-approximation algorithm for the no-wait flowshop scheduling problem with makespan objective implies the existence of a polynomial-time α(1 + ε)-approximation algorithm for the ATSP, for any ε > 0. This in turn implies that all non-approximability results for the ATSP (current or future) will carry over to its special case. In particular, it follows that no-wait flowshop problem is APX-hard, which is the first non-approximability result for this problem.
Item Type: | Book Item | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Series Name: | Lecture Notes in Computer Science | ||||
Publisher: | Springer Berlin Heidelberg | ||||
Place of Publication: | Berlin ; London | ||||
ISBN: | 9783642392054 | ||||
ISSN: | 0302-9743 | ||||
Book Title: | Automata, Languages, and Programming : 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I | ||||
Editor: | Freivalds, Rūsiņš and Kwiatkowska, Martha and Fomin, Fedor V. and Peleg , David | ||||
Official Date: | 2013 | ||||
Dates: |
|
||||
Volume: | Volume 7965 | ||||
Page Range: | pp. 769-779 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Description: | |||||
Title of Event: | 40th International Colloquium on Automata, Languages, and Programming, ICALP 2013 | ||||
Type of Event: | Other | ||||
Location of Event: | Riga, Latvia | ||||
Date(s) of Event: | 8-12 July 2013 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |