𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the Maximality of Logics with Approximations

✍ Scribed by José Iovino

Book ID
124978646
Publisher
Association for Symbolic Logic
Year
2001
Tongue
English
Weight
244 KB
Volume
66
Category
Article
ISSN
0022-4812

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On the difficulty of approximately maxim
On the difficulty of approximately maximizing agreements
✍ Shai Ben-David; Nadav Eiron; Philip M. Long 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 211 KB

We address the computational complexity of learning in the agnostic framework. For a variety of common concept classes we prove that, unless P ¼ NP; there is no polynomial time approximation scheme for finding a member in the class that approximately maximizes the agreement with a given training sam

On the maximality of Sn in
On the maximality of Sn in
✍ Justine Skalba 📂 Article 📅 1982 🏛 Elsevier Science 🌐 English ⚖ 991 KB
On the approximability of clique and rel
On the approximability of clique and related maximization problems
✍ Aravind Srinivasan 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 247 KB

We consider approximations of the form n 1Àoð1Þ for the Maximum Clique problem, where n is the number of vertices in the input graph and where the ''oð1Þ'' term goes to zero as n increases. We show that sufficiently strong negative results for such problems, which we call strong inapproximability re