TY - JOUR
T1 - Maximum renamable Horn sub-CNFs
AU - Boros, Endre
N1 - Funding Information: The author is thankful for the partial support by the National Science Foundation (Grants INT 9321811 and DMS-98-06389), NATO (Grant CRG 931531) and the Office of Naval Research (Grant N0001492F1375).
PY - 1999/10/15
Y1 - 1999/10/15
N2 - The NP-hard problem of finding the largest renamable Horn sub-CNF of a given CNF is considered, and a polynomial time approximation algorithm is presented for this problem. It is shown that for cubic CNFs this algorithm has a guaranteed performance ratio of 40/67.
AB - The NP-hard problem of finding the largest renamable Horn sub-CNF of a given CNF is considered, and a polynomial time approximation algorithm is presented for this problem. It is shown that for cubic CNFs this algorithm has a guaranteed performance ratio of 40/67.
KW - Approximation algorithms
KW - Horn CNF
KW - Satisfiability
UR - http://www.scopus.com/inward/record.url?scp=0007133087&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0007133087&partnerID=8YFLogxK
U2 - https://doi.org/10.1016/S0166-218X(99)00031-1
DO - https://doi.org/10.1016/S0166-218X(99)00031-1
M3 - Article
SN - 0166-218X
VL - 96-97
SP - 29
EP - 40
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
ER -