Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR06-045 | 20th May 2006 00:00

Approximability of Minimum AND-Circuits

RSS-Feed




Revision #1
Authors: Jan Arpe, Bodo Manthey
Accepted on: 20th May 2006 00:00
Downloads: 1538
Keywords: 


Abstract:

Given a set of monomials, the Minimum AND-Circuit problem asks for a circuit that computes these monomials using AND-gates of fan-in 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 P=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 d-3/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 Minimum AND-Circuit problem and several problems from different areas.


Paper:

TR06-045 | 13th March 2006 00:00

Approximability of Minimum AND-Circuits





TR06-045
Authors: Jan Arpe, Bodo Manthey
Publication: 31st March 2006 02:09
Downloads: 1479
Keywords: 


Abstract:

Given a set of monomials, the Minimum AND-Circuit problem asks for a
circuit that computes these monomials using AND-gates of fan-in 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 P = 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 d-3/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 Minimum AND-Circuit problem and
several problems from different areas.



ISSN 1433-8092 | Imprint