Reduced error pruning of branching programs cannot be approximated to within a logarithmic factor

DOI10.1016/S0020-0190(03)00255-2zbMath1175.68562MaRDI QIDQ1014397

Richard Nock, Tapio Elomaa, Matti Kääriäinen

Publication date: 28 April 2009

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

algorithmsinapproximabilitybranching programreduced error pruning

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Uses Software

• C4.5

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The difficulty of reduced error pruning of leveled branching programs
• Boosting using branching programs
• A threshold of ln n for approximating set cover
• Some optimal inapproximability results

This page was built for publication: Reduced error pruning of branching programs cannot be approximated to within a logarithmic factor