日本オペレーションズ・リサーチ学会「離散アルゴリズムの応用と理論」研究部会
Seminar on Discrete Algorithms: Applications and Theory


2016年3月より, 日本オペレーションズ・リサーチ学会「離散アルゴリズムの応用と理論」研究部会(Seminar on Discrete Algorithms: Applications and Theory)が発足しました.
研究部会の紹介はこちらをご覧下さい.
第9回研究会(ワークショップ 離散構造とアルゴリズム)のお知らせ
2017年度第4回(通算第9回)研究会を2018年1月26日(金)に行います. 離散最適化およびアルゴリズム分野において第一線でご活躍される先生方の講演会となっております. 多くの方のご参加をお待ちしております.
また研究会終了後に,藤重悟先生(京都大学)の古希をお祝いするとともに, 離散最適化の未来など語らうパーティーを開催します. 予約の都合のため,参加される方は 1月8日(月)までにこちらのフォームより参加登録をお願いします.
  • 日時: 2018年1月26日(金) 10:00 〜 17:45
  • 会場: 京大時計台の国際交流ホールI (会場への行き方はこちら・マップ3番)
  • プログラム:
    10:00-10:05 開会の辞
    10:05-10:45 岩田覚(東京大学)「重み付き線形マトロイド・パリティ」

    効率的な厳密解法が設計できる組合せ最適化問題として,マッチングとマトロイド交叉が知られている.両者の共通の一般化として導入されたマトロイド・パリティ問題は,一般のマトロイド上で指数時間を必要とする.これに対し,Lovasz (1980) は,行列表現が与えられた線形マトロイド上での最大最小定理を証明し,多項式時間解法を設計した.
     本講演では,小林佑輔(筑波大学)との共同研究に基いて,重み付き線形マトロイド・パリティ問題に対する多項式時間解法を紹介する.

    10:45-11:00 休憩
    11:00-11:25 根本俊男(文教大学)「参議院選挙合区に対する数理的考察」

    参議院議員通常選挙の選挙区において合区(鳥取と島根,高知と徳島で1選挙区)が始まった.一票の較差是正に対し各都道府県への議席数配分変更による従来のアプローチに加えて区割変更のアプローチも採用したといえる.この合区は都道府県の組合せによる格差是正への取り組みであり最適化モデルの構造が現れる.ここでは合区と一票の較差をめぐる議論に対し最適化モデルの観点からの知見を提供する.
     なお,本講演は堀田敬介(文教大学),和田淳一郎(横浜市立大学)と取り組んでいる共同研究の一部である.

    11:25-11:55 安藤和敏(静岡大学)「subdominant 閉路完全距離の特徴付けとそれに対する効率的なアルゴリズム」

    系統学における重要な問題は,生物種間の相違を表す相違写像が与えられたときに,これらの生物種の進化の歴史を忠実に表現する系統樹を推定することである.系統樹のモデルとして最も基本的なものは超距離木であり,超距離木に対応する相違写像は超距離と呼ばれる.最近,Trudeau(2012) は最小費用全域木ゲームの文脈において閉路完全距離という概念を導入した.閉路完全距離は超距離の自然な一般化であり超距離に対して成り立つsubdominant の存在のような良い性質を保存している.本研究では,subdominant閉路完全距離の特徴付けを与え,それに基づいて任意の相違写像に対する subdominant閉路完全距離を求める効率的なアルゴリズムを与える.さらに,このアルゴリズムから最小費用全域木ゲームの閉路完全解に対する同じ計算量を持つアルゴリズムを導く.

    11:55-13:40 お昼休み
    13:40-14:20 室田一雄(首都大学東京)「整凸関数の離散凸解析における役割」

    1990年にFavatiとTardellaによって提示された整凸関数の概念は.離散凸解析における関数クラスの基本的な枠組みとなっている.本講演では,その定義と特徴づけの精密化,近接定理,射影演算などの最近の研究結果も含めて,整凸関数の性質を概観し,整凸関数の意義について議論する.

    14:20-14:50 田村明久(慶應義塾大学)「離散凸解析を用いたマッチングモデルの展開」

    2003年の藤重先生との共同研究から派生した研究成果について振り返る.2003年の理論研究から始まった離散凸解析を用いたマッチングモデルの研究について,その後の理論的な展開,応用への可能性の示唆,実務問題への展開について紹介する.

    14:50-15:10 休憩
    15:10-15:40 平井広志(東京大学)「CAT(0)空間上のアルゴリズムと最適化について」

    CAT(0)空間と呼ばれるユークリッド空間や双曲空間を一般化した距離空間がある.CAT(0)とは,「曲率が非正」ということを意味している.この空間は,ユークリッド空間で成り立つ様々な良い性質を引き継いでいる.特に,任意の2点を結ぶ測地線( = 最短路)が一意に定まる.このことから凸関数なども自然に定義される.最近になって,CAT(0)空間を利用したモデリングやその上でのアルゴリズム・最適化理論が展開され始めている.本発表では,そのような試みの一端を紹介する.

    15:40-16:10 谷川眞一(東京大学)「周期グラフの大域剛性」

    ある結晶構造と同じ組成をもち幾何形状が異なる物質が存在するかを判定したい.幾何的制約条件のみを抜き出し問題を数理モデル化すると,この問題は空間内に埋め込まれた周期的無限グラフが辺長を変えずに異なる形状へ変形可能であるかを判定する問題として捉えることができる.一定の仮定のもと,この問題が劣モジュラ関数最小化の繰り返しで解けることを示す.
     本研究はViktoria Kaszanitzky氏とBernd Schulze氏との共同研究である.

    16:10-16:30 牧野和久(京都大学)「正モジュラ関数の最適化」

    正モジュラ関数は,様々な組合せ最適化問題に関連して現れ,効率的なアルゴリズム設計の鍵となる重要かつ中心的な構造的性質の一つである.本講演では,正モジュラ関数最小化問題,最大化問題の計算量がともに指数時間であることを示す.
    本研究はMagnus Halldorsson氏,石井利昌氏,高澤兼二郎氏との共同研究である.

    16:30-16:50 休憩
    16:50-17:40 藤重悟(京都大学)「最小ノルム点問題と離散最適化」

    ノルム最小化に関わる離散最適化の諸問題について,最近までの話題とこれからの展望についてお話ししたい.

    17:40-17:45 閉会の辞
  • パーティー:
    • 日時:2018年1月26日(金) 18:00 〜
    • 場所:京大時計台の国際交流ホールII
    • パーティー参加申込締切:2018年1月8日(月) 申込フォーム

