ECCC-Report TR98-001https://eccc.weizmann.ac.il/report/1998/001Comments and Revisions published for TR98-001en-usMon, 19 Jan 1998 00:00:00 +0200
Revision 1
| The Nonapproximability of OBDD Minimization Revision of: TR98-001 |
Detlef Sieling
https://eccc.weizmann.ac.il/report/1998/001#revision1The 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 for each
constant c>1 there is no polynomial time approximation algorithm
with the performance ratio c for the variable ordering problem
unless P=NP. This result justifies, also from a theoretical point
of view, to use heuristics for the variable ordering problem.
Mon, 19 Jan 1998 00:00:00 +0200https://eccc.weizmann.ac.il/report/1998/001#revision1
Paper TR98-001
| On the Existence of Polynomial Time Approximation Schemes for OBDD Minimization |
Detlef Sieling
https://eccc.weizmann.ac.il/report/1998/001The 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.
Tue, 06 Jan 1998 18:39:44 +0200https://eccc.weizmann.ac.il/report/1998/001