Arpe, Jan ;
Manthey, Bodo
Approximability of Minimum ANDCircuits
Abstract
Given a set of monomials, the {sc Minimum ANDCircuit} problem asks for a circuit that computes these monomials using ANDgates of fanin two and being of minimum size.
We prove that the problem is not polynomial time approximable within a factor of less than $1.0051$ unless $mathsf{P} = mathsf{NP}$, even if the monomials are restricted to be of degree at most three. For the latter case, we devise several efficient approximation algorithms, yielding an approximation ratio of $1.278$. For the general problem, we achieve an approximation ratio of $d3/2$, where $d$ is the degree of the largest monomial.
In addition, we prove that the problem is fixed parameter tractable with the number of monomials as parameter. Finally, we reveal connections between the {sc Minimum ANDCircuit} problem and several problems from different areas.
BibTeX  Entry
@InProceedings{arpe_et_al:DSP:2006:603,
author = {Jan Arpe and Bodo Manthey},
title = {Approximability of Minimum ANDCircuits},
booktitle = {Complexity of Boolean Functions},
year = {2006},
editor = {Matthias Krause and Pavel Pudl{\'a}k and R{\"u}diger Reischuk and Dieter van Melkebeek},
number = {06111},
series = {Dagstuhl Seminar Proceedings},
ISSN = {18624405},
publisher = {Internationales Begegnungs und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2006/603},
annote = {Keywords: Optimization problems, approximability, automated circuit design}
}
Keywords: 

Optimization problems, approximability, automated circuit design 
Seminar: 

06111  Complexity of Boolean Functions

Issue date: 

2006 
Date of publication: 

09.10.2006 