講演概要


第14回 研究会

日　時：2015年 2/20(金) 16:00 〜 18:00
会　場：東京大学 本郷キャンパス 工学部 6号館 2階 61号講義室

講演者１： J. Christopher Beck (University of Toronto)
講演題目： Linear and Mixed Integer Linear Programming for AI Planning
講演概要：
Planning is one of the traditional problems studied in artificial intelligence (AI) because the ability to decide on a set of actions to execute to achieve a goal is an important component of intelligent behaviour. This problem has not traditionally been studied in Operations Research (OR) and, indeed, "planning" refers to a very different problem in OR. However, there is an increasing number of examples of AI planning researchers adopting linear programming and mixed integer linear programming to solve AI planning problems. In this talk, I will introduce the AI planning problem, discuss standard solution techniques, and present examples of three ways that linear and mixed integer linear programming have been used for AI planning: as an alternative approach to solve the planning problem; as an addition to a planning algorithm to deal with numeric resources and constraints; and as a technique to compute better search guidance heuristics within a planning algorithm.

講演者２： Alex Fukunaga (University of Tokyo)
講演題目： On the delete relaxation for domain-independent planning
講演概要：
The delete relaxation (h+) is a widely studied lower bound for domain-independent planning problems in AI. The delete relaxation is is derived by modifying the original planning problem specification such that propositions are never removed from the state representation. Although h+ is easier to solve than the original planning problem, h+ is itself NP-complete. I will survey approaches to computing h+ including a recent integer programming formulation. I will also survey approximations to h+ and their application to quickly searching for (non-optimal) solutions to planning problems.


第13回 研究会

日　時：2014年 12/13(土) 14:00 〜
会　場：東京大学 本郷キャンパス 工学部 6号館 3階 セミナー室A･D

講演者１： 大舘 陽太 （北陸先端科学技術大学院大学）
講演題目： グラフ同型性判定問題: 幅パラメータと禁止部分構造
講演概要：
グラフ同型性判定問題とは，二つのグラフが与えられた時にその二つが「同じ」であるかどうか判定する問題である． この問題はグラフに関する問題で最も自然な問題であるにも関わらず，高速なアルゴリズムも困難性も知られていない． 他のグラフ問題と同様に，入力を制限した場合には多くの結果が知られているが，その中で「幅パラメータ」と 「禁止部分構造」に関する結果を紹介する．内容は，Pascal Schweitzer 氏 (RWTH Aachen) との共同研究に基づく．

講演者２： 福永 拓郎 （国立情報学研究所・JST, ERATO, 河原林巨大グラフプロジェクト）
講演題目： スパイダー被覆によるネットワークアクティベーションアルゴリズム
講演概要：
ネットワーク設計問題に対する近似アルゴリズムの一つに，スパイダー被覆アルゴリズムと呼ばれるものがある．これは貪欲アルゴリズムの一種であり，スパイダーと呼ばれるグラフを繰り返し選択することでネットワークを構築する．本講演ではまず最初にスパイダー被覆アルゴリズムの基礎について解説する．その後，ネットワーク設計問題をより一般化したネットワークアクティベーション問題に対するスパイダー被覆アルゴリズムについて，線形計画緩和に基づいた新たな解析を与える．またその過程において，大きな整数性ギャップを持つ線形計画緩和を持ち上げるための新たな手法や，アルゴリズムの進捗を表すための新たなポテンシャル関数を提案する．これにより，連結度制約が違反ペナルティを持つ場合に対しても近似アルゴリズムを与えることが可能となる．


第12回 研究会

日　時：2014年 10/4(土) 14:00 〜
会　場：東京大学 本郷キャンパス 工学部 6号館 3階 セミナー室A･D

