Göm menyn
Files: Description Format
Fulltext PDF (requires Acrobat Reader)
Fulltext PostScript (requires a PostScript Reader)
Author: Peter Jonsson
Article title: Tight Lower Bounds on the Approximability of Some NPO PB-Complete Problems
Publ. type: Article
Volume: 2
Article No: 4
Language: English
Abstract [en]: We investigate the approximability of the NPO PB-complete problems MIN ONES, MIN DONES, MAX ONES, MAX DONES
and MAX PB 0/1 PROGRAMMING. We show that, unless P = NP, these problems are not approximable within n1-ε} for any ε > 0 where n is the number of variables in the input. Since all of these problems are approximable within n, this lower bound is close to optimal.
Publisher: Linköping University Electronic Press
Year: 1997
Available: 1997-04-11
No. of pages: 9
Series: Linköping Electronic Articles in Computer and Information Science
ISSN: 1401-9841

Responsible for this page: Peter Berkesand
Last updated: 2017-02-21