研究者詳細 - 垣村　尚徳

総説・解説等 - 垣村　尚徳

分割表示 >> ／全件表示 37 件中 1 - 37 件目

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

垣村尚徳

数理科学（サイエンス社） 59 （ 12 ） 22 - 29 2021年12月

ISSN 0386-2240

大規模ネットワーク解析のための組合せ最適化アルゴリズム

垣村尚徳

回路とシステムワークショップ論文集 Workshop on Circuits and Systems （[電子情報通信学会]） 32 55 - 60 2019年08月

その他, 単著

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

垣村尚徳

数理科学（サイエンス社） 54 （ 8 ） 45 - 51 2016年08月

その他, 単著, ISSN 0386-2240

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

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

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

その他, 共著

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

垣村尚徳, 河原林健一

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

その他, 共著, ISSN 1345-3378

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

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

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

その他, 共著

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

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

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

その他, 共著

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

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

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

その他, 共著, ISSN 1345-3378

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

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

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

その他, 共著

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

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

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

その他, 共著

DS-1-13 線形相補性問題のパラメータ化計算量(DS-1.COMP-ELC学生シンポジウム,シンポジウムセッション)

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

電子情報通信学会総合大会講演論文集（一般社団法人電子情報通信学会） 2015 （ 1 ） "S - 25"-"S-26" 2015年02月

その他, 共著

Minimum-Cost b-Edge Dominating Sets on Trees

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

研究報告アルゴリズム（AL）（一般社団法人情報処理学会） 2015 （ 2 ） 1 - 6 2015年02月

その他, 共著, ISSN 0919-6072

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.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月

その他, 共著

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

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

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

その他, 共著

DS-1-4 線形相補性問題の完全双対整数性(DS-1.COMP-ELC学生シンポジウム,シンポジウムセッション)

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

電子情報通信学会総合大会講演論文集（一般社団法人電子情報通信学会） 2014 （ 1 ） "S - 7"-"S-8" 2014年03月

その他, 共著

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

垣村尚徳

数学セミナー（日本評論社） 53 （ 1 ） 25 - 29 2014年01月

その他, 単著, ISSN 0386-4960

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

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

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

その他, 共著

DS-1-8 疎な線形相補性問題に対する組合せ的アルゴリズム(DS-1.COMP学生シンポジウム,シンポジウムセッション)

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

電子情報通信学会総合大会講演論文集（一般社団法人電子情報通信学会） 2013 （ 1 ） "S - 15"-"S-16" 2013年03月

その他, 共著

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

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

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

その他, 共著

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

垣村尚徳, 高松瑞代

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

その他, 共著

"I"見聞録(第30回)第1回NII湘南会議--グラフアルゴリズムと組合せ最適化

神山直之, 垣村尚徳

情報処理（情報処理学会） 52 （ 7 ） 879 - 882 2011年07月

その他, 共著, ISSN 04478053

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

垣村尚徳, 牧野和久

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

その他, 共著

離散凸最適化ソルバとデモンストレーションソフトウェアの公開

土村展之, 森口聡子, 垣村尚徳, 岩田覚, 室田一雄

情報処理学会研究報告. AL, アルゴリズム研究会報告（一般社団法人情報処理学会） 2011 （ 4 ） 1 - 6 2011年01月

その他, 共著, ISSN 09196072

マトロイド・劣モジュラ関数の研究の流れを汲んだ離散凸解析による統一的枠組みの中で,離散最適化問題を効率的に解く各種アルゴリズムが提案されてきた.離散凸解析理論の普及を目的として,これらの成果を応用分野の研究者・実務家が享受できるように,関連するアルゴリズムを紹介するデモンストレーションソフトウェアと,アプリケーションソフトウェアを開発した.ソルバ及びデモンストレーションソフトウェアの WEB 公開について報告する.

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

垣村尚徳

オペレーションズ・リサーチ : 経営の科学（社団法人日本オペレーションズ・リサーチ学会） 56 （ 1 ） 21 - 26 2011年01月

その他, 単著, ISSN 00303674

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

垣村尚徳, 河原林健一

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

その他, 共著, ISSN 1345-3378

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

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

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

その他, 共著, ISSN 1345-3378

数理計画法における符号可解性(<特集>研究会推薦博士論文速報)

垣村尚徳

情報処理（一般社団法人情報処理学会） 50 （ 12 ） 1214 - 1214 2009年12月

その他, 単著, ISSN 04478053

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

垣村尚徳

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

その他, 単著

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

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

オペレーションズ・リサーチ : 経営の科学（社団法人日本オペレーションズ・リサーチ学会） 54 （ 8 ） 499 - 503 2009年08月

その他, 共著, ISSN 00303674

対称二部グラフのマッチング構造

垣村尚徳

情報処理学会研究報告. AL, アルゴリズム研究会報告（一般社団法人情報処理学会） 2008 （ 84 ） 33 - 40 2008年09月

その他, 単著, ISSN 09196072

対称二部グラフとは,二つの頂点集合を分ける軸で線対称性を持つ二部グラフである.本発表では,対称な二部グラフのマッチング構造を調べることを目的とする.まず対称な二部グラフに対しDulmage-Mendelsohn分解を行なうと,得られた成分(マッチング被覆グラフ)は対称性を有することが分かる.マッチング被覆二部グラフは,耳分解により,ある辺に長さ奇数のパスを繰り返し付け加えることで構成できる.本研究では,マッチング被覆二部グラフが対称ならば高々2本のパスを付け加えることで対称性を保持したまま耳分解できることを示す.さらに,対称二部グラフの組合せ的行列理論への応用として,Polyaの問題を一般化した問題を提案し,その問題が多項式可解であることを述べる.

線形相補性問題の符号可解性

垣村尚徳

情報処理学会研究報告. AL, アルゴリズム研究会報告（一般社団法人情報処理学会） 2007 （ 92 ） 49 - 56 2007年09月

その他, 単著, ISSN 09196072

線形相補性問題(LCP)とは,線形計画や凸二次計画を特殊ケースとして含む数理計画問題である.LCPが符号可解であるとは,解の取りうる符号パターンの集合が係数要素の大きさによらずに定まることを言う.本研究では,係数行列の対角要素が全て非零であるLCPに対して,その符号可解性に対する必要十分条件を与える.そして,符号可解LCPの解の符号パターンを効率的に得るための組合せ的解法を提案する.その計算量はO(γ)(γは係数の非零要素数の和)である.

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

垣村尚徳

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

その他, 単著

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

垣村尚徳

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

その他, 単著

超ロバスト計算原理プロジェクト特任研究員・特任アシスタント報告符号可解線形計画の組合せ的解法

垣村尚徳

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

その他, 単著