経営工学系ワーキングペーパー 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.

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

• 広報誌
• 経営工学系ワーキングペーパー 2017-6