Details of a Researcher - Kakimura, Naonori

Reviews, Commentaries, etc. - Kakimura, Naonori

Division display 1 - 20 of about 37 ／ All the affair displays >>

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

垣村尚徳

数理科学 (サイエンス社) 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

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