Scholarlink

<p>We study a particular class of greedy algorithms for combinatorial optimization problems and present a generalized version of this algorithmic pattern encompassing several previously published algorithms. We analyze the properties of the solutions produced by such algorithms and provide proofs of their optimality through the concept of <i>lexicographic max-ordering</i>. By presenting a unified formulation of this class of greedy algorithms, we hope to facilitate the development of new such algorithms and to provide a deeper understanding on the properties of existing ones. To illustrate the utility of our results, we present two case studies, where we study two previously published optimization algorithms and show that they can be seen as instances of the proposed general algorithmic pattern. In doing so, we provide alternative proofs of correctness for these algorithms and draw new conclusions about their properties.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

A general algorithmic pattern for finding lexicographic max-ordering solutions to combinatorial multicriteria optimization problems

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年8月1日

查看全文
  • Zoe Dumoulin,
  • María Andreína Francisco Rodríguez,
  • Filip Malmberg

摘要

We study a particular class of greedy algorithms for combinatorial optimization problems and present a generalized version of this algorithmic pattern encompassing several previously published algorithms. We analyze the properties of the solutions produced by such algorithms and provide proofs of their optimality through the concept of lexicographic max-ordering. By presenting a unified formulation of this class of greedy algorithms, we hope to facilitate the development of new such algorithms and to provide a deeper understanding on the properties of existing ones. To illustrate the utility of our results, we present two case studies, where we study two previously published optimization algorithms and show that they can be seen as instances of the proposed general algorithmic pattern. In doing so, we provide alternative proofs of correctness for these algorithms and draw new conclusions about their properties.