講演者１： 奥野 貴之 （東京理科大学）
講演題目： 2次元箱型添字集合つき半無限計画問題に対するαBB切除平面法の研究
講演概要：
半無限計画問題とは有限個の決定変数と無限個の不等式制約をもった最適化問題である. 半無限計画問題の難しさのひとつは, 与えられた点の実行可能性を調べるためにある非凸最適化問題の大域的最適解を求める必要性にあるが, αBB切除平面法とは, その非凸最適化問題を必ずしも解く必要がなく, 代わりに非凸最適化問題を近似した凸最適化問題を逐次的に解きながら最適解に収束する点列を生成する手法である. 本講演では, 半無限計画問題に関する基本的な事項の説明に重点を置きつつ, 講演者らのαBB切除平面法に関する最近の研究を紹介する. 尚, この研究は林俊介氏（東北大学）とSoon-Yi Wu氏（台湾国立成功大学）との共同研究である.

講演者２： 岡本 吉央 （電気通信大学）
講演題目： 多角形領域の直径と半径を計算するアルゴリズム
講演概要：
単純多角形の中に単純多角形が障害物として置かれた多角形領域の直径と半径を厳密に計算するアルゴリズムを議論する．障害物の有無や考えるノルムがL1であるかL2であるか，ということに依存して，計算量も変化する．障害物が存在しない場合，計算量は(ほぼ)線形であるが，障害物が存在する場合，計算量は極端に大きくなる(が，多項式である)．本講演では，この違いが何に由来するのかという理由，そして，その中で高速化を達成するアルゴリズム的アイディアの一端を紹介する．細かい証明は全く行わず，「気持ち」を共有することに重点を置く．この内容は，Sang Won Bae氏，Matias Korman氏，Joseph Mitchell氏，Valentin Polishchuk氏，Haitao Wang氏 との共同研究に基づく．


第11回 研究会

日　時：2014年 4/19(土) 14:00 〜
会　場：東京大学 本郷キャンパス 工学部 6号館 3階 セミナー室A･D

講演者１： 谷川 眞一 （京都大学）
講演題目： 低ランク半正定値行列補完問題の解の一意性に関する研究
講演概要：
Singer-Cucuringu(2010)はグラフの剛性の解析手法に着想を得て(一般的な)低ランク半正定値行列の補完の一意性を判定する発見的アルゴリズムを提案している。Singer-Cucuringuのアプローチをもとに、本発表では半正定値行列補完とグラフの剛性のより詳細な類似性と決定的な相違点を明らかにし、補完が一意となるための十分条件を導く。 本研究は、Bill Jackson氏とTibor Jordan氏との共同研究である。

講演者２： 神山 直之 （九州大学）
講演題目： マトロイド制約付き最適選好マッチング問題
講演概要：
本発表では，Abraham, Irving, Kavitha, Mehlhorn (2007) によって提案された最適選好マッチング問題のマトロイドを 用いた一般化を扱う．まず，このマトロイドを用いた拡張に 対する解の存在性の特徴付けを導入し，その後この特徴付け を用いて与えられた問題例に解が存在するかを，多項式時間 で判定することができることを示す．さらに，解が存在しな い問題例に対して最小の参加者を消去することにより解が存 在するように問題例を変形する問題も上記の特徴付けを用い ることにより多項式時間で解くことができることを示す．後 半の問題はWu, Lin, Wang, Chao (2013) によって提案され た最適選好簡約問題の一般化となっている．


第10回 研究会（SODA2014報告会）

日　時：2014年 2/10 (月) 9:40 〜 18:00
会　場：東京工業大学キャンパス・イノベーションセンター 2階 多目的ルーム

9:40-10:40：大舘 陽太 (JAIST)
担当論文：Large induced subgraphs via triangulations and CMSO
F. Fomin, I. Todinca, Y. Villanger

11:00-12:00：安藤 映 (崇城大学)
担当論文：Smoothed Analysis of Local Search for the Maximum-Cut Problem
M. Etscheid, H. Roglin

13:00-14:00：小長谷 松雄 (JAIST)
担当論文：Selection and Sorting in the "Restore" Model
T. M. Chan, J. I. Munro, V. Raman

14:20-15:20：澄田 範奈 (東京大学)
担当論文：Dantzig's pivoting rule for shortest paths, deterministic MDPs, and minimum cost to time ratio cycles
T. D. Hansen, H. Kaplan, U. Zwick

