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 : CARNEGIE-MELLON 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 node-disjoint 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 odd-length 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