グラフ・ネットワークにおける理論と最適化グループセミナー
日時
2012年11月28日（水）11:00 – 12:00
場所
東京大学本郷キャンパス 理学部7号館007教室
講演者
福永拓郎 先生（京都大学）
タイトル
Iterative rounding approximation algorithms for degree-bounded node-connectivity network design
アブストラクト
We consider the problem of finding a minimum edge cost subgraph of an undirected or a directed graph satisfying given connectivity requirements and degree bounds b(v) on nodes v. In this talk, we mainly discuss the problem with element- and node-connectivity requirements, for which no efficient approximation algorithm was known. We present an iterative rounding algorithm of the set-pair LP relaxation for this problem, and show that it achieves good approximation factors. This is a joint work with R. Ravi (Carnegie Mellon University) and Zeev Nutov (Open University of Israel).