15:40-16:40：木村 慧 (東京大学)
担当論文：Space complexity of list H-coloring: a dichotomy
L. Egri, P. Hell, B. Larose, A. Rafiey

17:00-18:00：桂 敬史 (東北大学)
担当論文：Bicriteria data compression
A. Farruggia, P. Ferragina, A. Frangioni, R. Venturini


第9回 研究会

日　時：2014年 1/28（火） 15:00 〜 18:00
会　場：京都大学 数理解析研究所 204教室

講演者１： Jakub Gajarsky （Masryk University）
講演題目： Faster Deciding MSO Properties of Trees of Fixed Height, and Some Consequences
講演概要：
We prove, in the universe of trees of bounded height, that for any MSO formula with m variables there exists a set of kernels such that the size of each of these kernels can be bounded by an elementary function of m. This yields a faster MSO model checking algorithm for trees of bounded height than the one for general trees. From that we obtain, by means of interpretation, corresponding results for the classes of graphs of bounded tree-depth (MSO2) and shrub-depth (MSO1), and thus we give wide generalizations of Lampis’ (ESA 2010) and Ganian’s (IPEC 2011) results. In the second part of the paper we use this kernel structure to show that FO has the same expressive power as MSO1 on the graph classes of bounded shrub-depth. This makes bounded shrub-depth a good candidate for characterization of the hereditary classes of graphs on which FO and MSO1 coincide, a problem recently posed by Elberfeld, Grohe, and Tantau (LICS 2012).

講演者２： Sebastian Ordyniak （Masryk University）
講演題目： A Complete Parameterized Complexity Analysis of Bounded Planning
講演概要：
The propositional planning problem is a notoriously difficult computational problem, which remains hard even under strong syntactical and structural restrictions. Given its difficulty it becomes natural to study planning in the context of parameterized complexity. In this work we continue the work initiated by Downey, Fellows and Stege on the parameterized complexity of planning with respect to the parameter ``length of the solution plan.'' We provide a complete classification of the parameterized complexity of the planning problem under two of the most prominent syntactical restrictions, i.e., the so called PUBS restrictions introduced by Baeckstroem and Nebel and restrictions on the number of preconditions and effects as introduced by Bylander. We also determine which of the considered fixed-parameter tractable problems admit a polynomial kernel and which don't.


第8回 研究会（FOCS2013報告会）

日　時：2013年 12/23 (月), 24（火）
会　場：東京大学 本郷キャンパス 工学部 6号館 3階 セミナー室A･D

12月23日
13:00−14:10 山内 由紀子　(九州大学)
担当論文：Tight Bounds for Set Disjointness in the Message Passing Model
M. Braverman, F. Ellen, R. Oshman, T. Pitassi and V. Vaikuntanathan

14:30−15:40 森 立平　（東京工業大学）
担当論文： Approximate Constraint Satisfaction Requires Large LP Relaxations
S.O. Chan, J.R. Lee, P. Raghavendra and D. Steurer

16:00−17:10 斎藤 惇　（群馬大学）
担当論文： A Satisfiability Algorithm for Sparse Depth Two Threshold Circuits
R. Impagliazzo, R. Paturi, and S. Schneider

12月24日
10:30-11:40 長尾 篤樹　（京都大学）
担当論文： Average Case Lower Bounds for Monotone Switching Networks
Y. Filmus, T. Pitassi, R. Robere and S.A. Cook

13:00-14:10 河瀬 康志　（東京大学）
担当論文： The Price of Stability for Undirected Broadcast Network Design with Fair Cost Allocation is Constant
V. Bilò, M. Flammini and L. Moscardelli

14:30-15:40 山口 裕生　（東京工業大学）
担当論文： Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees
A. Marcus, D.A. Spielman and N. Srivastava

16:00-17:10 中川 航太郎　（東京工業大学）
担当論文：Towards a Better Approximation for Sparsest Cut?
S. Arora, R. Ge and A.K. Sinop

なお，担当論文は変更する可能性があります．


 第7回 研究会

