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)