Approximability of minimum AND-circuits

DOI10.1007/S00453-007-9039-0MaRDI QIDQ1024782zbMATH OpenOpenAlexFDO

Authors Jan Arpe, Bodo Manthey

Publication date 17 June 2009

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2006/603/

zbMATH Keywords

approximation algorithmsinapproximabilitycircuit design

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Recommendations

• Approximability of Minimum AND-Circuits
• Improved approximation algorithms for minimum AND-circuits problem via \(k\)-set cover
• Minimizing Disjunctive Normal Form Formulas and $AC^0$ Circuits Given a Truth Table
• On approximability of Boolean formula minimization
• Publication:4938653

Cites work

• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• scientific article; zbMATH DE number 3750146 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• Approximation algorithms for combinatorial problems
• Circuit minimization problem
• Complexity of Monotone Networks for Computing Conjunctions
• Complexity of approximating bounded variants of optimization problems
• Computing Sequences with Addition Chains
• Efficient Generation of Minimal Length Addition Chains
• Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
• Grammar-based codes: a new class of universal lossless source codes
• Hardness of approximate two-level logic minimization and PAC learning with membership queries
• Minimizing Disjunctive Normal Form Formulas and $AC^0$ Circuits Given a Truth Table
• Network flows. Theory, algorithms, and applications.
• Some APX-completeness results for cubic graphs
• Some simplified NP-complete graph problems
• The Smallest Grammar Problem
• The macro model for data compression (extended abstract)
• The minimum equivalent DNF problem and shortest implicants

Cited in

(3)

• Approximability of Minimum AND-Circuits
• The Minimum Oracle Circuit Size Problem.
• Improved approximation algorithms for minimum AND-circuits problem via \(k\)-set cover

This page was built for publication: Approximability of minimum AND-circuits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1024782)