第8回研究会のお知らせ
2017年度第3回(通算第8回)研究会を2017年11月10日(金)に行います. 多くの方のご参加をお待ちしております.
  • 講演者1: 藤井 浩一 氏(NTTデータ 数理システム)
    題目: 最適化ソリューションを支えるソルバー技術
  • 講演者2: 宮代 隆平 氏(東京農工大学)
    題目: 特徴選択に対する整数計画アプローチ
また,研究会終了後に懇親会を予定しております. 予約の都合のため,お手数をおかけしますが,参加を希望される方は10月31日(火)までにこちらより参加登録をお願いします.
概要はこちら
第7回研究会(RIMS 共同研究「組合せ最適化セミナー」)のお知らせ
2017年度第2回(通算第7回)研究会を7月26日(水)〜28日(金)に行います. 今回はRIMS 共同研究「組合せ最適化セミナー」との共催です. 多くの方のご参加をお待ちしております.
今回は共催のため,参加を希望される方はこちらをご覧の上,事前登録をよろしくお願いいたします.
詳細なプログラムはこちらをご覧ください.
第6回研究会のお知らせ
2017年度第1回(通算第6回)研究会を2017年4月27日(木)に行います. 多くの方のご参加をお待ちしております.
  • 講演者1: 宮本 裕一郎 氏(上智大学)
    題目: 離散最適化ヒューリスティクスに対するパラメーターチューニング手法の比較
概要はこちら
第5回研究会のお知らせ
2016年度第5回(通算第5回)研究会を2017年2月10日(金)に行います. 多くの方のご参加をお待ちしております.
  • 講演者1: 永井 秀稔 氏(新日鉄住金ソリューションズ株式会社)
    題目: 現実のスケジューリング問題における最適化適用の現状
  • 講演者2: 池上 敦子 氏(成蹊大学)
    題目: ナーススケジューリング ― 解修正のための情報づくり ―
概要はこちら
第4回研究会のお知らせ
2016年度第4回(通算第4回)研究会を2017年1月6日(金)に行います. 多くの方のご参加をお待ちしております.
  • 講演者1: Nhan Bao Ho (La Trobe University)
    題目: The Sprague-Grundy function for Star Silver Dollar game
  • 講演者2: Endre Boros (Rutgers University)
    題目: Generating maximal irredundant and minimal redundant subfamilies of a hypergraph
  • 講演者3: Vladimir Gurvich (Rutgers University)
    題目: Metric and ultrametric spaces of resistances
概要はこちら
第3回研究会のお知らせ
2016年度第3回(通算第3回)研究会を10月7日(金)に行います. 多くの方のご参加をお待ちしております.
  • 講演者1: 田島 玲 氏(Yahoo! JAPAN研究所)
    題目(第一部): ヤフーにおけるデータ利活用(1) – サービスへの貢献
    題目(第二部):ヤフーにおけるデータ利活用(2) – 先進事例
  • 講演者2: 柳浦 睦憲 氏(名古屋大学)
    題目: メタ戦略の今
概要はこちら
第2回研究会(RIMS 共同研究「組合せ最適化セミナー」)のお知らせ
2016年度第2回(通算第2回)研究会を7月27日(水)〜29日(金)に行います. 今回はRIMS 共同研究「組合せ最適化セミナー」との共催です. 多くの方のご参加をお待ちしております.
今回は共催のため,参加を希望される方はこちらをご覧の上,事前登録をよろしくお願いいたします.
詳細なプログラムはこちらをご覧ください.
第1回研究会のお知らせ
2016年度第1回(通算第1回)研究会を6月10日(金)に行います. 多くの方のご参加をお待ちしております.
  • 講演者1: 岩岡 浩一郎 氏(パナソニック システムネットワークス)
    題目: 交通信号制御におけるメタヒューリスティックスの活用
  • 講演者2: 武田 朗子 氏(統計数理研究所)
    題目: 非凸二次最適化の二値判別への応用
概要はこちら