日　時：2013年 11/9(土) 14:00 〜
会　場：東京大学 本郷キャンパス 工学部 6号館 3階 セミナー室A･D

講演者１： 岩田 陽一 （東京大学）
講演題目： 劣モジュラ緩和による(線形時間)FPTアルゴリズム
講演概要：
カット関数など，劣モジュラ性を有する関数は効率的に多項式時間で最小化が可能であることが知られている． 本講演では，様々なNP困難について，隠れた劣モジュラ性を活用することでFPTアルゴリズムを構築できることについて論ずる． 劣モジュラ緩和と名付けるこの手法により，近年示された頂点被覆問題・Multiway Cut問題に対する分枝限定法に基づくFPTアルゴリズムの一般化に成功し，さらにはUnique Label Coverなど様々な問題に対してその適応範囲を広げることができる． また，一部の問題については，緩和問題をネットワークフローを用いて解くことにより，線形時間にすることができる．

講演者２： 宮代 隆平 （東京農工大学）
講演題目： 混合整数二次錐計画法を用いた回帰式の変数選択
講演概要：
統計や機械学習では，変数選択/特徴選択が重要な課題として知られている． 変数選択の際の評価指標としては， AIC，BIC を始めとする多数のものがこれまでに提案されている． AIC値（あるいは同種の指標）の最小化問題は， 選択される説明変数の個数を定数として与えれば 混合整数二次計画問題として定式化できることは知られていたが， 最適な説明変数の個数は事前にはわからないという問題点があった． 本研究では，選択される説明変数の個数が未知の場合のAIC値最小化問題が， 混合整数二次錐計画問題として定式化できることを示す． また，AICの他にもBIC/MDL，adjusted R^2，HQ 等， 多数の指標が同様に定式化できることを述べる．


第6回 研究会

日　時：2013年 8/26(月) 15:00 〜 17:00
会　場：東京大学 本郷キャンパス 工学部 14号館 5階 534号室

講演者１： Kristóf Bérczi （Eötvös Loránd University）
講演題目： Triangle-free subgraphs
講演概要： PDFファイル参照


講演者２： Tamás Király （Eötvös Loránd University）
講演題目： Generalized polymatroids, total dual laminarity, and truncation-paramodularity
講演概要：
Generalized polymatroids are a family of polyhedra with several useful properties and applications. One property used widely in the literature is the existence of laminar dual solutions. We make this notion of "total dual laminarity" explicit and examine whether it characterizes g-polymatroids. We also introduce the related notion of truncation-paramodularity and an application to supermodular colouring. Finally, we consider the computational complexity of deciding whether a system of linear inequalities is truncation-paramodular / total dual laminar / defines an (integer) g-polymatroid. Joint work with András Frank, Júlia Pap, and David Pritchard.


第5回 研究会

日　時：2013年 5/11(土) 14:00 〜
会　場：東京大学 本郷キャンパス 工学部 6号館 3階 セミナー室A･D

講演者１： 伊藤 健洋 （東北大学）
講演題目： 一意被覆問題に対する近似アルゴリズム
講演概要：
本発表では，平面上に点集合とオブジェクトの集合が与えられたとき，そのオブジェ クトの部分集合を選び，できる限り多くの点がその中のただ一つのオブジェクトで覆 われるようにする問題を扱う．このような幾何問題は，Erlebachとvan Leeuwenに よって2008年に導入された．与えられるオブジェクト集合が，軸平行な単位正方形の 集合，または単位円の集合であっても，この問題は強NP困難であることが知られてお り，我々は近似の観点から研究を進めた．軸平行な単位正方形で一意被覆する場合， 既存研究における最良の近似比はvan Leeuwen (2009) による2であったが，本発表で は多項式時間近似スキーム(PTAS)を与える．一方，単位円で一意被覆する場合，既存 研究における最良の近似比はErlebachとvan Leeuwen (2008) による18であったが， 本発表ではこれを4.31に改良する．

