Reviews, Commentaries, etc. - Kakimura, Naonori

離散数学入門 : グラフ,マトロイドから離散凸解析まで (特集 離散数学に親しむ)

垣村 尚徳

数理科学 (サイエンス社)  59 ( 12 ) 22 - 29 2021.12

ISSN  0386-2240

Combinatorial Optimization for Network Analysis

垣村 尚徳

回路とシステムワークショップ論文集 Workshop on Circuits and Systems ([電子情報通信学会])  32   55 - 60 2019.08

Other, Single Work

情報科学と線形代数 : ネットワーク解析と行列固有値 (特集 線形代数の探究 : 様々な問題を通してみるその姿)

垣村 尚徳

数理科学 (サイエンス社)  54 ( 8 ) 45 - 51 2016.08

Other, Single Work,  ISSN  0386-2240

ネットワーク型交渉ゲームの安定化アルゴリズム

伊藤健洋, 垣村尚徳, 神山直之, 小林佑輔, 岡本吉央

情報処理学会研究報告(Web) 2016 ( AL-157 ) VOL.2016‐AL‐157,NO.3 (WEB ONLY) 2016.02

Other, Joint Work

イマージョンを含まないグラフに対する彩色アルゴリズム

垣村尚徳, 河原林健一

日本応用数理学会年会講演予稿集(CD-ROM) 2016   ROMBUNNO.9GATSU13NICHI,11:00,3E,3 2016

Other, Joint Work,  ISSN  1345-3378

1-A-10 広告予算配分に対する閾値影響モデル(離散最適化(2))

宮内 敦史, 岩政 勇仁, 福永 拓郎, 垣村 尚徳

日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集 (公益社団法人日本オペレーションズ・リサーチ学会)  2015   24 - 25 2015.09

Other, Joint Work

2-A-4 重み付きマトロイド交わり問題に対する厳密解法と近似解法(離散最適化(3))

黄 建中, 垣村 尚徳, 神山 直之

日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集 (公益社団法人日本オペレーションズ・リサーチ学会)  2015   174 - 175 2015.09

Other, Joint Work

学術情報ネットワークにおける最適キャッシュ配置

横井優, NGUYEN Hau Than, 松岡達也, 小林佑輔, 垣村尚徳, 河原林健一

日本応用数理学会年会講演予稿集(CD-ROM) 2015   ROMBUNNO.9GATSU9NICHI,09:30,A,2 2015.09

Other, Joint Work,  ISSN  1345-3378

1-B-13 線形相補性問題のパラメータ化計算量(学生セッション:離散最適化(3))

澄田 範奈, 垣村 尚徳, 牧野 和久

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

Other, Joint Work

1-C-3 木における最小費用b-辺支配集合問題(離散最適化(1))

伊藤 健洋, 垣村 尚徳, 神山 直之, 小林 佑輔, 岡本 吉央

日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集 (公益社団法人日本オペレーションズ・リサーチ学会)  2015   44 - 45 2015.03

Other, Joint Work

DS-1-13 Parameterized Complexity of the Linear Complementarity Problem

Sumita Hanna, Kakimura Naonori, Makino Kazuhisa

Proceedings of the IEICE General Conference (一般社団法人電子情報通信学会)  2015 ( 1 ) "S - 25"-"S-26" 2015.02

Other, Joint Work

Minimum-Cost b-Edge Dominating Sets on Trees

Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto

IPSJ SIG Notes (Information Processing Society of Japan (IPSJ))  2015 ( 2 ) 1 - 6 2015.02

Other, Joint Work,  ISSN  0919-6072

　View Summary

We consider the minimum-cost b-edge dominating set problem. This is a generalization of the edge dominating set problem, but the computational complexity for trees is an astonishing open problem. We make steps toward the resolution of this open problem in the following three directions. (1) We give the first combinatorial polynomial-time algorithm for paths. Prior to our work, the polynomial-time algorithm for paths used linear programming, and it was known that the linear-programming approach could not be extended to trees. Thus, our algorithm would yield an alternative approach to a possible polynomial-time algorithm for trees. (2) We give a fixed-parameter algorithm for trees with the number of leaves as a parameter. Thus, a possible NP-hardness proof for trees should make use of trees with unbounded number of leaves. (3) We give a fully polynomial-time approximation scheme for trees. Prior to our work, the best known approximation factor was two. If the problem is NP-hard, then a possible proof cannot be done via a gap-preserving reduction from any APX-hard problem unless P = NP.

1-C-11 方向つき線形相補性問題の計算複雑度(離散最適化(3))

澄田 範奈, 垣村 尚徳, 牧野 和久

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

Other, Joint Work

1-G-10 線形相補性問題の完全双対整数性(離散最適化(2))

澄田 範奈, 垣村 尚徳, 牧野 和久

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

Other, Joint Work

DS-1-4 On Total Dual Integrality of the Linear Complementarity Problem

Sumita Hanna, Kakimura Naonori, Makino Kazuhisa

Proceedings of the IEICE General Conference (一般社団法人電子情報通信学会)  2014 ( 1 ) "S - 7"-"S-8" 2014.03

Other, Joint Work

詰め込み問題とグラフマイナー理論 (特集 グラフ理論の新展開)

垣村 尚徳

数学セミナー (日本評論社)  53 ( 1 ) 25 - 29 2014.01

Other, Single Work,  ISSN  0386-4960

2-F-2 二部グラフ上の最適予算配分問題に対する高速アルゴリズム(離散最適化(4))

相馬 輔, 垣村 尚徳, 河原林 健一

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

Other, Joint Work

DS-1-8 Combinatorial Algorithms for Sparse Linear Complementarity Problems

Sumita Hanna, Kakimura Naonori, Makino Kazuhisa

Proceedings of the IEICE General Conference (一般社団法人電子情報通信学会)  2013 ( 1 ) "S - 15"-"S-16" 2013.03

Other, Joint Work

1-C-10 疎な線形相補性問題に対する組合せ的アルゴリズム(離散最適化(1))

澄田 範奈, 垣村 尚徳, 牧野 和久

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

Other, Joint Work

1-D-5 デルタマトロイド制約付きマッチング(離散最適化(1))

垣村 尚徳, 高松 瑞代

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

Other, Joint Work

"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