Lehrstuhl Mathematik & InformatikContinuous Reductions Among Combinatorial Optimization Problems
Abstract. Many reductions among combinatorial problems
are known in the context of NP-completeness. These reductions preserve
the optimality of solutions. However, they may change the "relative
error" of approximative solutions dramatically. In this paper, we
apply a new type of reductions, called continuous reductions. When one
problem is continuously reduced to another, any approximation
algorithm for the latter problem can be transformed into an
approximation algorithm for the former. Moreover, the performance
ratio is preserved up to a constant factor. We relate the problem
"Minimum Number of Inverters in CMOS-Circuits", which arises in the
context of logic synthesis, to several "classical" combinatorial
problems such as "Maximum Independent Set" and "Deletion of a Minimum
Number of Vertices (Edges) in Order to Obtain a Bipartite (Partial) Subgraph".