日 時:11 月 27 日(金) 13:00〜14:30 出席者: 29 人 場 所:京都大学 工学部 8 号館 2 階 共同 2 講義室 テーマと講師: 「The Power of SDP Relaxations - Computing Strong Bounds for QAPs and Graph Problems」 Hans D. Mittelmann (Arizona State University) [概要]: 本講演では,二次配置問題(QAP)と接吻数(kissing number)問題に半正定値計 画(SDP)緩和を適用することにより,既存の結果よりも近似度の高い結果が得 られることが示された.また,発表者がウェブで公開しているベンチマーク集 が紹介され,具体的な問題例,アルゴリズムの利用法などの説明も行われた.