Approximation with a fixed number of solutions of some multiobjective maximization problems

详细信息    查看全文

• 作者：Cristina Bazgan ; Laurent Gourv¨¨s ; J¨¦r?me Monnot
• 关键词：Multiobjective maximization problems ; Approximation ; Submodular functions ; Bisection ; Matching ; Coverage
• 刊名：Journal of Discrete Algorithms
• 出版年：2013
• 出版时间：September, 2013
• 年：2013
• 卷：22
• 期：Complete
• 页码：19-29
• 全文大小：302 K

文摘

We investigate the problem of approximating the Pareto set of some multiobjective optimization problems with a given number of solutions. 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 Submodular Symmetric Function (and special cases), Max Bisection, and Max Matching and also for the k-objective versions of Max Coverage, Heaviest Subgraph, Max Coloring of interval graphs.