Approximability of Minimum AND-Circuits

Jan Arpe, Bodo Manthey

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)

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 discuss generalizations of the MINIMUM AND-CIRCUIT problem and relations to addition chains and grammar-based compression.
Original languageEnglish
Pages (from-to)337-357
Number of pages21
JournalAlgorithmica
Volume53
Issue number3
DOIs
Publication statusPublished - Mar 2009

Fingerprint

Dive into the research topics of 'Approximability of Minimum AND-Circuits'. Together they form a unique fingerprint.

Cite this