Structural Analysis of Mathematical Programming based on CombinatorialMatrix Theory

基于组合矩阵理论的数学规划结构分析

• 批准号: 21760057
• 负责人: KAKIMURA Naonori
• 金额: $ 2.75万
• 依托单位: The University of Tokyo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2009
• 资助国家: 日本
• 起止时间: 2009 至 2011
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-21760057/
• 关键词: 組合せ最適化; 定性的行列理論; 疎性; マッチング; グラフアルゴリズム; 点素サイクル; ナップサック問題; フィードバック点集合; 線形相補性問題; ビンパッキング問題; 近似アルゴリズム; 組合せ的行列理論; 数理計画; 半正定値対称行列

Mathematical programming is a branch of mathematics concerned with optimization problems, in which one aims to find the best solution subject to some constraints, and it can be applied to a variety of engineering fields such as operations research. Combinatorial matrix theory is an approach to understand matrix structure using combinatorial methodology, which is useful for structural analysis of large linear systems in practice. In this research, we have analyzed mathematical programming problems based on combinatorial properties such as sign patterns or sparsity. In addition, we have developed combinatorial matrix theory in terms of mathematical programming applications.

数学编程是与优化问题有关的数学分支，其中一个人旨在找到受某些约束的最佳解决方案，并且可以应用于各种工程领域，例如运营研究。组合基质理论是一种使用组合方法来理解基质结构的方法，该方法可用于实践中大型线性系统的结构分析。在这项研究中，我们根据组合特性（例如符号模式或稀疏性）分析了数学编程问题。此外，我们还根据数学编程应用开发了组合矩阵理论。

项目成果

コーダル構造を持つ半正定値対称行列に対する極大クリーク行列分解の直接的な証明

弦结构正半定对称矩阵最大团矩阵分解的直接证明

• 发表时间: 2009
• 作者: Fritz Eisenbrand;Naonori Kakimura;Thomas Rothvoss;Laura Sanita;Aki-Hiro Sato;Naonori Kakimura;佐藤彰洋;N. Kakimura;佐藤彰洋;垣村尚徳
• 通讯作者: 垣村尚徳

順序交換性を持つ集合被覆問題

具有顺序交换性的集合覆盖问题

• 发表时间: 2011
• 作者: Hidekazu Kodama;Yosinobu Yasuno;Munehiro Date and Eiichi Fukada;佐藤彰洋;N. Kakimura and K. Kawarabayashi;安野功修,児玉秀和;垣村尚徳,牧野和久;古川猛夫,児玉秀和;垣村尚徳(withF.Eisenbrand,T.RothvossandL.Sanita)
• 通讯作者: 垣村尚徳(withF.Eisenbrand,T.RothvossandL.Sanita)

A Direct Proof for the Matrix Decomposition of Chordal-Structured Positive Semidefinite Matrices

弦结构正半定矩阵矩阵分解的直接证明

• DOI: 10.1016/j.laa.2010.04.012
• 发表时间: 2010
• 期刊: Linear Algebra and Its Applications
• 影响因子: 1.1
• 作者: Aki-Hiro SATO;Takaki HAYASHI;Naonori Kakimura
• 通讯作者: Naonori Kakimura

Erdos-Posa Property and Its Algorithmic Applications - Parity Constraints Subset Feedback Set, and Subset Packing

Erdos-Posa性质及其算法应用——奇偶约束子集反馈集和子集打包

• 发表时间: 2012
• 作者: N. Kakimura;K. Kawarabayashi;and Y. Kobayashi
• 通讯作者: and Y. Kobayashi

Set Covering with OrderedReplacement - Additive and Multiplicative Gaps

使用 OrderedReplacement 设置覆盖 - 加法和乘法间隙

• 发表时间: 2011
• 作者: F. Eisenbrand;N. Kakimura;T. Rothvoss;and L. Sanita
• 通讯作者: and L. Sanita