Name
Abstract | ||
|---|---|---|
The multiobjective set covering problem (MOSCP), an NP-hard combinatorial optimization problem, has received limited attention in the literature from the perspective of approximating its Pareto set. The available algorithms for approximating the Pareto set do not provide a bound for the approximation error. In this study, a polynomial-time algorithm is proposed to approximate an element in the weak Pareto set of the MOSCP with a quality that is known. A tolerance function is defined to identify the approximation quality and is derived for the proposed algorithm. It is shown that the tolerance function depends on the characteristics of the problem and the weight vector that is used for computing the approximation. For a set of weight vectors, the algorithm approximates a subset of the weak Pareto set of the MOSCP. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1007/s11590-018-1267-5 | Optimization Letters |
Keywords | Field | DocType |
Approximation algorithm,Approximation error,Representation,Combinatorial optimization,Efficient solution,Max-ordering | Approximation algorithm,Set cover problem,Mathematical optimization,Combinatorial optimization problem,Weight,Combinatorial optimization,Approximation error,Pareto principle,Mathematics | Journal |
Volume | Issue | ISSN |
13 | 1 | 1862-4480 |
Citations | PageRank | References |
0 | 0.34 | 13 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Lakmali Weerasena | 1 | 0 | 0.68 |
| Margaret M. Wiecek | 2 | 213 | 22.90 |