期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1998
卷号：1998
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：The size of Ordered Binary Decision Diagrams (OBDDs) is
determined by the chosen variable ordering. A poor choice may cause an
OBDD to be too large to fit into the available memory. The decision
variant of the variable ordering problem is known to be
NP-complete. We strengthen this result by showing that there in no
polynomial time approximation scheme for the variable ordering problem
unless P=NP. We also prove a small lower bound on the performance
ratio of a polynomial time approximation algorithm under the
assumption P\neq NP.
关键词：nonapproximability, Ordered Binary Decision Diagrams, variable ordering problem for OBDDs
