Approximability of Minimum AND-Circuits

Jan Arpe; Bodo Manthey

doi:10.1007/s00453-007-9039-0

Approximability of Minimum AND-Circuits

Jan Arpe
, Bodo Manthey

Discrete Mathematics and Mathematical Programming

Research output: Contribution to journal › Article › Academic › peer-review

2 Citations (Scopus)

5 Downloads (Pure)

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 language	English
Pages (from-to)	337-357
Number of pages	21
Journal	Algorithmica
Volume	53
Issue number	3
DOIs	https://doi.org/10.1007/s00453-007-9039-0
Publication status	Published - Mar 2009

Access to Document

10.1007/s00453-007-9039-0

Approximability of minimum AND-circuits
Arpe, J. & Manthey, B., 1 Jan 2006, Algorithm Theory – SWAT 2006: 10th Scandinavian Workshop on Algorithm Theory, Riga, Latvia, July 6-8, 2006: Proceedings. Arge, L. & Freivalds, R. (eds.). Springer, p. 292-303 12 p. (Lecture Notes in Computer Science; vol. 4059).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Cite this

@article{f7f9d5c97d864bec99671d94cb3129cd,

title = "Approximability of Minimum AND-Circuits",

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.",

author = "Jan Arpe and Bodo Manthey",

year = "2009",

month = mar,

doi = "10.1007/s00453-007-9039-0",

language = "English",

volume = "53",

pages = "337--357",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer",

number = "3",

}

TY - JOUR

T1 - Approximability of Minimum AND-Circuits

AU - Arpe, Jan

AU - Manthey, Bodo

PY - 2009/3

Y1 - 2009/3

N2 - 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.

AB - 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.

U2 - 10.1007/s00453-007-9039-0

DO - 10.1007/s00453-007-9039-0

M3 - Article

SN - 0178-4617

VL - 53

SP - 337

EP - 357

JO - Algorithmica

JF - Algorithmica

IS - 3

ER -

Approximability of Minimum AND-Circuits

Abstract

Access to Document

Fingerprint

Research output

Approximability of minimum AND-circuits

Cite this