[计算机科学] 优化问题的K-交换技术的有向图描述 置换与自适应算法系统 [推广有奖]

摘要翻译：
本文介绍了元素交换技术在排列优化中的应用。提出了问题的多层次描述，这是理解排列优化问题（如排序、调度、旅行商问题）本质和复杂性的基础。该描述基于几种置换邻域（例如，通过目标函数的改进）。我们提出的操作有向图及其类型可以被认为是理解置换上组合优化问题的凸性和多项式可解性的一种方法。讨论了问题分析和层次启发式设计的问题。通过对单个问题的分析和求解策略（轨迹）的选择/设计，得到了一个多层次的自适应算法系统。
---
英文标题：
《Digraph description of k-interchange technique for optimization over
  permutations and adaptive algorithm system》
---
作者：
Mark Sh. Levin
---
最新提交年份：
2011
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Data Structures and Algorithms        数据结构与算法
分类描述：Covers data structures and analysis of algorithms. Roughly includes material in ACM Subject Classes E.1, E.2, F.2.1, and F.2.2.
涵盖数据结构和算法分析。大致包括ACM学科类E.1、E.2、F.2.1和F.2.2中的材料。
--
一级分类：Computer Science        计算机科学
二级分类：Artificial Intelligence        人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--
一级分类：Mathematics        数学
二级分类：Optimization and Control        优化与控制
分类描述：Operations research, linear programming, control theory, systems theory, optimal control, game theory
运筹学，线性规划，控制论，系统论，最优控制，博弈论
--

---
英文摘要：
  The paper describes a general glance to the use of element exchange techniques for optimization over permutations. A multi-level description of problems is proposed which is a fundamental to understand nature and complexity of optimization problems over permutations (e.g., ordering, scheduling, traveling salesman problem). The description is based on permutation neighborhoods of several kinds (e.g., by improvement of an objective function). Our proposed operational digraph and its kinds can be considered as a way to understand convexity and polynomial solvability for combinatorial optimization problems over permutations. Issues of an analysis of problems and a design of hierarchical heuristics are discussed. The discussion leads to a multi-level adaptive algorithm system which analyzes an individual problem and selects/designs a solving strategy (trajectory).
---
PDF链接：
https://arxiv.org/pdf/1102.4498