講演者２： 来嶋 秀治 （九州大学）
講演題目： 確率と計算
講演概要：
高度に発達した近年の計算環境において、 「乱数」は様々な局面で陰に陽に用いられる。 本講演では、「乱択アルゴリズムにおいて、 乱数に真に求める性質は何か？」をテーマに、 アルゴリズム設計の視点から、講演者の成果を紹介する。


第4回 研究会

日　時：2013年 2/2(土) 14:00 〜
会　場：東京大学 本郷キャンパス 工学部 6号館 3階 セミナー室A･D

講演者１： 小関 健太 （国立情報学研究所・JST, ERATO, 河原林巨大グラフプロジェクト）
講演題目： 閉曲面上のグラフのハミルトン性
講演概要：
与えられたグラフの全ての頂点を通る閉路をハミルトン閉路という．巡回セールスマン問題や4色定理との関わりから，現在まで 「閉曲面上に辺の交差なく埋め込まれたグラフ」 のハミルトン性に関しての研究が盛んに行われてきたが，いまだいくつかの未解決問題が存在している．講演者らは，未解決問題のうちの一つであった「射影平面上の任意の 4-連結グラフはハミルトン連結である」 という予想の肯定的な解決を与えたが，本発表ではその結果で用いられている手法を中心に，上記の話題に対しての最近の研究を紹介する．なお，本研究は 河原林健一教授（国立情報学研究所） との共同研究である．

講演者２： 武田 朗子 （慶応義塾大学）
講演題目： 数理最適化の視点から機械学習の分野へ　〜ロバスト最適化法と金融リスク尺度最小化の応用〜
講演概要：
機械学習の分野では，データからモデルを学習する際に，しばしば数理最適化問題として定式化され，最適化手法を用いて解かれている．本発表では，私の研究成果を例に挙げ，数理最適化の視点からどのように機械学習の分野へ貢献することができるかを紹介したい．まず、二値分類問題に対する既存の学習モデルをいくつか紹介し，それらの学習モデルがロバスト最適化法により統一的に定式化できることを話したい．さらに，既存モデルが金融リスク尺度の最小化モデルとして解釈できることを示し，新たな学習モデルの提案へと繋げたい．


第3回 研究会

日　時：2012年 12/15(土) 14:00 〜
会　場：東京大学 本郷キャンパス 工学部 6号館 3階 セミナー室A･D

講演者１： 山下 真 （東京工業大学）
講演題目： 半正定値計画問題に対する行列補完理論の高速実装
講演概要：
行列のいくつかの成分に値が決まっているとき、その他の成分に適切な値を 設定することで行列全体を半正定値行列にすることを行列補完という。 半正定値計画問題において、半正定値条件を課す変数行列は一般に密行列となるが、 入力行列が構造的な疎性を持つときには行列補完を用いることで少数の成分のみを 保持するだけで主双対内点法を実行できる。この性質をソフトウェアに実装したのが SDPA-C (SemiDeifinite Programming Algorithm with Completion method) である。 本発表では、行列分解に関する計算過程を改良することで、より高速に Schur complement 行列を計算できることを紹介する。また、マルチスレッド化などを 通して、SDPA-Cの計算時間が短縮されたことを数値実験結果により示す。

講演者２： 永野 清仁 （東京大学）
講演題目： 機械学習分野における離散凸最適化手法の応用研究
講演概要：
機械学習は与えられたデータの解析を通じ有用な規則や判断基準などの抽出を目的とする学問領域であるが、 近年では問題の離散構造を利用したアルゴリズム設計が注目され始めている。 特に現在の機械学習分野における離散最適化において、劣モジュラ関数は中心的な概念であると認識されている。 本発表では、離散版の凸最適化とでもいうべき劣モジュラ最適化手法の機械学習分野への応用に関する近年の研究について、 我々のグループの結果を含め解説する。


第2回 研究会

日　時：2012年 10/13(土) 14:00 〜
会　場：東京大学 本郷キャンパス 工学部 6号館 2階 63 講義室

