Loading...
Please wait, while we are loading the content...
Similar Documents
On the Complexity of Solving the Generalized Set Packing Problem Approximately
| Content Provider | Semantic Scholar |
|---|---|
| Author | Megiddo, Nimrod |
| Copyright Year | 2004 |
| Abstract | The generalized set packing problem GSP is as follows Given a family F of subsets of M f mg and a vector b R nd a subfamily F F of maximum cardinality such that for every i M i does not belong to more than bi members of F The subproblem GSPk consists of those instances of GSP where each member of M belongs to at most k members of F It is shown that for every k if there is a polynomial time approximation algorithm for GSPk with a positive performance ratio then GSPk has a polynomial approximation scheme This generalizes a result of Garey and Johnson with regard to the maximum independent set problem in a graph y IBM Almaden Research Center Harry Road San Jose California and School of Mathematical Sciences Tel Aviv University Tel Aviv Israel The generalized set packing problem is the following integer linear programming prob lem |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://theory.stanford.edu/~megiddo/pdf/setpack.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |