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. 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
﻿