A Unified Representation for Some Combinatorial Optimization Problems,
AT AND T BELL LABS HOLMDEL NJ
Pagination or Media Count:
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.
- Numerical Mathematics