On the difficulty of approximately maximizing agreements.
type: Item
instance of: scholarly article
title: On the difficulty of approximately maximizing agreements.
zbMATH Open document ID: 1053.68054
DOI: 10.1016/S0022-0000(03)00038-2
author: Shai Ben-David
author: Nadav Eiron
author: Philip M. Long
published in: Journal of Computer and System Sciences
publication date: 2003-08-19T00:00:00Z
Mathematics Subject Classification ID: 68Q32
Mathematics Subject Classification ID: 68T05
zbMATH DE Number: 1967144
zbMATH Keywords: Machine learning
zbMATH Keywords: Computational learning theory
zbMATH Keywords: Neural networks
zbMATH Keywords: Inapproximability
zbMATH Keywords: Hardness
zbMATH Keywords: Half-spaces
zbMATH Keywords: Axis-aligned hyper-rectangles
zbMATH Keywords: Balls
zbMATH Keywords: Monomials
describes a project that uses: AdaBoost.MH
MaRDI profile type: Publication
cites work: The complexity and approximability of finding maximum feasible subsystems of linear relations
cites work: The hardness of approximate optima in lattices, codes, and systems of linear equations
cites work: Learnability and the Vapnik-Chervonenkis dimension
cites work: Computing the maximum bichromatic discrepancy, with applications to computer graphics and machine learning
cites work: Q4228484
cites work: Q4526964
cites work: Decision theoretic generalizations of the PAC model for neural net and other learning applications
cites work: Tracking drifting concepts by minimizing disagreements
cites work: Robust trainability of single neurons
cites work: Learning in the Presence of Malicious Errors
cites work: Cryptographic limitations on learning Boolean formulae and finite automata
cites work: Toward efficient agnostic learning
cites work: Cryptographic hardness of distribution-specific learning
cites work: Computational limitations on learning from examples
full work available at URL: s0022-0000(03)00038-2
OpenAlex ID: W1968934255
Recommended article: A note on bargaining over a finite number of feasible agreements
Recommended article: The maximum incentive solutions in bargaining problems
Recommended article: Efficient solutions to bargaining problems with uncertain disagreement points
Recommended article: The Complexity of Optimal Mechanism Design
Recommended article: On the Complexity of Approximating a Nash Equilibrium
Recommended article: Q5365135
Recommended article: Q3035169
Recommended article: Q3524711
Recommended article: On the structure and complexity of worst-case equilibria
description: scientific article; zbMATH DE number 1967144