Accession Number:

ADP006625

Title:

A Unified Representation for Some Combinatorial Optimization Problems,

Descriptive Note:

Corporate Author:

AT AND T BELL LABS HOLMDEL NJ

Personal Author(s):

Report Date:

1992-03-01

Pagination or Media Count:

7.0

Abstract:

In this short note, we list a number of combinatorial optimization problems, among them the Traveling Salesman Problem and the Graph Partitioning Problem, that can be represented by a common matrix formulation. This formulation was used previously by Brockett to study certain geometric matching problems. Although this unified representation does not necessarily imply the existence of a unified efficient algorithm to solve all these problems, it may provide useful insights for a better understanding of the structure of these problems.

Subject Categories:

  • Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE