| Article ID: | iaor20012534 |
| Country: | United Kingdom |
| Volume: | 7 |
| Issue: | 1 |
| Start Page Number: | 5 |
| End Page Number: | 31 |
| Publication Date: | Jan 2000 |
| Journal: | International Transactions in Operational Research |
| Authors: | Ehrgott Matthias |
| Keywords: | combinatorial analysis |
The computational complexity of combinatorial multiple objective programming problems is investigated. NP-completeness and #P-completeness results are presented. Using two definitions of approximability, general results are presented, which outline limits for approximation algorithms. The performance of the well-known tree and Christofides' heuristics for the traveling salesman problem is investigated in the multicriteria case with respect to the two definitions of approximability.