A fundamental problem in linear inequalities with applications to the travelling salesman problem
dc.contributor.author | Murty, Katta G. | en_US |
dc.date.accessioned | 2006-09-11T19:32:21Z | |
dc.date.available | 2006-09-11T19:32:21Z | |
dc.date.issued | 1972-02 | en_US |
dc.identifier.citation | Murty, Katta G.; (1972). "A fundamental problem in linear inequalities with applications to the travelling salesman problem." Mathematical Programming 2(1): 296-308. <http://hdl.handle.net/2027.42/47908> | en_US |
dc.identifier.issn | 0025-5610 | en_US |
dc.identifier.issn | 1436-4646 | en_US |
dc.identifier.uri | https://hdl.handle.net/2027.42/47908 | |
dc.description.abstract | We consider a system of m linearly independent equality constraints in n nonnegative variables: Ax = b, x ≧ 0. The fundamental problem that we discuss is the following: suppose we are given a set of r linearly independent column vectors of A , known as the special column vectors. The problem is to develop an efficient algorithm to determine whether there exists a feasible basis which contains all the special column vectors as basic column vectors and to find such a basis if one exists. Such an algorithm has several applications in the area of mathematical programming. As an illustration, we show that the famous travelling salesman problem can be solved efficiently using this algorithm. Recent published work indicates that this algorithm has applications in integer linear programming. An algorithm for this problem using a set covering approach is described. | en_US |
dc.format.extent | 537785 bytes | |
dc.format.extent | 3115 bytes | |
dc.format.mimetype | application/pdf | |
dc.format.mimetype | text/plain | |
dc.language.iso | en_US | |
dc.publisher | Springer-Verlag; The Mathematical Programming Society | en_US |
dc.subject.other | Calculus of Variations and Optimal Control | en_US |
dc.subject.other | Mathematics | en_US |
dc.subject.other | Numerical Analysis | en_US |
dc.subject.other | Mathematics of Computing | en_US |
dc.subject.other | Combinatorics | en_US |
dc.subject.other | Operation Research/Decision Theory | en_US |
dc.subject.other | Mathematical Methods in Physics | en_US |
dc.subject.other | Numerical and Computational Methods | en_US |
dc.subject.other | Mathematical and Computational Physics | en_US |
dc.subject.other | Optimization | en_US |
dc.title | A fundamental problem in linear inequalities with applications to the travelling salesman problem | en_US |
dc.type | Article | en_US |
dc.subject.hlbsecondlevel | Mathematics | en_US |
dc.subject.hlbtoplevel | Science | en_US |
dc.description.peerreviewed | Peer Reviewed | en_US |
dc.contributor.affiliationum | University of Michigan, Ann Arbor, Michigan, USA | en_US |
dc.contributor.affiliationumcampus | Ann Arbor | en_US |
dc.description.bitstreamurl | http://deepblue.lib.umich.edu/bitstream/2027.42/47908/1/10107_2005_Article_BF01584550.pdf | en_US |
dc.identifier.doi | http://dx.doi.org/10.1007/BF01584550 | en_US |
dc.identifier.source | Mathematical Programming | en_US |
dc.owningcollname | Interdisciplinary and Peer-Reviewed |
Files in this item
Remediation of Harmful Language
The University of Michigan Library aims to describe library materials in a way that respects the people and communities who create, use, and are represented in our collections. Report harmful or offensive language in catalog records, finding aids, or elsewhere in our collections anonymously through our metadata feedback form. More information at Remediation of Harmful Language.
Accessibility
If you are unable to use this file in its current format, please select the Contact Us link and we can modify it to make it more accessible to you.