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

Scaling and proximity properties of discrete optimization

离散优化的缩放和邻近属性

基本信息

批准号：
17K00037
负责人：
森口聡子
金额：
$ 2.25万
依托单位：
Tokyo Metropolitan University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2017
资助国家：
日本
起止时间：
2017-04-01 至 2024-03-31
项目状态：
已结题

项目摘要

本研究は，離散最適化に対して，スケーリング技法を軸とするアルゴリズム効率化のための理論体系を構築することを目的とし，また理論の応用を見据えて，研究を推進した．スケーリングとは，定義域の偶数点のみを見る，などのように，目盛を間引いた関数近似の導入で効率化を図る技法で，古典的なネットワークフローや資源配分問題で多くの成功例が知られている．離散凸解析のこれまでの研究により，いくつかの離散凸関数最小化に対して，スケーリング技法の有効性と近接定理による理論保証が明らかになっている．本研究では，これまでスケーリング技法や近接定理について考えられていなかったより広い離散関数のクラスに対する拡張と理論構築を試み，効率的なアルゴリズムが構築可能なクラスの解明を進めていった．離散凸最適化においては，Ｍ凸関数，Ｌ凸関数，整凸関数，マルチモジュラ関数など，種々の関数クラスが考察される．それらの間の包含関係や，そのうちの２つのクラスの共通部分がどのようなものになるのかを，網羅的に整理した．これによって，様々な分野の研究者が離散凸関数の概念を容易に理解できるようになる．また，離散凸構造の多面体的表現を解明していった．複数の離散凸構造の間の包含関係や，そのうちの２つのクラスの共通部分の理解に，多面体的表現が有用であったことから始まった研究であるが，多面体的表現により，スケーリング，近接性に関する議論がしやすくなり，また整数計画の理論の応用やソルバーの利用がしやすくなるという今後の展開が開ける．

This study aims to advance the theory of discrete optimization. The problem of resource allocation is solved by the method of introducing the approximation of the number of variables into the domain. The study of discrete convex analysis and the minimization of discrete convex relations are discussed in this paper. In this paper, we try to construct the theory of approximation theorem, and construct the theory of approximation theorem. Discrete-convex optimization, M convex number, L convex number, integer convex number, The common part of the relationship between the two parts is the arrangement of the net. The concept of discrete convex number is easy to understand by researchers. The behavior of discrete convex structures and polyhedra is clarified. The inclusion relations between discrete convex structures and the understanding of the common parts of the two structures are useful for the study of the behavior of polyhedra. The discussion of the relationship between proximity and the behavior of polyhedra is also useful for the development of the theory of integer projects.