
Accession Number : ADA182365
Title : The Asymmetric Assignment Problem and Some New Facets of the Traveling Salesman Polytope.
Descriptive Note : Management Sciences research rept.,
Corporate Author : CARNEGIEMELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Personal Author(s) : Balas, Egon
PDF Url : ADA182365
Report Date : May 1987
Pagination or Media Count : 35
Abstract : An assignment (spanning union of nodedisjoint dicycles) in a directed graph is called asymmetric if it contains at most one arc of each pair (i,j), (j,i). This document describes a class of facets for the asymmetric assignment polytope, associated with certain oddlength closed alternating trails. The inequalities defining these facets are also facet defining for the traveling salesman polytope on the same digraph. Furthermore, this class of facets is distinct from each of the classes identified earlier. Keywords: Directed graphs; Alternating trails; Partial linear analysis.
Descriptors : *ASYMMETRY, *INEQUALITIES, GRAPHS, LINEAR SYSTEMS, MATHEMATICAL ANALYSIS
Subject Categories : Operations Research
Distribution Statement : APPROVED FOR PUBLIC RELEASE