On solving covering problems
Olivier Coudert · 1996
The set covering problem and the minimum cost assignment problem (respectively known as unate and binate covering problem) arise throughout the logic synthesis ow.This paper investigates the complexity and approximation ratio of two l o w er bound computation algorithms from both a theoretical and practical point o f view.It also presents a new pruning technique that takes advantage of the partitioning.