Projects per year
Abstract
Given a set of monomials, the MinimumANDCircuit problem asks for a circuit that computes these monomials using ANDgates of fanin 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 ANDCIRCUIT problem and several problems from different areas.
Original language  English 

Title of host publication  SWAT 2006: Algorithm Theory – SWAT 2006 
Number of pages  12 
Volume  4059 LNCS 
Publisher  Springer Verlag 
Publication date  01.01.2006 
Pages  292303 
ISBN (Print)  9783540357537 
ISBN (Electronic)  9783540357551 
DOIs  
Publication status  Published  01.01.2006 
Event  10th Scandinavian Workshop on Algorithm Theory  Riga, Latvia Duration: 06.07.2006 → 08.07.2006 Conference number: 67922 
Fingerprint
Dive into the research topics of 'Approximability of Minimum ANDCircuits'. Together they form a unique fingerprint.Projects
 1 Finished

Robust learning methods and data compression
01.01.04 → 31.12.08
Project: DFG Projects › DFG Individual Projects