The Library
Robotic-cell scheduling: Special polynomially solvable cases of the traveling salesman problem on permuted Monge matrices
Tools
UNSPECIFIED (2005) Robotic-cell scheduling: Special polynomially solvable cases of the traveling salesman problem on permuted Monge matrices. JOURNAL OF COMBINATORIAL OPTIMIZATION, 9 (4). pp. 381-399. ISSN 1382-6905.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Abstract
In this paper, we introduce the 1 - K robotic-cell scheduling problem, whose solution can be reduced to solving a TSP on specially structured permuted Monge matrices, we call b-decomposable matrices. We also review a number of other scheduling problems which all reduce to solving TSP-s on permuted Monge matrices. We present the important insight that the TSP on b-decomposable matrices can be solved in polynomial time by a special adaptation of the well-known subtour-patching technique. We discuss efficient implementations of this algorithm on newly defined subclasses of permuted Monge matrices.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software Q Science > QA Mathematics |
||||
Journal or Publication Title: | JOURNAL OF COMBINATORIAL OPTIMIZATION | ||||
Publisher: | SPRINGER | ||||
ISSN: | 1382-6905 | ||||
Official Date: | June 2005 | ||||
Dates: |
|
||||
Volume: | 9 | ||||
Number: | 4 | ||||
Number of Pages: | 19 | ||||
Page Range: | pp. 381-399 | ||||
Publication Status: | Published |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |