On solving covering problems
- 1 January 1996
- proceedings article
- Published by Association for Computing Machinery (ACM)
- p. 197-202
- https://doi.org/10.1145/240518.240555
Abstract
The set covering problem and the minimum cost assignmentproblem (respectively known as unate and binatecovering problem) arise throughout the logic synthesisflow. This paper investigates the complexity andapproximation ratio of two lower bound computation algorithmsfrom both a theoretical and practical point ofview. It also presents a new pruning technique that takesadvantage of the partitioning.1 IntroductionThe (unate or binate) covering problem is a well knownintractable problem. ...Keywords
This publication has 0 references indexed in Scilit: