第９回研究会（２００７年１２月１５日（土）　１４時 〜）講演概要

会場：　上智大学　四谷キャンパス １１号館４階　１１−４１９

講演者： 森口　聡子　氏　（上智大学）
タイトル： 離散凸関数最小化における連続緩和と近接定理
概要： 整数格子点上で定義された関数のクラスで，離散 凸解析の理論において中心的な役割を担っている離散 Ｌ/Ｍ凸関数の最小化を扱う． 離散Ｌ/Ｍ凸関数それぞれの最小化問題に対して，理論的に効率の良い多項式時間アルゴ リズムが既に提案されているが，本発表では， 実装上高速に最小解を求めることを動機とし， 離散Ｌ/Ｍ凸関数に対する連続緩和を用いた最小 化法を報告する．さらに，連続緩和を用いた最小化法の有効性を 理論的に保証する， 連続緩和解と離散最小解の近接性に関する定理を示す． 数値実験の結果についても報告する． この研究は，東京大学の土村展之氏との共同研究である．

講演者： 池辺　淑子　氏　（東京理科大学）
タイトル： 複数の会場をもつスポーツスケジュールの構成的存在証明
概要： 本発表では 2n チームおよび（いずれのチームの本拠地で もない）n 会場 が与えられた下で、以下の4件を満たすスケジュールを作成 する問題を考える：
(1) すべてのチームペアは1回以上対戦する、
(2) 各試合日においてn試合同時に開催する、
(3) 各チームは各会場を2回ずつ使用する、
(4) 同じ会場で2回対戦するチームペアはない。
2nが2の冪乗に等しいときおよび n が 30 と 互いに素なときは それぞれ、de Werra, Ekim and Raess および Horton による構成的 存在証明が与えられている（2n=4、6のときはスケ ジュールは 存在しない）。本発表では n が2の冪乗でないよう な任意の 5 以上 の整数の場合に条件を満たすスケジュールが存在することを構成的に 証明する。証明はいくつかのケースに分かれ、（通常の）総当り戦を 構成するKirkmann 法や素数の原始根などを用いる。

ホーム

Copyright, S@CO All rights reserved, 2006-2007.