The Library
Robotic-cell scheduling: Special polynomially solvable cases of the traveling salesman problem on permuted Monge matrices
Tools
Tools
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
Full text not available from this repository.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 |
| Date: | June 2005 |
| Volume: | 9 |
| Number: | 4 |
| Number of Pages: | 19 |
| Page Range: | pp. 381-399 |
| Publication Status: | Published |
| URI: | http://wrap.warwick.ac.uk/id/eprint/6722 |
Data sourced from Thomson Reuters' Web of Knowledge
Actions (login required)
 |
View Item |
