## Abstract

In this paper, we examine combinatorial optimization problems by considering the case where the set N (the ground set of elements) is expressed as a union of a finite number of m nonempty distinct subsets N_{1}, . . . , N_{m}. The term we use is the generalized Steiner problems coined after the Generalized Traveling Salesman Problem. We have collected a short list of classical combinatorial optimization problems and we have recast each of these problems in this broader framework in an attempt to identify a linkage between these "generalized" problems. In the literature one finds generalized problems such as the Generalized Minimum Spanning Tree (GMST), Generalized Traveling Salesman Problem (GTSP) and Subset Bin-packing (SBP). Casting these problems into the new problem setting has important implications in terms of the time effort required to compute an optimal solution or a "good" solution to a problem. We examine questions like "is the GTSP "harder" than the TSP?" for a number of paradigmatic problems starting with "easy" problems such as the Minimal Spanning Tree, Assignment Problem, Chinese Postman, Two-machine Flow Shop, and followed by "hard" problems such as the Bin-packing, and the TSP.

Original language | English (US) |
---|---|

Pages (from-to) | 415-436 |

Number of pages | 22 |

Journal | Journal of Combinatorial Optimization |

Volume | 4 |

Issue number | 4 |

DOIs | |

State | Published - 2000 |

## Keywords

- Approximation algorithms
- Complexity
- Generalized TSP
- NP-hardness

## ASJC Scopus subject areas

- Computer Science Applications
- Discrete Mathematics and Combinatorics
- Control and Optimization
- Computational Theory and Mathematics
- Applied Mathematics