On dual solutions of the linear assignment problem (Q761971): Difference between revisions

The linear assignment problem (LAP) which is a relaxation of many cominatorial problems such as the traveling salesman problem, delivery and school bus problems, vehicle scheduling problems, the quadratic assignment problem, is considered and a shortest path algorithm is used to compute different dual solutions of the LAP. Two applications in the context of the traveling salesman problem are proposed.

0 references

zbMATH Keywords

linear assignment

0 references

shortest path algorithm

0 references

dual solutions

0 references

traveling salesman

0 references

reviewed by

Oleg A. Shcherbina

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1016/0377-2217(85)90310-8

0 references

cites work

A restricted Lagrangean approach to the traveling salesman problem

0 references

An exact branch-and-bound procedure for the quadratic-assignment problem

0 references

Technical Note—Bounds for the Travelling-Salesman Problem

0 references

Q4151660

0 references

An approach for solving a class of transportation scheduling problems

0 references

Network flow, transportation and scheduling. Theory and algorithms

0 references

Technical Note—Rounding Symmetric Traveling Salesman Problems with an Asymmetric Assignment Problem

0 references

Q5519710

0 references

Q4130999

0 references

An operator theory of parametric programming for the transportation problem-I

0 references

Q4401715

0 references

On some techniques useful for solution of transportation network problems

0 references

Solving symmetric vehicle routing problems asymmetrically

0 references

The symmetric traveling salesman problem and edge exchanges in minimal 1- trees

0 references

Identifiers

zbMATH Open document ID

0557.90066

0 references

DOI

10.1016/0377-2217(85)90310-8

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:761971

@@ Property / author @@
-Q761968
@@ Property / author: Q761968 / rank @@
-Normal rank
@@ Property / reviewed by @@
-Q750304
@@ Property / reviewed by: Q750304 / rank @@
-Normal rank
@@ Property / author @@
+G. A. P. Kindervater
@@ Property / author: G. A. P. Kindervater / rank @@
+Normal rank
@@ Property / reviewed by @@
+Oleg A. Shcherbina
@@ Property / reviewed by: Oleg A. Shcherbina / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/0377-2217(85)90310-8
+Normal rank
@@ Property / OpenAlex ID @@
+W2028068470
@@ Property / OpenAlex ID: W2028068470 / rank @@
+Normal rank
@@ Property / cites work @@
+A restricted Lagrangean approach to the traveling salesman problem
+Normal rank
@@ Property / cites work @@
+An exact branch-and-bound procedure for the quadratic-assignment problem
+Normal rank
@@ Property / cites work @@
+Technical Note—Bounds for the Travelling-Salesman Problem
+Normal rank
@@ Property / cites work @@
+Q4151660
@@ Property / cites work: Q4151660 / rank @@
+Normal rank
@@ Property / cites work @@
+An approach for solving a class of transportation scheduling problems
+Normal rank
@@ Property / cites work @@
+Network flow, transportation and scheduling. Theory and algorithms
+Normal rank
@@ Property / cites work @@
+Technical Note—Rounding Symmetric Traveling Salesman Problems with an Asymmetric Assignment Problem
+Normal rank
@@ Property / cites work @@
+Q5519710
@@ Property / cites work: Q5519710 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4130999
@@ Property / cites work: Q4130999 / rank @@
+Normal rank
@@ Property / cites work @@
+An operator theory of parametric programming for the transportation problem-I
+Normal rank
@@ Property / cites work @@
+Q4401715
@@ Property / cites work: Q4401715 / rank @@
+Normal rank
@@ Property / cites work @@
+On some techniques useful for solution of transportation network problems
+Normal rank
@@ Property / cites work @@
+Solving symmetric vehicle routing problems asymmetrically
+Normal rank
@@ Property / cites work @@
+The symmetric traveling salesman problem and edge exchanges in minimal 1- trees
+Normal rank