## Abstract

We examine a selective list of combinatorial optimization problems in NP with respect to inapproximability (Arora and Lund (1997)) given that the ground set of elements N has additional characteristics. For each problem in this paper, the set N is expressed explicitly by subsets of N either as a partition or in the form of a cover. The problems examined are generalizations of well-known classical graph problems and include the minimal spanning tree problem, a number of elementary machine scheduling problems, the bin-packing problem, and the travelling salesman problem (TSP). We conclude that for all these generalized problems the existence of a polynomial time approximation scheme (PTAS) is impossible unless P=NP. This suggests a partial characterization for a family of inapproximable problems. For the generalized Euclidean TSP we prove inapproximability even if the subsets are of cardinality 2.

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

Pages (from-to) | 1019-1034 |

Number of pages | 16 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 21 |

Issue number | 4 |

DOIs | |

State | Published - 2007 |

## Keywords

- Approximation algorithms
- Generalized bin packing
- Generalized scheduling problems
- Inapproximability
- Subset travelling salesman

## ASJC Scopus subject areas

- Mathematics(all)