Approximability of minimum AND-circuits

DOI10.1007/S00453-007-9039-0zbMATH Open1172.68061OpenAlexW2057316079MaRDI QIDQ1024782FDOQ1024782

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/

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

zbMATH Keywords

approximation algorithmsinapproximabilitycircuit design

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Cites Work

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

Cited In (4)

• AND-compression of NP-complete problems: streamlined proof and minor observations
• The Minimum Oracle Circuit Size Problem.
• Improved approximation algorithms for minimum AND-circuits problem via \(k\)-set cover
• Approximability of Minimum AND-Circuits

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)