講演者１： 高澤 兼二郎 （京都大学）
講演題目： 離散凸構造を持つ組合せ最適化問題
講演概要：
多項式時間可解である組合せ最適化問題の多くはマトロイド構造， あるいはそれを一般化する離散凸構造を持っている． 本発表では，マッチング森問題および双有向森問題が持つ離散凸構造について紹介する． マッチング森は，1982 年に Giles によって提唱されたマッチングと有向森の共通の一般化である． また，双有向森は，1982 年に Schrijver によって提唱された有向森と二部グラフの枝被覆の 共通の一般化である．各々に対して，完全双対整数性を持つ多面体的表現や重み付きの問題に対する 組合せ的アルゴリズムが知られている． 本発表では，マッチング森がデルタマトロイド構造を持つことおよび， 最短双有向森問題が付値マトロイド交叉問題の枠組に入ることを紹介する． また，これらの事実のアルゴリズム設計への適用について論じる．

講演者２： 岩田 覚 （京都大学）
講演題目： 重み付き線形マトロイド・パリティ
講演概要：
マッチングとマトロイドの共通の一般化として，導入された マトロイド・パリティ問題は，独立性判定オラクルを仮定する 通常の枠組みでは，多項式時間解法が存在し得ないことが 知られている．しかし，Lovasz (1980) は，マトロイドが 行列で表現されているときには，多項式時間解法が存在する ことを示した．その後，この線形マトロイド・パリティ問題に 対して，より効率的な解法も提案されている． 本講演では，線形マトロイド・パリティの枠組みにおいて， 重み付きの最適化問題に対する強多項式時間解法を与える． このアルゴリズムは，歪対称多項式行列の Pfaffian を用いた 定式化と Gabow-Stallmann (1986)による増加道アルゴリズムを 基にしている． なお，講演者の研究とは独立に，Gyula Pap も同じ問題に対して， 別の強多項式時間解法を得ている．


第1回 研究会

日　時：2012年 5/26(土) 14:00 〜
会　場：東京大学 本郷キャンパス 工学部 6号館 3階 セミナー室A･D

講演者１： 後藤 順哉 （中央大学）
講演題目： CVaR最小化のためのロバスト最適化モデルとコヒレント尺度への拡張
講演概要：
CVaRに代表されるコヒレントなリスク尺度は、90年代終盤に金融工学の文脈で提示され 支持を得てきた。しかしながら、損失分布の裾部分への寄与の大きさから、大規模なポー トフォリオ選択などの文脈で適用する場合、その推定誤差が大きいことが指摘されている。 本発表ではまずその対策としてロバスト最適化モデルを考え、正則化付きCVaR最小化モデル との関連について述べる。後半ではKonno,Waki,Yuuki(2002)のファクターモデルに基づいた CVaR最小化とその問題点を概観し、それに対するロバスト化について検討する。

講演者２： 松井 知己 （中央大学）
講演題目： 多数回停止可能な最適停止問題における勝利確率の下界について
講演概要：
本発表では，古典的秘書問題を特殊ケースとして含む Bruss の Odds Problem について議論する. Odds Problem では，0/1確率変数列を逐次観測し，各変数を観測後に観測を停止するか，観測を継続するかを決定する．停止した確率変数が, 1となる最後の確率変数である確率を最大にする規則を最適停止規則と呼び，その際の確率を勝利確率と呼ぶ．Odds Problem の勝利確率は 1/e 以上であることが，2003年に Bruss によって示されている． Odds Problem において，多数回停止を可能とした問題については,停止回数2回の場合の勝利確率がe^{-1}+e^{-3/2}以上であることが, 2010年に Ano, Kakinuma and Miyoshi によって示されている. 本研究では，一般の停止回数に対して，勝利確率の下限を与える．これらの下限は多数回停止可能な古典的秘書問題の勝利確率の下限でもあるという美しい構造を持つことが発見される。 本研究は, 穴太克則氏（芝浦工業大学）との共同研究である.


「最適化の理論と応用」研究部会トップページへ戻る

「最適化の理論と応用」研究部会
　
主査： 牧野　和久 （京都大学）
幹事： 小林　佑輔 （東京大学）