On approximating NP-hard optimization problems
type: Item
instance of: scholarly article
title: On approximating NP-hard optimization problems
zbMATH Open document ID: 0910.68093
published in: Documenta Mathematica
publication date: 1998-08-05T00:00:00Z
full work available at URL: Hastad.MAN.html
review text: Consider the problem of satisfying the maximal number of equations in an over-determined system of linear equations. The author shows that it is NP-hard to approximate this problem within a factor smaller than 2.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 1184382
zbMATH Keywords: NP-hard optimization problems
zbMATH Keywords: approximating algorithms
zbMATH Keywords: linear equations
author: Johan Hastad
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1184382