Approximability of minimum AND-circuits

Jan Arpe; Bodo Manthey

doi:10.1007/11785293_28

Approximability of minimum AND-circuits

Jan Arpe^*
, Bodo Manthey

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

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.

Original language	English
Title of host publication	Algorithm Theory – SWAT 2006
Subtitle of host publication	10th Scandinavian Workshop on Algorithm Theory, Riga, Latvia, July 6-8, 2006: Proceedings
Editors	Lars Arge, Rusins Freivalds
Publisher	Springer
Pages	292-303
Number of pages	12
ISBN (Electronic)	978-3-540-35755-1
ISBN (Print)	978-3-540-35753-7
DOIs	https://doi.org/10.1007/11785293_28
Publication status	Published - 1 Jan 2006
Externally published	Yes
Event	10th Scandinavian Workshop on Algorithm Theory, SWAT 2006 - Riga, Latvia Duration: 6 Jul 2006 → 8 Jul 2006 Conference number: 10

Publication series

Name	Lecture Notes in Computer Science
Volume	4059
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	10th Scandinavian Workshop on Algorithm Theory, SWAT 2006
Abbreviated title	SWAT 2006
Country/Territory	Latvia
City	Riga
Period	6/07/06 → 8/07/06

Keywords

Approximation ratio
Vertex cover
Input instance
Addition chain
Input gate

Access to Document

10.1007/11785293_28

Approximability of Minimum AND-Circuits
Arpe, J. & Manthey, B., Mar 2009, In: Algorithmica. 53, 3, p. 337-357 21 p.
Research output: Contribution to journal › Article › Academic › peer-review
2 Link opens in a new tab Citations (Scopus)

5 Downloads (Pure)

Cite this

@inproceedings{53b2a9b0b98c45dfa1962de4dc104a1c,

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 reveal connections between the MINIMUM AND-CIRCUIT problem and several problems from different areas.",

keywords = "Approximation ratio, Vertex cover, Input instance, Addition chain, Input gate",

author = "Jan Arpe and Bodo Manthey",

year = "2006",

month = jan,

day = "1",

doi = "10.1007/11785293\_28",

language = "English",

isbn = "978-3-540-35753-7",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "292--303",

editor = "Lars Arge and Rusins Freivalds",

booktitle = "Algorithm Theory – SWAT 2006",

address = "Germany",

note = "10th Scandinavian Workshop on Algorithm Theory, SWAT 2006, SWAT 2006 ; Conference date: 06-07-2006 Through 08-07-2006",

}

Arpe, J & Manthey, B 2006, Approximability of minimum AND-circuits. in L Arge & R Freivalds (eds), Algorithm Theory – SWAT 2006: 10th Scandinavian Workshop on Algorithm Theory, Riga, Latvia, July 6-8, 2006: Proceedings. Lecture Notes in Computer Science, vol. 4059, Springer, pp. 292-303, 10th Scandinavian Workshop on Algorithm Theory, SWAT 2006, Riga, Latvia, 6/07/06. https://doi.org/10.1007/11785293_28

Approximability of minimum AND-circuits. / Arpe, Jan; Manthey, Bodo.
Algorithm Theory – SWAT 2006: 10th Scandinavian Workshop on Algorithm Theory, Riga, Latvia, July 6-8, 2006: Proceedings. ed. / Lars Arge; Rusins Freivalds. Springer, 2006. p. 292-303 (Lecture Notes in Computer Science; Vol. 4059).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Approximability of minimum AND-circuits

AU - Arpe, Jan

AU - Manthey, Bodo

N1 - Conference code: 10

PY - 2006/1/1

Y1 - 2006/1/1

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 reveal connections between the MINIMUM AND-CIRCUIT problem and several problems from different areas.

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 reveal connections between the MINIMUM AND-CIRCUIT problem and several problems from different areas.

KW - Approximation ratio

KW - Vertex cover

KW - Input instance

KW - Addition chain

KW - Input gate

U2 - 10.1007/11785293_28

DO - 10.1007/11785293_28

M3 - Conference contribution

AN - SCOPUS:33746457870

SN - 978-3-540-35753-7

T3 - Lecture Notes in Computer Science

SP - 292

EP - 303

BT - Algorithm Theory – SWAT 2006

A2 - Arge, Lars

A2 - Freivalds, Rusins

PB - Springer

T2 - 10th Scandinavian Workshop on Algorithm Theory, SWAT 2006

Y2 - 6 July 2006 through 8 July 2006

ER -

Approximability of minimum AND-circuits

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Research output

Approximability of Minimum AND-Circuits

Cite this