Name
Title | ||
|---|---|---|
Approximation with a fixed number of solutions of some biobjective maximization problems |
Abstract | ||
|---|---|---|
We investigate the problem of approximating the Pareto set of biobjective optimization problems with a given number of solutions. This task is relevant for two reasons: (i) Pareto sets are often computationally hard so approximation is a necessary tradeoff to allow polynomial time algorithms; (ii) limiting explicitly the size of the approximation allows the decision maker to control the expected accuracy of approximation and prevents him to be overwhelmed with too many alternatives. Our purpose is to exploit general properties that many well studied problems satisfy. We derive existence and constructive approximation results for the biobjective versions of Max Bisection, Max Partition, Max Set Splitting and Max Matching. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/978-3-642-29116-6_20 | WAOA |
Keywords | Field | DocType |
max matching,biobjective optimization problem,max set splitting,max bisection,max partition,derive existence,biobjective version,pareto set,fixed number,constructive approximation result,biobjective maximization problem,decision maker,approximation,tradeoff | Mathematical optimization,Combinatorics,Computer science,Constructive,Multi-objective optimization,Partition (number theory),Time complexity,Polynomial-time approximation scheme,Pareto principle,Maximization,Decision maker | Conference |
Citations | PageRank | References |
2 | 0.47 | 20 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Cristina Bazgan | 1 | 679 | 62.76 |
| Laurent Gourvès | 2 | 241 | 30.97 |
| Jérôme Monnot | 3 | 512 | 55.74 |