Scholarlink

<p>In this paper, we study the independent quadratic assignment problem which is a variation of the well-known Koopmans–Beckman quadratic assignment problem. The problem is strongly NP-hard and is also hard to approximate. Some polynomially solvable special cases are identified along with a complete characterization of linearizable instances of the problem, the validity of which is shown to be verifiable in linear time. This improves the existing quadratic bound for this problem. Additional complexity results are also presented.</p>

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

The independent quadratic assignment problem: complexity and polynomially solvable special cases

  • 期刊论文

  • 发表日期：

    2025年5月21日

查看全文
  • Ante Ćustić,
  • Wei Yang,
  • Yang Wang,
  • Abraham P. Punnen

摘要

In this paper, we study the independent quadratic assignment problem which is a variation of the well-known Koopmans–Beckman quadratic assignment problem. The problem is strongly NP-hard and is also hard to approximate. Some polynomially solvable special cases are identified along with a complete characterization of linearizable instances of the problem, the validity of which is shown to be verifiable in linear time. This improves the existing quadratic bound for this problem. Additional complexity results are also presented.