Files: Description File size 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.
PDF
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
REFERENCE TO THIS PAGE:
Jonsson, Peter (1997). Tight Lower Bounds on the Approximability of Some NPO PB-Complete Problems in Linköping Electronic Articles in Computer and Information Science, Vol. 2. http://www.ep.liu.se/ea/cis/1997/004/. ()