Reviews, Commentaries, etc. - Kakimura, Naonori

"I" report: NII Shonan meeting on "graph algorithm and combinatorial optimization"

神山 直之, 垣村尚徳

情報処理 (情報処理学会)  52 ( 7 ) 879 - 882 2011.07

Other, Joint Work,  ISSN  04478053

2-A-11 ロバスト独立システム(離散最適化(3))

垣村 尚徳, 牧野 和久

日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集 (社団法人日本オペレーションズ・リサーチ学会)  2011   134 - 135 2011.03

Other, Joint Work

Releasing Discrete Convex Optimization Solvers and Demonstration Softwares

Nobuyuki Tsuchimura, Satoko Moriguchi, Naonori Kakimura, Satoru Iwata, Kazuo Murota

IPSJ SIG Notes (一般社団法人情報処理学会)  2011 ( 4 ) 1 - 6 2011.01

Other, Joint Work,  ISSN  09196072

　View Summary

In discrete convex analysis, which is a unified framework of discrete convex functions based on the theory of matroids and submodular functions, efficient discrete optimization algorithms were proposed. In order to disseminate these theoretical results in application fields, we release softwares and web applications implementing algorithms developed in discrete convex analysis.

数理計画と組合せ的行列理論(<特集>最先端を目指す若手研究者達)

垣村 尚徳

オペレーションズ・リサーチ : 経営の科学 (社団法人日本オペレーションズ・リサーチ学会)  56 ( 1 ) 21 - 26 2011.01

Other, Single Work,  ISSN  00303674

　View Summary

組合せ的行列理論とその数理計画への応用を紹介する.組合せ的行列理論とは,行列の要素が零か非零かなどの組合せ的な情報を利用して解析を行う理論である.このような理論は工学に現れる大規模疎行列を扱う際に有用である.本稿では行列要素の符号に着目する定性的行列理論に焦点を当て,その線形計画と線形相補性問題への応用を述べる.

指定された頂点を通るパリティ制約付サイクルのパッキング

垣村尚徳, 河原林健一

日本応用数理学会年会講演予稿集 2011   125 - 126 2011

Other, Joint Work,  ISSN  1345-3378

行列*代数による対称構造物の釣合経路追跡法

相浦大司, 垣村尚徳, 室田一雄

日本応用数理学会年会講演予稿集 2011   233 - 234 2011

Other, Joint Work,  ISSN  1345-3378

Sign-Solvability in Mathematical Programming(<Special Feature>Quick Report on Doctoral Theses Recommended by IPSI SIGs)

Kakimura Naonori

IPSJ Magazine (一般社団法人情報処理学会)  50 ( 12 ) 1214 - 1214 2009.12

Other, Single Work,  ISSN  04478053

2-D-2 コーダル構造を持つ半正定値対称行列に対する極大クリーク行列分解の直接的な証明(離散・組合せ最適化(5))

垣村 尚徳

日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集 (社団法人日本オペレーションズ・リサーチ学会)  2009   229 - 230 2009.09

Other, Single Work

平成21年春季研究発表会ルポ(情報の窓)

稲川 敬介, 鵜飼 孝盛, 垣村 尚徳, 岸本 信, 水谷 友彦, 堀田 敬介

オペレーションズ・リサーチ : 経営の科学 (社団法人日本オペレーションズ・リサーチ学会)  54 ( 8 ) 499 - 503 2009.08

Other, Joint Work,  ISSN  00303674

Matching Structure of Symmetric Bipartite Graphs

KAKIMURA Naonori

IPSJ SIG Notes (一般社団法人情報処理学会)  2008 ( 84 ) 33 - 40 2008.09

Other, Single Work,  ISSN  09196072

　View Summary

A bipartite graph is said to be symmetric if it has symmetry of reflecting two vertex sets. This paper investigates matching structure of symmetric bipartite graphs. We first apply the Dulmage-Mendelsohn decomposition to a symmetric bipartite graph. The resulting components, which are matching-covered, turn out to have symmetry. We then decompose a matching-covered bipartite graph via an ear decomposition, which is a sequence of subgraphs obtained by adding an odd-length path repeatedly. We show that, if a matching-covered bipartite graph is symmetric, an ear decomposition can retain symmetry by adding no more than two paths. As an application of these decompositions to combinatorial matrix theory, we present a natural generalization of Polya's problem. We introduce the problem of deciding whether a rectangular matrix has a signing that is totally sign-nonsingular or not, where a rectangular matrix is totally sign-nonsingular if the sign of the determinant of each submatrix with row size is uniquely determined by the signs of the nonzero entries. We show that this problem can be solved in polynomial time with the aid of the matching structure of symmetric bipartite graphs.

Sign-Solvable Linear Complementarity Problems

KAKIMURA Naonori

IPSJ SIG Notes (Information Processing Society of Japan (IPSJ))  2007 ( 92 ) 49 - 56 2007.09

Other, Single Work,  ISSN  09196072

　View Summary

This paper presents a connection between qualitative matrix theory and linear complementarity problems (LCPs). An LCP is said to be sign-solvable if the set of the sign patterns of the solutions is uniquely determined by the sign patterns of the given coefficients. We provide a characterization for sign-solvable LCPs such that the coefficient matrix has nonzero diagonals,which can be tested in polynomial time. This characterization leads to an efficient combinatorial algorithm to find the sign pattern of a solution for these LCPs. The algorithm runs in O(γ) time,where γ is the number of the nonzero coefficients.

2-C-3 線形相補性問題の符号可解性(グラフ・ネットワーク)

垣村 尚徳

日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集 (社団法人日本オペレーションズ・リサーチ学会)  2007   142 - 143 2007.03

Other, Single Work

第4部 超ロバスト計算原理プロジェクト報告 超ロバスト計算原理プロジェクト 線形相補性問題の符号可解性

垣村尚徳

東京大学21世紀COE情報科学技術戦略コア 平成18年度 報告書    332 - 333 2007

Other, Single Work

The super robust calculation principle project. Special designation researcher and special designation assistant report. The combinative solution method of code solvable linear programming.

KAKIMURA HISANORI

東京大学21世紀COE情報科学技術戦略コア 平成17年度 報告書    357 - 358 2006

Other, Single Work

Combinatorial Matrix Analysis by Sign Patterns

垣村 尚徳, 岩田 覚

[O]perations research as a management science [r]esearch (社団法人日本オペレーションズ・リサーチ学会)  50 ( 12 ) 835 - 836 2005.12

Other, Joint Work,  ISSN  00303674

1-B-6 線形計画問題の符号可解性(組合せ最適化(1))

垣村 尚徳, 岩田 覚

日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集 (社団法人日本オペレーションズ・リサーチ学会)  2005   38 - 39 2005.09

Other, Joint Work

符号対称行列のSylvester指数(組合せ最適化(6))

垣村 尚徳, 岩田 覚

日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集 (社団法人日本オペレーションズ・リサーチ学会)  2004   228 - 229 2004.09

Other, Joint Work