Detlef Sieling

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

Detlef Sieling

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

Detlef Sieling

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

Michael Alekhnovich, Sanjeev Arora, Iannis Tourlakis

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