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