経営工学系 News

経営工学系ワーキングペーパー 2017-6 掲載

  • RSS

2017.08.18

経営工学系ワーキングペーパー 2017-6

経営工学系ワーキングペーパー 2017-6

経営工学系では、系の最新の研究成果の報告を掲載する「ワーキングペーパー」を発行しております。

最新号は「2017-6: Yotaro Takazawa, Shinji Mizuno, Tomonari Kitahara, An improved approximation algorithm for the covering 0-1 integer program」です。

論文タイトル
An improved approximation algorithm for the covering 0-1 integer program
著者
Yotaro Takazawa, Shinji Mizuno, Tomonari Kitahara
論文要旨
We present an improved approximation algorithm for the covering 0-1 integer program (CIP), a well-known problem as a natural generalization of the set cover problem. Our algorithm uses a primal — dual algorithm for CIP by Fujito (2004) as a subroutine and achieves an approximation ratio of (f- (f-1)/m) when m is greater than or equal to 2, where m is the number of the constraints and f is the maximum number of non-zero entries in the constraints. In addition, when m=1 our algorithm can be regarded as a PTAS. These results improve the previously known approximation ratio f.

今後も新しい号が発行され次第掲載していきます。

  • RSS

ページのトップへ

CLOSE

※ 東工大の教育に関連するWebサイトの構成です。

CLOSE