Improved approximation algorithms for minimum AND-circuits problem via k-set cover |
| |
Authors: | Hiroki Morizumi |
| |
Affiliation: | Graduate School of Informatics, Kyoto University, Yoshida-Honmachi, Sakyo-ku, Kyoto 606-8501, Japan |
| |
Abstract: | Arpe and Manthey [J. Arpe, B. Manthey, Approximability of minimum AND-circuits, Algorithmica 53 (3) (2009) 337-357] recently studied the minimum AND-circuit problem, which is a circuit minimization problem, and showed some results including approximation algorithms, APX-hardness and fixed parameter tractability of the problem. In this note, we show that algorithms via the k-set cover problem yield improved approximation ratios for the minimum AND-circuit problem with maximum degree three. In particular, we obtain an approximation ratio of 1.199 for the problem with maximum degree three and unbounded multiplicity. |
| |
Keywords: | Approximation algorithms Circuit minimization problem k-set cover |
本文献已被 ScienceDirect 等数据库收录! |
|