Continuous reductions among combinatorial optimization problems
type: Item
instance of: scholarly article
title: Continuous reductions among combinatorial optimization problems
zbMATH Open document ID: 0659.68092
DOI: 10.1007/BF00289161
published in: Acta Informatica
publication date: 1989-01-01T00:00:00Z
review text: 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''.
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68W99
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 94C15
zbMATH DE Number: 4078830
zbMATH Keywords: combinatorial optimization
zbMATH Keywords: combinatorial circuits
zbMATH Keywords: logic synthesis
zbMATH Keywords: NP- completeness
zbMATH Keywords: continuous reductions
zbMATH Keywords: approximation algorithm
author: Hans Ulrich Simon
MaRDI profile type: Publication
cites work: Q3680754
cites work: Q4198056
cites work: An Efficient Heuristic Procedure for Partitioning Graphs
cites work: Q5187226
description: scientific article; zbMATH DE number 4078830