Output details
11 - Computer Science and Informatics
University of Edinburgh
Output title
Succinct approximate convex Pareto curves
Type
E - Conference contribution
DOI
-
Name of conference/published proceedings
Proceedings of the nineteenth annual ACM-SIAM Symposium on Discrete Algorithms (SODA '08)
Volume number
-
Issue number
-
First page of article
74
ISSN of proceedings
-
Year of publication
2008
Number of additional authors
1
Additional information
<12> Originality: We propose the concept of ε-convex Pareto (ε-CP) set as the appropriate notion of approximation of convex multi-objective optimization problems.
Significance: We characterize when an ε-CP can be constructed in polynomial time in terms of an efficient routine Comb for optimizing (exactly or approximately) monotone linear combinations of the objectives. We investigate the problem of computing minimum size ε-convex Pareto sets, and present general algorithms with provably tight approximation guarantees.
Rigour: A novel framework and algorithms for the approximation of convex multi-objective problems.
Interdisciplinary
-
Cross-referral requested
-
Research group
F - Laboratory for Foundations of Computer Science
Citation count
7
Proposed double-weighted
No
Double-weighted statement
-
Reserve for a double-weighted output
No
Non-English
No
English abstract
-
