Accession Number : ADP006625

Title :   A Unified Representation for Some Combinatorial Optimization Problems,

Corporate Author : AT AND T BELL LABS HOLMDEL NJ

Personal Author(s) : Wong, Wing Shing

Report Date : MAR 1992

Pagination or Media Count : 7

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.

Descriptors :   *OPTIMIZATION, *COMBINATORIAL ANALYSIS, ALGORITHMS, FORMULATIONS, GRAPHS, MATCHING, NUMBERS, STRUCTURES.

Subject Categories : Numerical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE