The Asymmetric Assignment Problem and Some New Facets of the Traveling Salesman Polytope.

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 1987
Accession Number
ADA182365

Entities

People

  • Egon Balas

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Air Platforms
  • C4I

DTIC Thesaurus Topics

  • Algorithms
  • Coefficients
  • Computer Programming
  • Contracts
  • Elimination
  • Equations
  • Inequalities
  • Mathematical Programming
  • Mathematics
  • Military Research
  • Operations Research
  • Schools
  • Sequences
  • Structural Properties
  • Students

Readers

  • Graph Algorithms and Convex Optimization.
  • Operations Research