Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with nonapproximability:
TR98-001 | 17th December 1997
Detlef Sieling

On the Existence of Polynomial Time Approximation Schemes for OBDD Minimization

Revisions: 1

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 ... more >>>

TR99-001 | 4th January 1999
Detlef Sieling

The Complexity of Minimizing FBDDs

Revisions: 1

Free Binary Decision Diagrams (FBDDs) are a data structure
for the representation and manipulation of Boolean functions.
Efficient algorithms for most of the important operations are known if
only FBDDs respecting a fixed graph ordering are considered. However,
the size of such an FBDD may strongly depend on the chosen ... more >>>

TR02-054 | 5th September 2002
Detlef Sieling

Minimization of Decision Trees is Hard to Approximate

Decision trees are representations of discrete functions with widespread applications in, e.g., complexity theory and data mining and exploration. In these areas it is important to obtain decision trees of small size. The minimization problem for decision trees is known to be NP-hard. In this paper the problem is shown ... more >>>

TR04-117 | 1st December 2004
Michael Alekhnovich, Sanjeev Arora, Iannis Tourlakis

Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy

Lovasz and Schrijver described a generic method of tightening the LP and SDP relaxation for any 0-1 optimization problem. These tightened relaxations were the basis of several celebrated approximation algorithms (such as for MAX-CUT, MAX-3SAT, and SPARSEST CUT).

We prove strong nonapproximability results in this model for well-known problems such ... more >>>

ISSN 1433-8092 | Imprint