权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

局所構造を利用した高速なアルゴリズムの開発

使用局部结构开发高速算法

基本信息

批准号：
19K22841
负责人：
牧野和久
金额：
$ 4.16万
依托单位：
Kyoto University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Challenging Research (Exploratory)
财政年份：
2019
资助国家：
日本
起止时间：
2019-06-28 至 2024-03-31
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-19K22841/
关键词：
アルゴリズムアルゴリズム論主双対法オンライン問題

项目摘要

離散最適化分野で未解決であった劣モジュラコストをもつ4－分割問題に対する初めの多項式時間アルゴリズムを構築した。またこの論文で用いたアルゴリズムフレームワークでは、４より大きな個数に分割する問題は解けないことも示した。また、再配置問題においてはその問題の離散構造を明らかにするとともに、さまざまな自然な設定の下での多項式時間アルゴリズム、近似アルゴリズム、制約を緩和した精度を保証したアルゴリズムなどの構築に成功した。それ以外にも、１．k彩色遷移問題とは，無向グラフと二つのk彩色が与えられた際に，k彩色であるという条件を保ったまま一度に一つの頂点の色を(局所的に)変更し，一方の彩色から他方の彩色へ変換することができるか否かを判定する問題である．本研究では，遷移制約をもつk彩色遷移問題を扱い，遷移制約が有向サイクルや特殊なマルチツリーで与えられる場合に，同問題が高速に(より正確には線形時間で)解けることを示した．２．ある特殊な整数計画問題に対し，解空間の局所的な構造について解析した．具体的には，整数解を求める問題を実数解を求める問題へ緩和した際に，緩和した問題の最適解の（局所的な）近傍に最適整数解が存在することを示した．これにより．この特殊な整数計画問題に対して，理論的に高速な分枝限定法（アルゴリズム）を開発した．

Discrete optimization segmentation is an unsolved problem. It is a 4-partition problem. This paper is about the problem of how to divide the number of words into four parts. The discrete structure of the problem is clearly defined, and the polynomial time under the natural setting is approximated, and the constraint is relaxed to ensure the success of the construction. The color shift problem of 1.k is the problem of non-directional color shift, k color shift. In this paper, we study the problem of color migration with migration constraints. In the case of migration constraints, the same problem can be solved at high speed. 2. In the case of special integer projects, the problem of spatial structure can be solved. The concrete integer solution of the problem is solved numerically. The optimal solution of the problem is solved numerically.これにより. This special integer project problem is developed by theoretical high speed branch constraint method.