Computational complexity of the minimum committee problem and related problems

DOI10.1134/S1064562406010376zbMath1155.94396OpenAlexW2043825590MaRDI QIDQ1005473

Mikhail Yu. Khachay

Publication date: 9 March 2009

Published in: Doklady Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1134/s1064562406010376

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Authentication, digital signatures and secret sharing (94A62)

Related Items (4)

Committee polyhedral separability: complexity and polynomial approximation ⋮ Computational complexity of recognition learning procedures in the class of piecewise-linear committee decision rules ⋮ Scheme of boosting in the problems of combinatorial optimization induced by the collective training algorithms ⋮ Parallel computations and committee constructions

Cites Work

• A threshold of ln n for approximating set cover
• On the hardness of approximating minimization problems
• Unnamed Item
• Unnamed Item

This page was built for publication: Computational complexity of the minimum committee problem and related problems