Name
Abstract | ||
|---|---|---|
We survey approximation algorithms for some well-known and very natural combinatorial optimization problems, the minimum set covering, the minimum vertex covering, the maximum set packing, and maximum independent set problems; we discuss their approximation performance and their complexity. For already known results, any time we have conceived simpler proofs than those already published, we give these proofs, and, for the rest, we cite the simpler published ones. Finally, we discuss how one can relate the approximability behavior (from both a positive and a negative point of view) of vertex covering to the approximability behavior of a restricted class of independent set problems. |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1145/254180.254190 | ACM Comput. Surv. |
Keywords | Field | DocType |
approximability behavior,independent set problem,maximum independent set problem,approximation algorithm,approximation performance,maximum set packing,natural combinatorial optimization problem,constrained optimization,algorithm analysis,simpler proof,optimal solution,minimum vertex,approximation algorithms,problem complexity,negative point,combinatorial algorithms,maximum independent set,vertex cover,independent set,set cover | Approximation algorithm,Discrete mathematics,Mathematical optimization,Packing problems,Vertex (geometry),Computer science,L-reduction,Theoretical computer science,Combinatorial optimization,Independent set,Set packing,Covering problems | Journal |
Volume | Issue | ISSN |
29 | 2 | 0360-0300 |
Citations | PageRank | References |
50 | 3.22 | 44 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vangelis T. Paschos | 1 | 80 | 4.72 |