Projekte pro Jahr
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.
Originalsprache | Englisch |
---|---|
Titel | SWAT 2006: Algorithm Theory – SWAT 2006 |
Seitenumfang | 12 |
Band | 4059 LNCS |
Herausgeber (Verlag) | Springer Verlag |
Erscheinungsdatum | 01.01.2006 |
Seiten | 292-303 |
ISBN (Print) | 978-3-540-35753-7 |
ISBN (elektronisch) | 978-3-540-35755-1 |
DOIs | |
Publikationsstatus | Veröffentlicht - 01.01.2006 |
Veranstaltung | 10th Scandinavian Workshop on Algorithm Theory - Riga, Lettland Dauer: 06.07.2006 → 08.07.2006 Konferenznummer: 67922 |
Fingerprint
Untersuchen Sie die Forschungsthemen von „Approximability of Minimum AND-Circuits“. Zusammen bilden sie einen einzigartigen Fingerprint.Projekte
- 1 Abgeschlossen
-
Robuste Lernverfahren und Datenkomprimierung
Reischuk, R. (Projektleiter*in (PI))
01.01.04 → 31.12.08
Projekt: DFG-Projekte › DFG Einzelförderungen